summaryrefslogtreecommitdiffstats
path: root/browser/components/urlbar/docs/ranking.rst
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-21 11:44:51 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-21 11:44:51 +0000
commit9e3c08db40b8916968b9f30096c7be3f00ce9647 (patch)
treea68f146d7fa01f0134297619fbe7e33db084e0aa /browser/components/urlbar/docs/ranking.rst
parentInitial commit. (diff)
downloadthunderbird-upstream.tar.xz
thunderbird-upstream.zip
Adding upstream version 1:115.7.0.upstream/1%115.7.0upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'browser/components/urlbar/docs/ranking.rst')
-rw-r--r--browser/components/urlbar/docs/ranking.rst229
1 files changed, 229 insertions, 0 deletions
diff --git a/browser/components/urlbar/docs/ranking.rst b/browser/components/urlbar/docs/ranking.rst
new file mode 100644
index 0000000000..a1c9d03c3c
--- /dev/null
+++ b/browser/components/urlbar/docs/ranking.rst
@@ -0,0 +1,229 @@
+=======
+Ranking
+=======
+
+Before results appear in the UrlbarView, they are fetched from providers.
+
+Each `UrlbarProvider <https://firefox-source-docs.mozilla.org/browser/urlbar/overview.html#urlbarprovider>`_
+implements its own internal ranking and returns sorted results.
+
+Externally all the results are ranked by the `UrlbarMuxer <https://searchfox.org/mozilla-central/source/browser/components/urlbar/UrlbarMuxerUnifiedComplete.jsm>`_
+according to an hardcoded list of groups and sub-grups.
+
+.. NOTE:: Preferences can influence the groups order, for example by putting
+ Firefox Suggest before Search Suggestions.
+
+The Places provider, responsible to return history and bookmark results, uses
+an internal ranking algorithm called Frecency.
+
+Frecency implementation
+=======================
+
+Frecency is a term derived from `frequency` and `recency`, its scope is to provide a
+ranking algorithm that gives importance both to how often a page is accessed and
+when it was last visited.
+Additionally, it accounts for the type of each visit through a bonus system.
+
+To account for `recency`, a bucketing system is implemented.
+If a page has been visited later than the bucket cutoff, it gets the weight
+associated with that bucket:
+
+- Up to 4 days old - weight 100 - ``places.frecency.firstBucketCutoff/Weight``
+- Up to 14 days old - weight 70 - ``places.frecency.secondBucketCutoff/Weight``
+- Up to 31 days old - weight 50 - ``places.frecency.thirdBucketCutoff/Weight``
+- Up to 90 days old - weight 30 - ``places.frecency.fourthBucketCutoff/Weight``
+- Anything else - weight 10 - ``places.frecency.defaultBucketWeight``
+
+To account for `frequency`, the total number of visits to a page is used to
+calculate the final score.
+
+The type of each visit is taken into account using specific bonuses:
+
+Default bonus
+ Any unknown type gets a default bonus. This is expected to be unused.
+ Pref ``places.frecency.defaultVisitBonus`` current value: 0.
+Embed
+ Used for embedded/framed visits not due to user actions. These visits today
+ are stored in memory and never participate to frecency calculation.
+ Thus this is currently unused.
+ Pref ``places.frecency.embedVisitBonus`` current value: 0.
+Framed Link
+ Used for cross-frame visits due to user action.
+ Pref ``places.frecency.framedLinkVisitBonus`` current value: 0.
+Download
+ Used for download visits. It’s important to support link coloring for these
+ visits, but they are not necessarily useful address bar results (the Downloads
+ view can do a better job with these), so their frecency can be low.
+ Pref ``places.frecency.downloadVisitBonus`` current value: 0.
+Reload
+ Used for reload visits (refresh same page). Low because it should not be
+ possible to influence frecency by multiple reloads.
+ Pref ``places.frecency.reloadVisitBonus`` current value: 0.
+Redirect Source
+ Used when the page redirects to another one.
+ It’s a low value because we give more importance to the final destination,
+ that is what the user actually visits, especially for permanent redirects.
+ Pref ``places.frecency.redirectSourceVisitBonus`` current value: 25.
+Temporary Redirect
+ Used for visits resulting from a temporary redirect (HTTP 307).
+ Pref ``places.frecency.tempRedirectVisitBonus`` current value: 40.
+Permanent Redirect
+ Used for visits resulting from a permanent redirect (HTTP 301). This is the
+ new supposed destination for a url, thus the bonus is higher than temporary.
+ In this case it may be advisable to just pick the bonus for the source visit.
+ Pref ``places.frecency.permRedirectVisitBonus`` current value: 50.
+Bookmark
+ Used for visits generated from bookmark views.
+ Pref ``places.frecency.bookmarkVisitBonus`` current value: 75.
+Link
+ Used for normal visits, for example when clicking on a link.
+ Pref ``places.frecency.linkVisitBonus`` current value: 100.
+Typed
+ Intended to be used for pages typed by the user, in reality it is used when
+ the user picks a url from the UI (history views or the Address Bar).
+ Pref ``places.frecency.typedVisitBonus`` current value: 2000.
+
+The above bonuses are applied to visits, in addition to that there are also a
+few bonuses applied in case a page is not visited at all, both of these bonuses
+can be applied at the same time:
+
+Unvisited bookmarked page
+ Used for pages that are bookmarked but unvisited.
+ Pref ``places.frecency.unvisitedBookmarkBonus`` current value: 140.
+Unvisited typed page
+ Used for pages that were typed and now are bookmarked (otherwise they would
+ be orphans).
+ Pref ``places.frecency.unvisitedTypedBonus`` current value: 200.
+
+Two special frecency values are also defined:
+
+- ``-1`` represents a just inserted entry in the database, whose score has not
+ been calculated yet.
+- ``0`` represents an entry for which a new value should not be calculated,
+ because it has a poor user value (e.g. place: queries) among search results.
+
+Finally, because calculating a score from all of the visits every time a new
+visit is added would be expensive, only a sample of the last 10
+(pref ``places.frecency.numVisits``) visits is used.
+
+How frecency for a page is calculated
+-------------------------------------
+
+.. mermaid::
+ :align: center
+ :caption: Frecency calculation flow
+
+ flowchart TD
+ start[URL]
+ a0{Has visits?}
+ a1[Get last 10 visit]
+ a2[bonus = unvisited_bonus + bookmarked + typed]
+ a3{bonus > 0?}
+ end0[Frecency = 0]
+ end1["frecency = age_bucket_weight * (bonus / 100)"]
+ a4[Sum points of all sampled visits]
+ a5{points > 0?}
+ end2[frecency = -1]
+ end3["Frecency = visit_count * (points / sample_size)"]
+ subgraph sub [Per each visit]
+ sub0[bonus = visit_type_bonus]
+ sub1{bookmarked?}
+ sub2[add bookmark bonus]
+ sub3["score = age_bucket_weight * (bonus / 100)"]
+ sub0 --> sub1
+ sub1 -- yes --> sub2
+ sub1 -- no --> sub3
+ sub2 --> sub3;
+ end
+ start --> a0
+ a0 -- no --> a2
+ a2 --> a3
+ a3 -- no --> end0
+ a3 -- yes --> end1
+ a0 -- yes --> a1
+ a1 --> sub
+ sub --> a4
+ a4 --> a5
+ a5 -- no --> end2
+ a5 -- yes --> end3
+
+1. If the page is visited, get a sample of ``NUM_VISITS`` most recent visits.
+2. For each visit get a transition bonus, depending on the visit type.
+3. If the page is bookmarked, add to the bonus an additional bookmark bonus.
+4. If the bonus is positive, get a bucket weight depending on the visit date.
+5. Calculate points for the visit as ``age_bucket_weight * (bonus / 100)``.
+6. Sum points for all the sampled visits.
+7. If the points sum is zero, return a ``-1`` frecency, it will still appear in the UI.
+ Otherwise, frecency is ``visitCount * points / NUM_VISITS``.
+8. If the page is unvisited and not bookmarked, or it’s a bookmarked place-query,
+ return a ``0`` frecency, to hide it from the UI.
+9. If it’s bookmarked, add the bookmark bonus.
+10. If it’s also a typed page, add the typed bonus.
+11. Frecency is ``age_bucket_weight * (bonus / 100)``
+
+When frecency for a page is calculated
+--------------------------------------
+
+Operations that may influence the frecency score are:
+
+* Adding visits
+* Removing visits
+* Adding bookmarks
+* Removing bookmarks
+* Changing the url of a bookmark
+
+Frecency is recalculated:
+
+* Immediately, when a new visit is added. The user expectation here is that the
+ page appears in search results after being visited. This is also valid for
+ any History API that allows to add visits.
+* In background on idle times, in any other case. In most cases having a
+ temporarily stale value is not a problem, the main concern would be privacy
+ when removing history of a page, but removing whole history will either
+ completely remove the page or, if it's bookmarked, it will still be relevant.
+ In this case, when a change influencing frecency happens, the ``recalc_frecency``
+ database field for the page is set to ``1``.
+
+Recalculation is done by the `PlacesFrecencyRecalculator <https://searchfox.org/mozilla-central/source/toolkit/components/places/PlacesFrecencyRecalculator.sys.mjs>`_ module.
+The Recalculator is notified when ``PlacesUtils.history.shouldStartFrecencyRecalculation``
+value changes from false to true, that means there's values to recalculate.
+A DeferredTask is armed, that will look for a user idle opportunity
+in the next 5 minutes, otherwise it will run when that time elapses.
+Once all the outdated values have been recalculated
+``PlacesUtils.history.shouldStartFrecencyRecalculation`` is set back to false
+until the next operation invalidating a frecency.
+The recalculation task is also armed on the ``idle-daily`` notification.
+
+When the task is executed, it recalculates frecency of a chunk of pages. If
+there are more pages left to recalculate, the task is re-armed. After frecency
+of a page is recalculated, its ``recalc_frecency`` field is set back to ``0``.
+
+Frecency is also decayed daily during the ``idle-daily`` notification, by
+multiplying all the scores by a decay rate of ``0.975`` (half-life of 28 days).
+This guarantees entries not receiving new visits or bookmarks lose relevancy.
+
+
+Adaptive Input History
+======================
+
+Input History (also known as Adaptive History) is a feature that allows to
+find urls that the user previously picked. To do so, it associates search strings
+with picked urls.
+
+Adaptive results are usually presented before frecency derived results, making
+them appear as having an infinite frecency.
+
+When the user types a given string, and picks a result from the address bar, that
+relation is stored and increases a use_count field for the given string.
+The use_count field asymptotically approaches a max of ``10`` (the update is
+done as ``use_count * .9 + 1``).
+
+On querying, all the search strings that start with the input string are matched,
+a rank is calculated per each page as ``ROUND(MAX(use_count) * (1 + (input = :search_string)), 1)``,
+so that results perfectly matching the search string appear at the top.
+Results with the same rank are additionally sorted by descending frecency.
+
+On daily idles, when frecency is decayed, also input history gets decayed, in
+particular the use_count field is multiplied by a decay rate of ``0.975``.
+After decaying, any entry that has a ``use_count < 0.975^90 (= 0.1)`` is removed,
+thus entries are removed if unused for 90 days.