504879 - Improve autocomplete ranking

Status: RESOLVED FIXED

(Camino Graveyard :: Location Bar & Autocomplete, enhancement)

Description

[Stuart Morgan]

Placeholder for Dan's work on creating a clever ranking strategy. Proposal to follow.

Comment 1

[Smokey Ardisson (offline for a while; not following bugs - do not email)]

Dan, can you dump the proposal into this bug in order to make it a more useful bug? ;)

Comment 2

[Stuart Morgan]

We probably need to do at least some of this for 2.1, to better solve the "old bookmarks are cluttering my results" problem. We should do some kind of scoring that takes last visit date into account much more strongly--that would also solve other bad cases like "The bookmark I visited 10 times a year ago ranks higher than the bookmark made last week and have visited every day".

I'll make a simple-but-not-quite-as-simple-as-the-current-one scoring function for b1 and we'll see how it feels (in conjunction with the soft-limit per source, probably).

Comment 3

[Stuart Morgan]

Attachment: first attempt

This is an attempt at a better scoring algorithm; we'll land it and see how it works for people and then adjust as necessary. All the refactoring here will be useful regardless of the details of the scoring.

This will make it take longer to build the Tries on launch, and cost a bit more CPU to keep it up to date over time. I spent a fair amount of time with Shark though, trimming off many of the most expensive bits (thus all the special handling of getting the current time), so the impact won't be too high.

An obvious question in the design is why I recompute the scores all the time instead of storing them. One is a CPU/memory tradeoff, but the other is that the score varies over time, and by doing it this way I don't have to do something nasty like periodically re-score the entire Trie based on a timer (or, in a different form of nasty, ignore the fact that scores would get out of sync, such that running for a while, running a search, quitting, relaunching, and running the search again would give different results).

Pink, this is another one I'd appreciate an after-the-fact review on. I'll be doing some refactoring in follow-ups; I didn't want this patch to get too big.

Comment 4

[Stuart Morgan]

For those following along at home, the scoring algorithm is now conceptually:
1) Take the number of visits
2) Multiply by 1.1 if it's a bookmark
3) Multiply by an age factor:
- 0.1 if the last visit was over a year ago
- 0.5 if the last visit was over a month ago
- 0.9 if the last visit was over a week ago
(these aren't cumulative; only the longest applicable time period's multiplier applies)
4) Break ties in favor of the most recent visit

Only step 3 is new. Everything else, including the limit-per-source, is unchanged.

I basically just made those numbers up. They may not be severe enough, they may be too severe. They may be too jaggy and be better as a continuous function based on age. Ultimately the only way we'll be able to tell is to have people bang on it, see what works and what doesn't, and go from there.

Comment 5

[Stuart Morgan]

Landed as http://hg.mozilla.org/camino/rev/3abad5cb6ed5

We'll file new bugs for any followups.