Smart most recently used algorithm

Question

Background

I need such an algorithm inside an android app (home launcher) to show the recently used apps. I want to avoid simple LRU / MRU logic by combining those logics (or use an alternative if anyone has a suggestion). I don't want an app that was started 100x before 10 weeks to stay on top until another app was started 100x and I don't want to only show the LRU apps on top. I want something that matches what a human would expect to see in the most recently used section.

Solution

I can of course save every app launch in a database (including its timestamp) and then give each launch a weight based on its age and then sum them up and calc an avarage value. That's a valid solution and would fit my needs. BUT it will grow the database indefinitely.

Question

Does anyone has an idea or does there exist an algorithm for such a problem already that does not depend on a full list of historical data (app launches in my case)? But instead does update values that belong to each app?

• Ainsley H.: You can look at Reddit's voting system, each open is a vote, votes decay over time.

Answer 1

I suggested looking at the Reddit ranking system in a comment, however, that system is made in such a way that the time of creation is what matters, and that's not really relevant in your scenario.

I therefore suggest a physics-based approach.

Model each app as a balloon (circular, in vacuum). Every time you open an app, it corresponds to hitting the balloon straight upwards (like a volleyball set hit), and when you're not hitting the balloon, it falls towards the earth. Once it hits the ground it can remain idle (or bump up a bit if you want to remind the user of apps they forgot about).

In order for an app to remain "hot" you need to keep it above ground.

So how to implement this?

We have a list of timestamps that maps days since epoch to the number of times it was opened that day. In the below sketch, I use a linear decay (gravity would of course be quadratic).

You need to experiment with the constants and try different functions (logarithms and polynomials) to get it to work to your likings.

Sketch

USAGE = { # map day to number of opens for that day
 "A": {0: 2, 1: 2, 2: 2, 3: 2, 4: 2},
 "B": {0: 10, 1: 0, 2: 0, 4: 0},
 "C": {0: 0, 1: 3, 2: 3, 4: 3},
 "D": {0: 0, 1: 0, 2: 0, 3: 5},
 "X": {0: 3, 1: 3, 2: 3, 3: 3, 4: 0},
 "Y": {0: 0, 1: 0, 2: 0, 3: 0, 4: 3},
 "Z": {0: 0, 1: 0, 2: 0, 3: 0, 4: 2},
}
IMPACT = 1.1
DECAY = 1.1
def rank_app(timemap, t):
 """Return the "height" of the balloon on day t given the timemap"""
 height = 0
 for day in range(t + 1):
 height += timemap.get(day, 0) ** IMPACT # impact of opening
 since = abs((t - day - 1))
 height = max(0, height - since ** DECAY) # decay
 return round(height, 1)
def rank(usage, day):
 """Return (heigh, app) for each app on given day t."""
 return sorted(
 [(rank_app(usage[app], day), app) for app in usage],
 reverse=True,
 )
print("\n".join([f"{e[0]} {e[1]}" for e in rank(USAGE, day=5)]))

... which gives

3.9 D
2.6 X
2.6 C
2.3 Y
2.3 A
1.1 Z
0.5 B

Notice that D is on top because it was visited 5 times yesterday. On the other hand, B was visited 10 times on Day 0, but hasn't been visited since, so it is on the bottom.

If you are worried about the space it takes to store all the timestamps, you can truncate the list at any point and replace with its height at a given day.

• prom85: I read about reddits algorithm for comments which is not depending on creation time and I like it very much (based on the wilson score interval). Nevertheless I like your suggestion very much as well and with small adjustments I can make it use linear memory only as you have already pointed it in your last sentence. Thinking about the physic based idea behind your algorithm I "feel" that your algorithm should give very good results. I will implement both algorithms in my app and test them. Thanks for the ideas.