Last Comment Bug 395739 - (awesomebar) adaptive learning (match entered text to selected item) in url bar autocomplete
(awesomebar)
: adaptive learning (match entered text to selected item) in url bar autocomplete
Status: VERIFIED FIXED
[fixes bug 411293]
:
Product: Firefox
Classification: Client Software
Component: Location Bar (show other bugs)
: Trunk
: All All
: P3 normal with 13 votes (vote)
: Firefox 3 beta4
Assigned To: Ed Lee :Mardak
:
Mentors:
Depends on: 395735 406359 414287
Blocks: 406427 392143 404261 405745 406257 406422 406425 411293
  Show dependency treegraph
 
Reported: 2007-09-10 21:27 PDT by (not reading, please use seth@sspitzer.org instead)
Modified: 2011-11-02 13:12 PDT (History)
38 users (show)
mbeltzner: blocking‑firefox3+
reed: wanted‑firefox3+
edilee: in‑testsuite+
stephen.donner: in‑litmus+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
v1 (11.12 KB, patch)
2007-11-03 18:06 PDT, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v1.1 (13.73 KB, patch)
2007-11-03 20:38 PDT, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v1.2 (13.47 KB, patch)
2007-11-04 20:15 PST, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v2 (19.91 KB, patch)
2007-12-02 03:42 PST, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v3 (18.82 KB, patch)
2008-01-17 00:10 PST, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v4 (22.87 KB, patch)
2008-01-18 16:28 PST, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v4.1 (22.62 KB, patch)
2008-01-23 19:12 PST, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v4.2 (23.07 KB, patch)
2008-01-27 14:34 PST, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v4.3 (21.90 KB, patch)
2008-01-27 19:50 PST, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v4.4 (21.84 KB, patch)
2008-02-02 22:17 PST, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v4.5 (20.45 KB, patch)
2008-02-06 23:19 PST, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v5 (14.04 KB, patch)
2008-02-07 20:55 PST, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v5.1 (14.23 KB, patch)
2008-02-11 18:35 PST, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v5.2 (14.19 KB, patch)
2008-02-17 10:43 PST, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v5.3 (14.13 KB, patch)
2008-02-18 14:57 PST, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v5.4 (14.25 KB, patch)
2008-02-21 09:02 PST, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v5.5 (13.82 KB, patch)
2008-02-25 10:18 PST, Ed Lee :Mardak
no flags Details | Diff | Splinter Review
v5.6 (13.70 KB, patch)
2008-02-25 15:35 PST, Ed Lee :Mardak
dietrich: review+
Details | Diff | Splinter Review
v5.7 (13.03 KB, patch)
2008-02-27 14:30 PST, Ed Lee :Mardak
edilee: review+
mbeltzner: approval1.9b4+
mbeltzner: approval1.9+
Details | Diff | Splinter Review

Description (not reading, please use seth@sspitzer.org instead) 2007-09-10 21:27:38 PDT
adaptive learning (match entered text to selected item) in url bar autocomplete

mconnor wrote:

<mconnor> which is kinda/sorta how quicksilver learns
<mconnor> though it remembers "fo" == "foo.com" rather than just making foo.com
>rate higher for anything matching

faaborg wrote:

I think we should seriously consider this type of adaptive learning.  Another
difference is that the first match in Quicksilver is set as the default action
on enter (like Safari).

I'm not sure what the 5 delight items currently are, but what do people think about bumping the least interesting item for a quicksilver inspired adaptive learning algorithm in the location bar auto-complete?  (https://bugzilla.mozilla.org/show_bug.cgi?id=395446)

For instance, if every time you type "ph" you select a bookmark called "phonebook", that result will be bumped up in the results for "ph" in the future, even if you have a bookmark called "phishing UI" that has a much higher overall frecency than "phonebook."

The search in the location bar is already a killer feature, and I think this would streamline the interaction even more. 

beltzner wrote:

That sounds like a good modification to the frecency algorithm to me.

dietrich wrote:

alex, that'd be *very* cool. as this bug is closed, can you file a new bug,
clearly spec'ing out the behavior?

gavin wrote:

See also bug 370117: it has a patch that makes us keep a record of how many
times a form history autocomplete entries are used, so that we can sort them by
frequency of use in the dropdown. That patch implements a formhistory-specific
API, but we could instead modify nsIAutocompleteResult to enable the
autocompletecontroller to notify the nsIAutocompleteSearch implementations of a
selected result, and have it record that data and take it into account when it
performs searches.
Comment 1 (not reading, please use seth@sspitzer.org instead) 2007-09-10 21:31:59 PDT
question for faaborg:  how would this interact with tag results?

If I have a tag for "calendar", should items tagged with "calendar" still show up first (before all other results), even if I choose a different results after typing "calendar"?
Comment 2 Alex Faaborg [:faaborg] (Firefox UX) 2007-09-10 21:48:36 PDT
>how would this interact with tag results?

I'm now in the process of backpedaling on previous statements about grouping results by type (spotlight), or favoring certain types over others in the ranking (tags).  I'll be posting fresh mockups to bug #393508, hopefully later tonight.
Comment 3 Ed Lee :Mardak 2007-10-30 02:12:34 PDT
Could this be done with a new table (moz_inputs) that contained:

1) places_id int (moz_places.id)
2) input string
3) usage_count int

key: placed_id + input

So for the current order by query..
"ORDER BY h.typed DESC, h.visit_count DESC..."

ORDER BY (SELECT i.usage_count FROM moz_inputs i WHERE i.places_id = h.id AND i.input LIKE ?3 ESCAPE '/' ORDER BY i.input = ?3 DESC, i.usage_count DESC LIMIT 1), h.typed DESC, ...

Basically sort all the results based that would have originally been shown but first sort by usage count of the corresponding places id and user input.

The "input LIKE ?3" with "input = ?3" allows it to match partial inputs but will always take the exact match first. This could help the user end up typing fewer and fewer characters.

For example, if "mozilla" -> mozilla.org was the only entry in moz_inputs with a usage_count of 10, the user could type "moz" and still get the benefit of the "10". This would probably be better than treating all the items equally. Additionally, "moz" would get a new entry to mozilla.org so next time it'll be an exact match for "moz".

Similarly, it would be flexible enough to allow new inputs like "ill". At first this would show mozilla.org because that's all it knows about, but perhaps the user goes to illinois.edu. Next time "ill" will choose illinois.edu (1) over mozilla.org (10) because it's a perfect match.

The "usage_count DESC" is to just provide a fallback for cases like "il" that can match "mozilla" or "ill", so it'll just go with whatever is stronger (10 mozilla.org).

(Note: ORDER BY (SELECT resulting in null) will have the null entries last for DESC [or null entries first for ASC], which is what we want.)


On selection, the entry in moz_inputs would be incremented or created. Potentially we might want to do some decay as well -- scale all entries that match the input by 90%. This would allow for changing preferences.. maybe the user wants "ill" to go to mozilla.org instead of illinois.edu. (Before places, the only way was to delete the autocomplete entry and "rebuild the usage history" from scratch.)

[I suppose I could write the patch if I had time and figured out how to create new tables.. and if necessary follow up if the nested queries doesn't have good performance...]
Comment 4 Ed Lee :Mardak 2007-11-03 18:06:28 PDT
Created attachment 287270 [details] [diff] [review]
v1

New interface for feedback-directed stuff.. right now just search. (Anything else that could use this?)

Slightly different from what I proposed earlier -- grabbing the exact match doesn't help when comparing it to other URLs. (E.g., exact match = 5, fuzzy = 50; the fuzzy one wins when we do DESC) So I gave the exact match more weight.

I also had to add a new bind parameter because directly comparing strings with extra %'s isn't useful. :p
Comment 5 Ed Lee :Mardak 2007-11-03 18:30:26 PDT
For simple cases where only single entries match (e.g., you always type "mozilla" to go to mozilla.com), it'll be the only entry that has a rank value, so it's first. The other entries are sorted as they were before this feedback stuff.

Slightly trickier is if you type "mozilla" often and have 50 hits and decided to switch to "moz" which now has 1 hit, typing "mo" will rank based on the 50-hit entry.

For an even trickier situation..

Assume we have these <input> -> <url> <rank> values:

moz -> bugzilla 5
moz -> devmo 10
mozilla -> bugzilla 50
mozilla -> devmo 2

If the user types "mo", they get bugzilla because it's the best rank overall.
mo: *bugzilla* (50) vs devmo (10)

"moz" gets devmo because it's an exact match
moz: bugzilla (105) vs *devmo* (110)

"mozil" only matches "mozilla", so it uses those values
mozil: *bugzilla* (50) vs devmo (2)


---


And if anybody wanted a main use case.. (at least it's the main use case that irks me :p)

I frequent 2 forums: http://www.neogaf.com/forum/forumdisplay.php?f=2 and http://forums.mozillazine.org/viewforum.php?f=23

I always type "neo" to get the first and "forums" to get the second. The reason why I have to type out "forums" is because the first site has a higher visit count than the second and typing the "s" filters out the first site.

With the adaptive, Firefox could learn that "neo" should show the first and "for" should show the second.
Comment 6 Ed Lee :Mardak 2007-11-03 20:38:56 PDT
Created attachment 287282 [details] [diff] [review]
v1.1

Ooops, forgot to 'hg add' the idl file.

Here's some builds that include this patch if people want to look at how it behaves.

https://build.mozilla.org/tryserver-builds/2007-11-03_18:58-edward.lee@engineering.uiuc.edu-adaptive.urlbar/
Comment 7 Marco Bonardo [::mak] (Away 6-20 Aug) 2007-11-04 17:51:07 PST
can i suggest for insert a query like
REPLACE INTO moz_inputhistory
SELECT h.id, COALESCE(input, ?2), COALESCE(use_count, 0) + 1
FROM moz_places h
LEFT JOIN moz_inputhistory ON place_id = h.id AND input = ?2
WHERE url = ?1

also i think that when a moz_places is removed (for example after an expire, or after a clear history), the corresponding inputhistory should be dropped.

what about searches like "ww" or "ht", that will fill the table with useless entries (almost all sites start up as www or http...) and for searches made up of one letter like "a". imho you could define a minimum size for the search to be saved, like 3 chars.
Comment 8 Ed Lee :Mardak 2007-11-04 18:08:40 PST
(In reply to comment #7)
> can i suggest for insert a query like
> ...
Aha! I knew there should be a better way than what I came up with. ;) I was on the right track with the LEFT JOIN to get the null entry for use_count.

> also i think that when a moz_places is removed (for example after an expire, or
> after a clear history), the corresponding inputhistory should be dropped.
Ah yup. Is there any automatic way to prune entries with invalid foreign keys? But sqlite doesn't support FOREIGN KEY. We could either prune the dead entries every time a moz_place entry is removed "on demand", or we just occasionally sweep out the moz_inputhistory entries that have a null JOINed id for "garbage collect".

> what about searches like "ww" or "ht", that will fill the table with useless
> entries (almost all sites start up as www or http...) and for searches made up
> of one letter like "a". imho you could define a minimum size for the search to
> be saved, like 3 chars.
Those searches are still useful because the location bar would favor your previously selected "ww" entry. Maybe the user only goes to one site or a handful of sites by "ww" and other keywords for other sites.

The single letter searches are also useful because once the user starts using just a single letter for a particular site, s/he only needs to type that one letter and down/enter to select.
Comment 9 Ed Lee :Mardak 2007-11-04 18:13:58 PST
Because we have the AutoCompleteResult and which index is the selected item, we could factor that into the feedback -- there's a difference between choosing the 1st result vs choosing the 5th result.

For example, we could give a higher initial use_count or reduce the use_count of entries that were skipped.

Along the lines of adapting to shifting preferences.. we could easily just do a mass SET use_count = use_count * .75 WHERE input LIKE ?1.
Comment 10 Ed Lee :Mardak 2007-11-04 20:15:05 PST
Created attachment 287364 [details] [diff] [review]
v1.2

Switched to a REPLACE query that doesn't have all those subqueries, similar to Marco's suggestion.

For the removing stale entries, I'm guessing it should be in nsNavHistory.cpp near where historyvisits are deleted. (But where else? Also in Expire?)

But the garbage collection idea is interesting from a coding and performance perspective. Instead of more code to each "on-place-id-removal," the pruning code would be centralized and run when there are spare cycles... assuming it's okay to be in an inconsistent state.
Comment 11 Marco Bonardo [::mak] (Away 6-20 Aug) 2007-11-05 02:09:21 PST
my comment was not that short searches like "ww" or "a" are totally useless, the problem is that maybe if the table grows too much it will cause slowdowns on location bar (see bugs on location bar autocomplete hangs if the history is too big), and will cause vacuum to be much slower. So a choice to avoid an excessive grow up of the table could be to save only searches made up of at least 3 chars. You should test performance with a very big table and a big history to see how it interacts.

for the cleanup i think that you shoul call a cleanup function in nsNavHistoryExpire::OnQuit() after the ExpireHistoryParanoid(). You could create an ExpireInputStrings() with a query to delete entries without a valid place_id.
Comment 12 Ed Lee :Mardak 2007-11-05 10:36:55 PST
Another way to keep the history smaller is to only track the "best 3" for any particular input. (Would need a way to figure out which entries to drop.. keep a newly added entry even though it would have a use_count of 1?)

Or figure out which entries aren't getting used much - e.g., you used to type "forums" but now always type "for" so the counter is only bumped up for the latter.

For that second idea, that would come naturally with exponentially backing off for unselected entries (use_count *= .75), and OnQuit, prune entries that don't have matching place_id or use_count under .1.
Comment 13 Ed Lee :Mardak 2007-11-05 10:40:25 PST
Oh, and I suppose an even easier.. OnQuit, only remember the entries with the highest 1000 use_counts.
Comment 14 Ed Lee :Mardak 2007-11-05 16:33:28 PST
Another reason that we shouldn't ignore short inputs is that we can use the empty input for feedback as well. The patch already works for updating feedback for entries selected by clicking the down arrow, but it doesn't use it to order the results.

I've seen some users never type anything into the location bar -- every time s/he clicks the down arrow and selects something. With feedback, the user could just click the arrow and select the first entry because that's what s/he selected previously.


dietrich/ss/marco: Any particular reason why the dbSelectStatement in AutoCompleteTypedSearch is created every call instead of created once in CreateAutoCompleteQueries with the other queries? Additionally, the query itself is somewhat different..

with search: SELECT FROM places JOIN hist LEFT book LEFT favi WHERE GROUP ORDER

without search: SELECT FROM places LEFT book LEFT favi JOIN hist WHERE (SELECT DISTINCT) GROUP ORDER

Actually, couldn't the "without search" just reuse the AutoCompleteFullHistorySearch ("with search") code and use the chunking for better responsiveness? The LIKE query would just happen to be '%%', which I would hope is implemented by sqlite as a short circuit.. ;)
Comment 15 Ed Lee :Mardak 2007-12-02 03:42:37 PST
Created attachment 291069 [details] [diff] [review]
v2

Bug 395735 adds the feedback interface, so this bug now just implements it for nsNavHistory.

Bug 406359 unifies search and drop down, so adaptive learning applies to clicking the dropdown and selecting items without a search term.

Reworked mDBAutoCompleteQuery to make things easier for implementing bug 394038. Instead of doing a sub-query for each result, make moz_inputhistory part of the main query and calculate an overall rank.

The rank can be reused for typed, visit_count, visit_date (anything that would go in the ORDER BY).. we just need to figure out a standard way to combine these different "units". For starters, I have the adaptive matching give a rank from 0 to 10 while having an exact match ups the rank by 10. So the total range for adaptive is 0 to 20.

Changed mDBFeedbackIncrease from Increment so that use_count caps out at 10 instead of going up and up forever.

Added ExpireInputHistoryParanoid to handle clearing history.

Testcase makes sure results go up accordingly.
Comment 16 Ed Lee :Mardak 2007-12-02 09:44:46 PST
Here's a tryserver build with the patches for bug 395735, bug 406359, bug 395739 applied. Different from before is that clicking the drop down will show results based on the adaptive engine (compared to now, it just shows the most recent pages). This doesn't include the bugs that depends on this one (decay old, detect shift, limit size).

Well, other major things is that it's updated to the latest trunk which includes the fixes for bug 399664. :)

win32 zip:
https://build.mozilla.org/tryserver-builds/2007-12-02_04:18-edward.lee@engineering.uiuc.edu-awesomebar/edward.lee@engineering.uiuc.edu-awesomebar-firefox-try-win32.zip

win32 installer:
https://build.mozilla.org/tryserver-builds/2007-12-02_04:18-edward.lee@engineering.uiuc.edu-awesomebar/edward.lee@engineering.uiuc.edu-awesomebar-firefox-try-win32.installer.exe

osx:
https://build.mozilla.org/tryserver-builds/2007-12-02_04:18-edward.lee@engineering.uiuc.edu-awesomebar/edward.lee@engineering.uiuc.edu-awesomebar-firefox-try-mac.dmg

linux:
https://build.mozilla.org/tryserver-builds/2007-12-02_04:18-edward.lee@engineering.uiuc.edu-awesomebar/edward.lee@engineering.uiuc.edu-awesomebar-firefox-try-linux.tar.bz2
Comment 17 bomfog 2007-12-05 17:03:52 PST
I've been using the win32 zip for a few days without problems. Seems to work great, but I haven't really compared head-to-head to know the actual effect.

Do your later tryserver builds with "aw.bar" in the file name have the same changes? The 2007-12-04_22:14-...-aw.bar.dl.mgr build seems fine too, using it at the moment.

Intuitive, automatic one or two letter shortcuts? This is gonna be beautiful.
Comment 18 Ed Lee :Mardak 2007-12-05 17:19:04 PST
Yup. The latest build has the patches here as well as the blocks bugs like decaying values and penalizing skipped results.

For other people who want to try out..

win 32 zip:
https://build.mozilla.org/tryserver-builds/2007-12-04_22:14-edward.lee@engineering.uiuc.edu-aw.bar.dl.mgr/edward.lee@engineering.uiuc.edu-aw.bar.dl.mgr-firefox-try-win32.zip

win 32 installer:
https://build.mozilla.org/tryserver-builds/2007-12-04_22:14-edward.lee@engineering.uiuc.edu-aw.bar.dl.mgr/edward.lee@engineering.uiuc.edu-aw.bar.dl.mgr-firefox-try-win32.installer.exe

os x:
https://build.mozilla.org/tryserver-builds/2007-12-04_22:14-edward.lee@engineering.uiuc.edu-aw.bar.dl.mgr/edward.lee@engineering.uiuc.edu-aw.bar.dl.mgr-firefox-try-mac.dmg

linux:
https://build.mozilla.org/tryserver-builds/2007-12-04_22:14-edward.lee@engineering.uiuc.edu-aw.bar.dl.mgr/edward.lee@engineering.uiuc.edu-aw.bar.dl.mgr-firefox-try-linux.tar.bz2

And if you were curious about the full list of changes.. (and if you want to comment on how the penalizing works for you or various changes, you can comment in those bugs).

awesomebar:
Bug 395735 - Instrument the location bar auto-complete to report accuracy
Bug 406359 - Unify the logic for url bar searches and drop down items
Bug 406358 - Location bar drop down ignores frequency of visits
Bug 395739 - adaptive learning (match entered text to selected item) in url bar autocomplete
Bug 406422 - Globally decay adaptive input history to allow for new entries
Bug 406425 - Limit how many adaptive input history entries to track
Bug 406427 - Penalize skipped results to allow adaptive learning of shifting preferences

download manager:
Bug 392097 - only showing 7 days of download history, until I search, then I see more items
Bug 405884 - List date/time of download for each download shown
Bug 406230 - Vertically align download icons in the center
Bug 394516 - Figure out a remaining-time rounding scheme for minutes -> hours/days
Bug 406857 - Don't clear referrer when restarting downloads
Bug 405893 - Search should match TLDs as well as download file names
Bug 405888 - Remove the "Information" button at the right of every download row
Bug 405886 - Remove the "Open File" button at the right of every download row
Bug 406923 - Just started downloads don't know about their referrers until reopened
Comment 19 Ed Lee :Mardak 2007-12-06 00:01:18 PST
(In reply to comment #17)
> I haven't really compared head-to-head to know the actual effect.
> Intuitive, automatic one or two letter shortcuts?
If you really wanted to see a difference, using the "aw.bar" build and type in something short in the location bar such as "p" or "h" or "t" or just click the drop-down arrow. Compare that to the results on a standard trunk build. ;)
Comment 20 bomfog 2007-12-06 09:18:13 PST
Training myself to use the location bar instead of bookmarks is taking a little time, but typing one letter, glancing at the auto-completion to verify, and hitting enter is an almost mystical experience. I'm sold.
Comment 21 Alex Faaborg [:faaborg] (Firefox UX) 2008-01-16 12:25:28 PST
Any update on if we are going to be able to get this landed before the beta 3 freeze next week?
Comment 22 Ed Lee :Mardak 2008-01-16 15:31:14 PST
The current uploaded patch is without the global frecency changes. I can update it to patch against what the code would be after bug 394038 lands. Additionally, I can patch with or without the changes for bug 410133. This bug would probably be more likely to land (code-review-wise) without the 'custom sql function' bug landing first.

I still have the test that's already included in the attached patch, but I'll need to modify it if we don't want this bug to depend on bug 406359.
Comment 23 Ed Lee :Mardak 2008-01-17 00:10:07 PST
Created attachment 297504 [details] [diff] [review]
v3

I've updated the patch against the latest patch in bug 394038.

One slight difference from earlier patches is that the adaptive behavior only looks at the beginning of previous inputs (and not anywhere, so "m" matches Mozilla but not attachMent). Additionally, the adaptive rank (0-10) is rounded to 1 decimal point so closely ranked places use frecency instead.

I've also updated the test now that bug 400544 landed (null URI) and assuming bug 406359 (adaptive for clicking dropdown) won't make it.

Marco, would there be any use to avoid MAX(rank) and do ORDER BY rank DESC LIMIT 1 for the subquery in the WHERE? moz_inputhistory should be tiny anyway. Perhaps there should be an additional index on place_id because that's the only thing we check for mDBAutoCompleteQuery.
Comment 24 Ed Lee :Mardak 2008-01-18 16:28:54 PST
Created attachment 297892 [details] [diff] [review]
v4

After using a build with global frecency and adaptive learning, I noticed things were a little slow. Seth, turns out it was the extra ORDER BY having issues with a lot of places having an adaptive rank of 0 (i.e., user selected that place before).

I reworked the adaptive results to be processed before the regular results instead of getting them at the same time and separating with ORDER BY. So both parts return values really fast instead of slowing both down when together.

Here's a build with global frecency and this faster adaptive v4 as well as stopping early after reaching 25 results. For me on my iBook 1.3GHz, results come back instantly. (A debug build of v4 was faster than an optimized v3.)
https://build.mozilla.org/tryserver-builds/2008-01-18_15:28-edward.lee@engineering.uiuc.edu-test.glob.frec.fast.adap/

If you want to compare with a build with the v3 patch..
https://build.mozilla.org/tryserver-builds/2008-01-17_01:06-edward.lee@engineering.uiuc.edu-test.glob.frec.adap/
Comment 25 Ed Lee :Mardak 2008-01-23 19:12:27 PST
Created attachment 298853 [details] [diff] [review]
v4.1

Minor unbitrots from the latest global frecency patch that was checked in.

Additionally, saved some cycles by not bothering to check adaptive results if it's not on the first chunk.
Comment 26 Ed Lee :Mardak 2008-01-27 14:34:34 PST
Created attachment 299620 [details] [diff] [review]
v4.2

Modularize by putting the adaptive search in its own function. This makes it more consistent with how TagsSearch only searches the first time.
Comment 27 Ed Lee :Mardak 2008-01-27 19:50:53 PST
Created attachment 299662 [details] [diff] [review]
v4.3

The AutoCompleteProcessSearch code was unncessarily creeping into this patch that focues on adaptive learning, so I've split it off to bug 414287 (which has its own family of bugs like bug 414285 and bug 414288).

With bug 406359 seeming to be more likely to make it in due to its perf benefits, I've renabled the adaptive tests that makes sure adaptive learning works for clicking the drop down.
Comment 28 Dietrich Ayala (:dietrich) 2008-01-30 17:54:39 PST
Comment on attachment 299662 [details] [diff] [review]
v4.3


>     }
>+
>+    // Get adaptive results after tags on the first chunk
>+    rv = AutoCompleteAdaptiveSearch();
>+    NS_ENSURE_SUCCESS(rv, rv);
>   }

given that adaptive results are far more revisitation-specific than tagging, it seems like those results should display first.
Comment 29 Ed Lee :Mardak 2008-02-02 22:17:22 PST
Created attachment 301081 [details] [diff] [review]
v4.4

More unbitrotting and ProcessSearch doesn't need a dummy anymore.

FYI: This patch is on top of a stack of..

Bug 407944 - for rich autocomplete performance, correctness (rtl) and features (selecting all matches), use one html:span and use selection
Bug 414285 - Refactor AutoCompleteTagsSearch token splitting code and persist tokens
Bug 406359 - Unify the logic for url bar searches and drop down items
Bug 401869 - Allow multiple words search in Auto-complete/Location Bar
Bug 415403 - Show matches for all search words for location bar autocomplete
Bug 395735 - Instrument the location bar auto-complete to report accuracy
Bug 414287 - Share search result processing logic as AutoCompleteProcessSearch
Bug 414288 - Simplify TagsSearch to be correct, clear, concise
Bug 414426 - Optimize SearchTags query by filtering out non-tags
Bug 395739 - adaptive learning (match entered text to selected item) in url bar autocomplete

But I can rework this patch to only require bug 395735 as I originally had for patch v1 back in November. The only major thing on this stack that really affects this adaptive patch is bug 414287 because we can share the logic between tags search and adaptive search.
Comment 30 Ed Lee :Mardak 2008-02-06 23:19:27 PST
Created attachment 301833 [details] [diff] [review]
v4.5

More unbitrotting now that bug 395735 uses the observer service instead of a new interface for feedback. Also, I figured out why "same rank, diff #visits" wasn't working: 1) needed to use setPageDetails instead of just a bunch of addVisits and 2) the query wasn't sorting by visit_count after rank ;)
Comment 31 Ed Lee :Mardak 2008-02-07 20:55:29 PST
Created attachment 302077 [details] [diff] [review]
v5

Unbitrot from changes to bug 395735. Now this patch just focuses on adding the adaptive search results. 

Now only ~10 lines of code plus 1 SQL statement to implement adaptive search results! ;) .. and a 263 lines for the test case :p
Comment 32 Ed Lee :Mardak 2008-02-11 18:35:34 PST
Created attachment 302729 [details] [diff] [review]
v5.1

Unbitrot from bug 414287 which changed the interface to AutoCompleteProcessSearch, so pass in QUERY_ADAPTIVE use the default query behavior.

Just 2 more patches!
Comment 33 Ed Lee :Mardak 2008-02-17 10:43:50 PST
Created attachment 303889 [details] [diff] [review]
v5.2

Save some bitrot for bug 392143 by splitting QueryTypes onto multiple lines. But do we want adaptive searches to show up above bookmark keywords as in attachment 303884 [details]? One feature of showing keywords in the autocomplete is that multiple bookmarks can have the same keyword and the user can pick which one to use.. So potentially the adaptive results would show up one or two or more lower...

Oh, also sort by frecency instead of visit_count to keep with the frecency usages.
Comment 34 Ed Lee :Mardak 2008-02-18 14:57:57 PST
Created attachment 304103 [details] [diff] [review]
v5.3

Pre-emptive unbitrot assuming bug 401660 will be more likely to land before this one as it helps fix blocking bug 405320 and bug 416577, bug 416211, bug 418257.. but then again this bug does fix blocking bug 411293.
Comment 35 Johnathan Nightingale [:johnath] 2008-02-19 08:00:14 PST
Hey Mardak,

The last several revisions feel like they've been (at least partially) un-bitrottings.  For those of us following along at home, is there a plan to get this landed?  I know it's only wanted, but I guess what I'm asking is, should we find you a reviewer and get it approved, or is there still more work happening?

I know you mentioned back in v4.4 that there were a bunch of other, related patches/bugs, but the time we spend your brilliance on bitrot is time we can't spend it on other things.  :)

Mostly, I just feel bad about you being at v5.3 for a 40 line patch (with tests!)
Comment 36 Ed Lee :Mardak 2008-02-19 08:21:30 PST
The only thing really blocking this patch is bug 395735 which is waiting for review. I'll request review from dietrich when this bug is ready to land, i.e., bug 395735 gets reviewed and lands.

I'll keep unbitrotting the patch as I have done for the last several months so that it's always ready for review. (I suppose I do have some personal gains in doing so anyway. ;) I get to use tryserver builds that are trunk+adaptive+other patches instead of nightly builds.)

https://build.mozilla.org/tryserver-builds/2008-02-18_14:34-edward.lee@engineering.uiuc.edu-showall.adaptive.keyword.compact/

Bug 401660 - when showing autocomplete result, show tags that partially match
Bug 407946 - emphasize all matching text in title and url, not just the first
match in title and url
Bug 415403 - Show matches for all search words for location bar autocomplete
Bug 395735 - Instrument the location bar auto-complete to report accuracy
Bug 395739 - adaptive learning (match entered text to selected item) in url bar
autocomplete
Bug 392143 - show keywords as url bar autocomplete choices
Bug 416211 - Tagged results don't show bookmark title when matching the tag
Bug 407204 - adjust the title and url text sizes
Bug 406257 - reduce the number of rows in url bar autocomplete from 10 to 6
Comment 37 Ed Lee :Mardak 2008-02-19 14:11:33 PST
(In reply to comment #35)
> is there still more work happening?
Just to clarify, there hasn't been much changed to the adaptive logic for a few months. The last many patches have been due to unbitrotting code that has checked in or readjusting to a shifting base of other patches.
Comment 38 Ed Lee :Mardak 2008-02-21 09:02:40 PST
Created attachment 304746 [details] [diff] [review]
v5.4

Unbitrot changes from bug 401660 that will reduce the number of columns needed for autocomplete queries.

But then again bug 401660 fixes a P3 blocker bug 405320 while this bug fixes a P2 blocker bug 411293.
Comment 39 Ed Lee :Mardak 2008-02-23 16:29:10 PST
Requesting blocking‑firefox3. I just tried using trunk and it's unusable for me.

I need to type 6 letters to get a page I visit every day instead of just 1 letter? "forums" instead of "f"? Typing 'p' and not getting planet.mozilla.org first? Typing 'm' and finding mail.google as the 5th entry? Clicking the drop down and finding the top results filled with autorefreshing pages instead of pages I actually type more often?

Essentially typing any one letter and not getting the page I want. And not only that, the page that I do want is way down in the list.

Not being able to easily do the most common task I do with a web browser.. visiting my frequently visited pages. That seems pretty blocking to me.
Comment 40 Alex Faaborg [:faaborg] (Firefox UX) 2008-02-23 16:47:02 PST
Using trunk I've found myself adapting to learn which first letter will produce the result I want to streamline the interaction, which really isn't ideal.  The application should adapt, not the user.

Even if we can't get blocking, this bug really deserves wanted+
Comment 41 Ed Lee :Mardak 2008-02-25 10:18:34 PST
Created attachment 305555 [details] [diff] [review]
v5.5

Unbitrot reviewed changes to bug 395735 (which just needs approval to land and this bug would be blocker free). However, I still have the patch on my stack assuming bug 401660 will be fixed first as it fixes more bugs/blocker, so it might be more likely to land first.

https://build.mozilla.org/tryserver-builds/2008-02-25_01:34-edward.lee@engineering.uiuc.edu-saveText.pimpDown.unescape.adaptive/

Bug 416446 - Make PluralForm more useful for extensions and delay importing strings for perf
Bug 415460 - searching in places queries does not decode urls
Bug 418961 - "Save Page As" "Text Files" saves file but Downloads window doesn't show completion
Bug 401660 - when showing autocomplete result, show tags that partially match
Bug 416211 - Tagged results don't show bookmark title when matching the tag
Bug 405320 - support "out of order" multiple word tag search in the url bar and in the places organizer
Bug 418920 - Allow multiple word search with tags in addition to title and url
Bug 419068 - Allow tagged pages to mingle with non-tagged autocomplete results
Bug 407946 - emphasize all matching text in title and url, not just the first match in title and url
Bug 415403 - Show matches for all search words for location bar autocomplete
Bug 395735 - Instrument the location bar auto-complete to report accuracy
Bug 395739 - adaptive learning (match entered text to selected item) in url bar autocomplete
Bug 392143 - show keywords as url bar autocomplete choices
Bug 407204 - adjust the title and url text sizes
Bug 406257 - reduce the number of rows in url bar autocomplete from 10 to 6
Bug 419324 - Edit bookmarks dialog doesn't unescape URLs
Bug 419403 - Pimp My Download Manager Search! (multi word, match any text)
Comment 42 Ed Lee :Mardak 2008-02-25 15:35:33 PST
Created attachment 305623 [details] [diff] [review]
v5.6

Unbitrot review changes to bug 401660 which removed one of the bind parameters for the query.
Comment 43 Dietrich Ayala (:dietrich) 2008-02-27 13:55:32 PST
Comment on attachment 305623 [details] [diff] [review]
v5.6

r=me

however, due to the propensity for lower frecency adaptive results to push down higher frecency non-adaptive results, we may need to cap the number of adaptive results shown. adding the cap is trivial, so lets try this out, and watch feedback.
Comment 44 Dietrich Ayala (:dietrich) 2008-02-27 13:56:18 PST
Comment on attachment 305623 [details] [diff] [review]
v5.6


>+// d1 is younger (should show up higher) than d2 (PRTime is in usecs not msec)
>+let d1 = new Date(Date.now() - 1000 * 60 * 60) * 1000;
>+let d2 = new Date(Date.now() - 1000 * 60 * 60 * 3) * 1000;

and d2 is unused, please remove.
Comment 45 Ed Lee :Mardak 2008-02-27 14:30:01 PST
Created attachment 306130 [details] [diff] [review]
v5.7

r=dietrich

(In reply to comment #43)
> however, due to the propensity for lower frecency adaptive results to push down
> higher frecency non-adaptive results, we may need to cap the number of adaptive
> results shown. adding the cap is trivial, so lets try this out, and watch
> feedback.
That's true, but one of the main reasons for adaptive is to give the user results that *don't* work for frecency. The user types "foo" chooses the 4th result skipping past the first 3 because even though the first 3 have higher frecency, the user actually wants #4 when typing "foo". So next time the user types "f", "fo", or "foo", what was at #4 is now at #1.

For an extreme example, you type "p" and the autocomplete shows your most frecent pages because everything matches p for htt*P*. However, you want "planet.mozilla.org" which you visit frequently but not as much as several other sites that don't even start with "p".

There /is/ a separate issue of picking among two or more adaptive results for the same input, and the user now prefers a highly-adapted result less than a to-be-highly-adapted result. But that's addressed in bug 406422. "Adaptive-adaptive results."

(In reply to comment #44)
> (From update of attachment 305623 [details] [diff] [review])
> >+// d1 is younger (should show up higher) than d2 (PRTime is in usecs not msec)
> >+let d2 = new Date(Date.now() - 1000 * 60 * 60 * 3) * 1000;
> and d2 is unused, please remove.
Removed and fixed comments.. and added comments elsewhere. Split off the test for bug 411293.
Comment 46 Stephen Donner [:stephend] 2008-02-27 14:32:17 PST
Could you (Edward/Dietrich) look over the testcase at https://litmus.mozilla.org/show_test.cgi?id=5196 and let me know how it could be better written?  Thanks!
Comment 47 Ed Lee :Mardak 2008-02-27 14:49:17 PST
(In reply to comment #46)
> Could you (Edward/Dietrich) look over the testcase at..
That should work. FYI, by step 5, the result for "ph" -> phonebook will be the first result.. assuming there hasn't been any previous adaptive learning. Also the expected result should specify to look at the list when typing "ph" or just "p".

Or if you know it's a fresh profile:
1) Click the location bar drop down and select the last result
2) Click the drop down and see that selected result as #1
Comment 48 Mike Beltzner [:beltzner, not reading bugmail] 2008-02-27 21:34:07 PST
Comment on attachment 306130 [details] [diff] [review]
v5.7

a1.9b4=beltzner
Comment 49 Stephen Donner [:stephend] 2008-02-27 23:05:58 PST
https://litmus.mozilla.org/show_test.cgi?id=5196, "Gotta-have-more-Litmus" edition

in-litmus+
Comment 50 Ed Lee :Mardak 2008-02-28 08:06:34 PST
Woohoo! Thanks everyone for waiting so patiently.

Checking in toolkit/components/places/src/nsNavHistory.h;
/cvsroot/mozilla/toolkit/components/places/src/nsNavHistory.h,v  <--  nsNavHistory.h
new revision: 1.146; previous revision: 1.145
done
Checking in toolkit/components/places/src/nsNavHistoryAutoComplete.cpp;
/cvsroot/mozilla/toolkit/components/places/src/nsNavHistoryAutoComplete.cpp,v  <--  nsNavHistoryAutoComplete.cpp
new revision: 1.46; previous revision: 1.45
done
RCS file: /cvsroot/mozilla/toolkit/components/places/tests/unit/test_adaptive.js,v
done
Checking in toolkit/components/places/tests/unit/test_adaptive.js;
/cvsroot/mozilla/toolkit/components/places/tests/unit/test_adaptive.js,v  <--  test_adaptive.js
initial revision: 1.1
done
Comment 51 Stephen Donner [:stephend] 2008-03-10 21:21:24 PDT
Verified FIXED using:

Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.4; en-US; rv:1.9b5pre) Gecko/2008031015 Minefield/3.0b5pre

Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9b5pre) Gecko/2008031004 Minefield/3.0b5pre

-and-

Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9b5pre) Gecko/2008031004 Minefield/3.0b5pre

Tested using https://litmus.mozilla.org/show_test.cgi?id=5196 and a hearty dose of daily trunk ad-hoc testing since checkin.

Note You need to log in before you can comment on or make changes to this bug.