Aarhus University Seal

Similarity Search for Dynamic Data Streams

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Marc Bury, TU Dortmund, Germany
  • Chris Schwiegelshohn
  • Mara Sorella, University of Rome La Sapienza, Italy
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.
Original languageEnglish
JournalIEEE Transactions on Knowledge and Data Engineering
Pages (from-to)2241-2253
Number of pages13
Publication statusPublished - Nov 2020
Externally publishedYes

    Research areas

  • Dynamic streaming, locality-sensitive hashing, nearest neighbor searching

See relations at Aarhus University Citationformats

ID: 207576251