Similarity Search for Dynamic Data Streams

Marc Bury, Chris Schwiegelshohn, Mara SorellaIEEE TKDE 2020 · OpenReview

TL;DR

This paper introduces the first scalable locality-sensitive hashing (LSH) algorithms for dynamic data streams, capable of handling both insertions and deletions of user data. Their approach significantly outperforms existing methods when dealing with data removals, making it more practical for real-world applications where data is constantly changing.

What Problem Does This Paper Address?

Nearest neighbor search is crucial for many applications like recommender systems and pattern recognition. Traditional LSH methods, particularly min-hashing, are efficient for static datasets and handle insertions well. However, they struggle when items are removed from user profiles, a common occurrence in dynamic environments (e.g., users unliking items, unfollowing accounts). Recomputing LSH structures after deletions is computationally prohibitive. This paper addresses the critical need for LSH techniques that can efficiently manage dynamic data streams with both additions and removals, maintaining scalability and accuracy.

Methods

The authors propose a novel LSH scheme for dynamic data streams, primarily focusing on the Jaccard similarity. Their approach involves:

  • Sketching Algorithm: They develop a sketching mechanism that approximates the Jaccard similarity (or its induced distance) within a (1 ± ε) factor using a small amount of space per user (polylogarithmic in the number of users and items). This is achieved by leveraging techniques similar to $\ell_0$ sketches and bit-sampling.
  • Locality-Sensitive Hashing for Dynamic Streams: They design an LSH algorithm that, unlike previous methods, can handle deletions. This is accomplished by using a combination of cardinality-based filtering and a novel small-space item sampling technique. This sampling method uses a nested hashing approach to maintain multiple samples for different similarity thresholds, allowing for efficient updates and queries.
  • Selective Recomputation: For deletions, their algorithm intelligently recomputes signatures only for "sensitive" buckets, avoiding costly full recomputations.

Datasets

  • Synthetic Dataset: A large binary data matrix (10,000 rows, up to 1,000,000 columns) with varying sparsity (1%-5% non-zero entries) was used. To simulate real-world scenarios, specific pairs of rows were created with higher Jaccard similarities. Both insertion-only and fully dynamic stream scenarios were tested.
  • Last.fm Dataset: A real-world dataset containing temporal listening histories of 44,154 users, spanning 5 years, with 721 million listening events and 4.6 million unique tracks. This dataset was processed to create user profiles based on artists and genres, resulting in a sparse dataset of 15,000 users and 380,000 items.

Key Insights and Ideas

  • Deletions are the Bottleneck: The core challenge in dynamic LSH is efficiently handling item removals. Existing methods are ill-equipped for this, requiring expensive recomputations.
  • Sketching for Efficiency: Using sketching techniques allows for a compact representation of user profiles, enabling efficient similarity estimation and filtering in dynamic streams.
  • Dynamic LSH is Achievable: The paper demonstrates that LSH can be effectively adapted for dynamic data streams, offering a practical solution for applications with evolving data.
  • Trade-offs in Parameters: The performance (accuracy and speed) is sensitive to parameter choices like α (inverse sampling rate) and c² (number of buckets), requiring careful tuning.

Key Results

  • Drastic Improvement with Deletions: The proposed algorithm drastically outperforms previous LSH approaches in the presence of deletions, with running times significantly lower. For instance, in the fully dynamic stream scenario, their algorithm is orders of magnitude faster than a "vanilla" min-hashing approach.
  • Competitive Performance for Insertions: For insertion-only streams, their algorithm shows comparable running times to existing methods.
  • Scalability: The algorithm uses a small amount of space per user (O(log|U|) bits for sketches) and achieves constant update and query times (O(1)).
  • Approximation Quality: The algorithm provides a (1 ± ε) approximation to Jaccard similarity and achieves good filtering behavior, with low false positive rates and high recall, especially with appropriate parameter tuning. For example, on the Last.fm dataset, they achieved over 90% filtering with a low false positive rate.

Limitations and Future Work

  • Parameter Tuning: The performance is sensitive to parameter choices (α, c²), and finding optimal values might require experimentation.
  • Theoretical Bounds vs. Practical Performance: While theoretical bounds are provided, the paper notes that practical performance can be good even with parameters below theoretical thresholds.
  • Extension to Other Similarities: The authors suggest extending their techniques to other similarity measures that admit LSH, particularly those relevant to collaborative filtering.
  • Real-world Applicability: The successful application to the Last.fm dataset suggests the algorithm's viability for real-world recommendation systems.

Summary updated

Abstract

Nearest neighbor searching systems are an integral part of many online applications, including but not limited to pattern recognition, plagiarism detection, and recommender systems. With increasingly larger data sets, scalability has become an important issue. Many of the most space and running time efficient algorithms are based on locality-sensitive hashing. Here, we view the data set as an n by lUl matrix where each row corresponds to one of n users and the columns correspond to items drawn from a universe U. The de-facto standard approach to quickly answer nearest neighbor queries on such a data set is usually a form of min-hashing. Not only is min-hashing very fast, but it is also space efficient and can be implemented in many computational models aimed at dealing with large data sets such as MapReduce and streaming. However, a significant drawback is that minhashing and related 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 (LSH) for fully dynamic data-streams. Specifically, using the Jaccard index as similarity measure, we design (1) a collaborative filtering mechanism maintainable in dynamic data streams and (2) a sketching algorithm for similarity estimation. Our algorithms have little 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.
BibTeX
@article{bury2020similarity,
  author = {Marc Bury and Chris Schwiegelshohn and Mara Sorella},
  title = {{Similarity Search for Dynamic Data Streams}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2020},
  url = {https://openreview.net/forum?id=mFE-DhRu8BQ},
}
Figure