Do You Like What I Like? Simple Probabilistic Scaling for Private MSN Similarity

TL;DR

Connecting with strangers in physical proximity is a basic human desire, but sharing personal tastes (like music) often compromises privacy. This paper presents a lightweight, serverless way for two smartphones to calculate how similar their owners' tastes are using Counting Bloom Filters (CBF). The surprising discovery? Using only one hash function provides the most accurate similarity estimation while minimizing memory—perfect for fast Bluetooth or NFC exchanges.

The "Frequency" Problem in Mobile Social Networks

Traditional Mobile Social Networks (MSNs) either rely on a central server (leaking your entire history) or simple Bloom Filters. The problem with standard Bloom Filters is that they are binary: they tell you if you like an artist, but not how much you like them. In social profiling, frequency is identity. If User A listens to Radiohead 1,000 times and User B listens once, they aren't truly "similar."

To bridge this gap, we need to compare multisets (sets where elements can appear multiple times). However, sending raw frequency lists is bandwidth-heavy and privacy-invasive.

Methodology: Reinventing Dice for Probabilistic Structures

The author proposes using Counting Bloom Filters (CBF) and Count-Min Sketches (CMS) to represent these musical multisets. The technical challenge is: how do you calculate similarity (like the Dice Coefficient) without "unpacking" the probabilistic structure?

The CBF-Dice Metric

The paper defines a new way to calculate the Dice Coefficient directly on the counters of a CBF:

$CBFext-Dice(P,Q)=\frac{2\cdot {\sum }_{i=1}^{n}min(p_i,q_i)}{{\sum }_{i=1}^n{p}_i+q_i}$

Where $p_i$ and $q_i$ are the counter values at index $i$. This effectively approximates the intersection of two multisets by looking at the overlap of their "collision buckets."

Fig 1. Visualization of a Counting Bloom Filter. Each index tracks the frequency of hashed elements.

The "Less is More" Paradox

In traditional database queries, more hash functions ($k$) lead to fewer false positives. However, this paper reveals a counter-intuitive reality for similarity estimation: Increasing $k$ actually increases the Root Mean Square Error (RMSE).

Why? Because every additional hash function populates more counters, increasing the global probability of collisions between different elements across the two users. When you are estimating the "total overlap," these extra collisions lead to a massive overestimation of similarity.

Fig 2. RMSE Comparison: Notice how the error climbs as the number of hash functions (k) increases.

Real-World Performance & Privacy

Using the Million Song Dataset, the author demonstrated that with an average of ~64 unique songs per user:

• A CBF of length 128 is sufficient for a "quick look."
• A CBF of length 400 provides high-fidelity estimation.
• No Underestimation: The nature of collisions means the similarity is either perfectly estimated or slightly overestimated.

From a privacy standpoint, this is a feature, not a bug. If two people have low similarity, the "noise" created by collisions makes it impossible for a malicious user to reverse-engineer exactly which songs the other person has been listening to.

Fig 3. Ground truth Dice (red) vs. CBF-Dice estimation (blue). The estimation tracks perfectly at higher similarity levels.

Critical Insight & Conclusion

This work shifts the focus of probabilistic data structures from "data retrieval" to "relationship estimation." For developers building decentralized apps (DApps) or proximity-based services, the takeaway is clear:

1. Use a single-hash CBF to preserve frequency data.
2. Size the filter to roughly twice the expected unique items.
3. Embrace the collision noise as a lightweight privacy layer.

By moving computation to the "edge" (the smartphones themselves), we can finally socialize in physical spaces without leaving a permanent digital footprint on a corporate server.