2020 · 30 citations · 33 references
ComputingComputer ScienceData MiningData StructuresDatabasesData CompressionData LocalityHash FunctionsHash TablesNearest Neighbor SearchSearching AlgorithmsBenchmark DatasetsDistance MetricsHashingHigh-dimensional Nearest Neighbor SearchIndex StructuresK-nearest Neighbor SearchLocality-sensitive HashingNearest Neighbor Data Structures
Locality-Sensitive Hashing (LSH) is one of the most popular methods for c-Approximate Nearest Neighbor Search (c-ANNS) in high-dimensional spaces. In this paper, we propose a novel LSH scheme based on the Longest Circular Co-Substring (LCCS) search framework (LCCS-LSH) with a theoretical guarantee. We introduce a novel concept of LCCS and a new data structure named Circular Shift Array (CSA) for k-LCCS search. The insight of LCCS search framework is that close data objects will have a longer LCCS than the far-apart ones with high probability. LCCS-LSH is LSH-family-independent, and it supports c-ANNS with different kinds of distance metrics. We also introduce a multi-probe version of LCCS-LSH and conduct extensive experiments over five real-life datasets. The experimental results demonstrate that LCCS-LSH outperforms state-of-the-art LSH schemes.
33
Piotr Indyk, Rajeev Motwani · 1998 · 4.2K citations · Full text
Similarity Search in High Dimensions via Hashing
Aristides Gionis, Piotr Indyk, Rajeev Motwani · 1999 · 3.1K citations
Locality-sensitive hashing scheme based on p-stable distributions
Mayur Datar, Nicole Immorlica, Piotr Indyk et al. · 2004 · 3K citations