Filtering 'Seen' Items in Recommendations
In feed and recommendation systems (like Tinder, TikTok, or Twitter), a critical requirement is ensuring users don't repeatedly see the same items. We need an efficient way to filter out items a user has already "seen."
Exact Sets (HashSets / Redis Sets)
The straightforward approach is to maintain an exact set of seen item IDs for every user. In Redis, you would use a Set (SADD user:123:seen item:456). Before showing an item, you check SISMEMBER.
Pros: 100% accurate. No false positives or false negatives.
Cons: Memory grows linearly. The raw payload for 100,000 eight-byte IDs is about 800 KB, but a Redis Set also pays object, hash-table, allocator, replication, and persistence overhead. Measure the actual representation before comparing it with a Bloom filter.
Bloom Filters
A Bloom Filter is a probabilistic data structure that is incredibly space-efficient. It tells you if an item is definitely not in the set, or possibly in the set.
- False Positives: It might say a user has seen an item when they haven't. In a recommendation system, this just means a valid item gets skipped. This is usually an acceptable product trade-off.
- False Negatives: It will never say a user hasn't seen an item if they actually have.
For 100,000 expected items and a 1% target false-positive rate, the optimal bit array is about 958,506 bits, or roughly 120 KB, before implementation metadata. That is much smaller than a typical exact Redis Set, whose entries cost far more than the raw eight-byte ID, but it is not only a few kilobytes. Exceeding planned capacity raises the false-positive rate, so monitor insert count and rotate or rebuild by time window.
Hybrid Approaches
Many systems use a hybrid approach based on time windows. They use an exact set (Redis) for the most recent session or the last 7 days (where accuracy matters most to avoid immediate repetition), and rely on a Bloom filter (or just drop filtering entirely) for historical interactions older than a month, assuming users forget or won't mind seeing very old content again.
Sizing formulas and a rotation example
For n items and target false-positive rate p, the optimal bit count is m = -n ln(p) / (ln 2)^2 and the number of hash functions is k = (m / n) ln 2. For n = 100,000 and p = 0.01, m is about 958,506 bits (about 117 KiB) and k is about 7. Halving p to 0.005 adds only about 1.44 bits per item.
Time-windowed rotation: keep an exact Redis set for the last 7 days of impressions (say 3,000 IDs per active user) and one Bloom filter per month for the previous six months, each sized for 15,000 items at 1 percent (about 18 KB each). A check probes the exact set, then each monthly filter; the combined false-positive rate is at most about 6 x 1 percent = 6 percent in the worst case, which you can lower by sizing older filters for 0.5 percent. Filters older than six months are simply dropped.
| Approach | Memory per 100k items | False positives | Deletion | Best for |
|---|---|---|---|---|
| Redis set of 8-byte IDs | Several MB in practice (object and hash overhead) | None | Yes | Recent, high-value history |
| Sorted set by timestamp | Larger than a plain set | None | Yes, by time range | Recent history with expiry |
| Bloom filter at 1 percent | About 120 KB | About 1 percent | No | Long history where skipping is harmless |
| Cuckoo filter | Similar to Bloom at low error rates | Tunable | Yes | History that must support un-see |
Real systems: RedisBloom provides BF.ADD and BF.EXISTS with scalable sub-filters; Medium has described using Bloom filters to avoid recommending already-read posts; dating apps apply the same idea to never re-show swiped profiles.