Journal
WSDM'18: PROCEEDINGS OF THE ELEVENTH ACM INTERNATIONAL CONFERENCE ON WEB SEARCH AND DATA MINING
Volume -, Issue -, Pages 72-80Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3159652.3159694
Keywords
locality sensitive hashing; dynamic data streams; Jaccard index
Categories
Funding
- Deutsche Forschungsgemeinschaft within the Collaborative Research Center SFB 876
- Google Focused Award on Web Algorithmics for Large-scale Data Analysis
- Microsoft Azure for Research Award (Online Event Detection and Evolution Tracking in Activity Networks)
Ask authors/readers for more resources
Recommender systems are an integral part of many web applications. With increasingly larger user bases, scalability has become an important issue. Many of the most scalable algorithms with respect to both space and running times are based on locality-sensitive hashing (LSH). However, a significant drawback is that these methods are only able to handle insertions to user profiles and tend to perform poorly when items may be removed. We initiate the study of scalable locality-sensitive hashing for dynamic input. Specifically, using the Jaccard index as similarity measure, we design (1) a sketching algorithm for similarity estimation via a black box reduction to l(0) norm estimation and (2) a locality sensitive hashing scheme maintainable in fully dynamic data streams that quickly filters out low-similarity pairs. Our algorithms have little to no overhead in terms of running time compared to previous LSH approaches for the insertion only case, and drastically outperform previous algorithms in case of deletions.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available