feat(service): prefer recently/often used applications in search

[truprecht]

This PR was intended to address #22, but as of writing this I noticed that I might have misunderstood is issue: with this PR, the order of the search results is altered, so that recently or often used applications are listed higher than matches that are rarely used. It does not affect the order of the active windows in the list of results. Anyways, I am certain that the implemented mechanism is still useful and can easily be extended to reorder the active window entries.

There are the following additions:

• The struct RecentUseStorage is a part of the Service and keeps track how often applications are called from the launcher in total (called long term storage) and which applications were called recently (called short term storage).
• When two search results are compared, two constants are added to the Jaro-Winkler-similarity to the item that was used more recently or more frequently, respectively. So those items will appear at a more favorable position in the search results. This comparison is implemented in a new struct Priority that keeps all relevant data needed for the ordering, including the plugin priority.
• The long term storage of RecentUseStorage is serialized and stored in the cache dir. The short term storage is freshly initialized on each startup. I still feel quite unsure about the serialization into the cache file, which is called with each Activate/ActivateContext request. Maybe there is some more elegant solution?

[jacobgkau]

I'm currently testing with Firefox and LibreWolf, searching for "web browser".

This is definitely working for often-used. I'm not sure the recently-used factor is currently working. For example, if I launch Firefox 10 times so its count in the cache file is 10 higher than LibreWolf, then switch to launching LibreWolf, LibreWolf stays second in the search results all ten launches, not surpassing Firefox until its number in the cache file is higher. Is this expected behavior? Lines 27-28 in priority.rs sound like recency should be twice as important as number of launches.

[truprecht]

You are completely right, that didn't work properly. The cache for recently used apps was wiped on each start of the service, and the service is restarted with the front end. So that was kinda pointless as only the serialized cache of often-used apps was considered. The last commit also serializes the recently used apps, now it should work.

[jacobgkau]

recently-used is working. It seems to have a much higher weight than often-used; if Firefox has been launched 100 times and LibreWolf has only been launched 1 time, selecting LibreWolf once (bringing its count up to two) makes it return first in the search results next time. The behavior seems desirable overall right now, but I wanted to double-check that's working as it should as well (since the 0.2 and 0.1 values made it seem like we still wanted to consider often-used when factoring in recently-used, rather than entirely overriding it.)

Another thing about this implementation is that not being query-specific combined with having a limited number of items in the recently-used list results in unrelated searches affecting each others' results: in the above scenario, LibreWolf returns first if I search web browser; but after searching calc and launching Calculator 20 times, LibreWolf is knocked out of the recently-used list and Firefox shows up first again for web browser. It's an improvement over no learning, to be clear, but maybe something to consider.

[mmstick]

I think we could better results if we limit the maximum value of the long-term search result. A person's trends can change from day to day, or week to week. Best not to allow the long term value to get too high.

[mmstick]

Perhaps also a means of automatically decreasing long term values over time. Maybe if we store a generation for each increment and automatically remove the oldest votes.

[truprecht]

@jacobgkau, yes it works as I intended. Recently used does not override often used, but it just adds a higher value to the compared score. So if you're comparing ≥3 search results, you hopefully end up with the most recent at the top, followed by the not so recent but often used, etc.

Thank you both for your sugestions. I got some rough ideas to tackle them, maybe you could tell me which are closest to your vision how this should work, or you could add some of your own:

• Recently used apps are stored at most once: Already presnt entries are not added again but shifted to the front of the list.
• The long-term storage is trimmed at some point. We could define some upper limit (e.g. the maximum value or the sum of all values in the map) which triggers this operation. I'd propose to divide all values by 2 an throw out all entries with value <1.
• The short and long-term caches are merged into one, storing the frequency as well as the recency for a fixed but rahter large number of activations. Old entries are removed from both metrics at the same time.

[mmstick]

Any updates on the progress of this?

[jacobgkau]

The behavior I noted before is still the case-- if Firefox has been launched 100 times, all it takes is launching LibreWolf once for it to appear above Firefox in the results. So we're basically sorting by recently used.

If I open up 20 other apps (so neither Firefox nor LibreWolf are in the recents list), then search for "web browser" again, then Firefox does show up first; and if I swap the numbers so LibreWolf has been launched 100 times and Firefox only once, then Librewolf shows up first. So often-used (which might be more accurately described as "most-used," since there's no time measurement being factored in to obtain a sense of "often") takes effect if none of the apps have been used recently.

While testing this, I did see that when searching for web browser, Cheese starts to show up before actual web browsers (including Firefox, which has "Web Browser" in its display name) if it's been recently launched.

The Cheese .desktop file contains the word "webcam" in its comment and keywords, but not plain "web" or "browser." I think this would be an example of an unintended side effect of the sorting.

[jacobgkau]

I just had Audacity show up as the first result when searching for gedit on this branch as well. Audacity's generic name is Sound Editor and it has some g characters in its keywords.

It seems either recently used is being given too much weight over normal result sorting, or it's exposing shortcomings in the normal result sorting. Either way, I think some improvement is needed so as not to regress searching so heavily.

[truprecht]

Sorry, I took a long break. I'll definitely check and fine-tune the weights in the coming days. @jacobgkau, could you please elaborate your expectation about the handling of recent and much used apps? Right now, the last 20 apps are preferred even over apps that were heavily used in the past, and you seem discontent with that. Would you expect some kind of trade-off between recent and most-used?

[mmstick]

@truprecht In general, searching gedit should always have gedit as the top search result. There should be a higher priority for exact binary name matches.

[jacobgkau]

Yeah, I don't have a strong opinion on recently used vs. heavily used. The issue preventing this from being accepted at this moment is recently used vs. normal search results/exact matching. Search terms still need to effectively filter out irrelevant results (and bring the closest match to the top) even with apps having recently used weights.

The use case for recently used is more for when a user just types a character or two and there are still lots of potentially relevant results.

[truprecht]

The recent commit limits the scores of all non-exact matches below any exact match. It also tunes the score bonuses so that they are in sum less than 0.1, which is the bonus for a match in the name vs in the description or keywords. That should resolve both of your complaints.

[jacobgkau]

78a69f9 builds locally, but it failed to build on the build server:

14:51:23 E: Package build dependencies not satisfied; skipping
14:51:23 launcher: 78a69f901e030d90c1c20435ca92fcba67033d29 (testing-launcher-pr132): jammy (22.04): amd64: binary failed: exit status: 3
14:51:23 launcher: 78a69f901e030d90c1c20435ca92fcba67033d29 (testing-launcher-pr132): jammy (22.04): binary-amd64 github status failure

Not sure why this happened.

[mmstick]

Temporary connection loss

Err:42 http://archive.ubuntu.com/ubuntu jammy/universe amd64 libpkgconf3 amd64 1.8.0-1
  Connection timed out [IP: 91.189.91.38 80]
E: Failed to fetch http://archive.ubuntu.com/ubuntu/pool/universe/p/pkgconf/libpkgconf3_1.8.0-1_amd64.deb  Connection timed out [IP: 91.189.91.38 80]

[jacobgkau]

Just force-pushing an amend with no changes to force this to build again.

[mmstick]

I missed this getting approved. It's good to me.