Do You Like What I Like? Similarity Estimation In Proximity-based Mobile Social Networks

Abstract

While existing social networking services tend to connect people who know each other, people show a desire to also connect to yet unknown people in physical proximity. Existing research shows that people tend to connect to similar people. Utilizing technology in order to stimulate human interaction between strangers, we consider the scenario of two strangers meeting. On the example of similarity in musical taste, we develop a solution for the problem of similarity estimation in proximity-based mobile social networks. We show that a single exchange of a probabilistic data structure between two devices can closely estimate the similarity of two users - without the need to contact a third-party server.We introduce metrics for fast and space-efficient approximation of the Dice coefficient of two multisets - based on the comparison of two Counting Bloom Filters or two Count-Min Sketches. Our analysis shows that utilizing a single hash function minimizes the error when comparing these probab

Stats

• citations8
• S2 citations—
• github stars0
• HF likes0
• heat score7.16
• arxiv keybeierle2018do

Related papers

• When Hashes Met Wedges: A Distributed Algorithm For Finding High Similarity Vectors (2017)5.84
• The Importance Of Being Dissimilar In Recommendation (2018)4.52
• Unconventional Application Of K-means For Distributed Approximate Similarity Search (2022)5.84
• Simisketch: Efficiently Estimating Similarity Of Streaming Multisets (2024)0.00
• Sparse Online Relative Similarity Learning (2021)2.26
• A New Family Of Near-metrics For Universal Similarity (2017)0.00
• Needle In A Haystack, Fast: Benchmarking Image Perceptual Similarity Metrics At Scale (2022)0.00
• Efficient Similarity Search In Dynamic Data Streams (2016)0.00