# Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring

arXiv: https://arxiv.org/abs/2004.05345 · HTML: https://mlsanity.com/paper/2004.05345/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Apr 2020.

## Built on by (most cited first, 11 of 11)

- [GCWSNet: Generalized Consistent Weighted Sampling for Scalable and Accurate Training of Neural Networks](https://mlsanity.com/paper/2201.02283/) (2022)
- [Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling](https://mlsanity.com/paper/2306.07674/) (2023)
- [HAKES: Scalable Vector Database for Embedding Search Service](https://mlsanity.com/paper/2505.12524/) (2025)
- [Very Efficient Listwise Multimodal Reranking for Long Documents](https://mlsanity.com/paper/2605.11864/) (2026)
- [SAH: Shifting-aware Asymmetric Hashing for Reverse k-Maximum Inner Product Search](https://mlsanity.com/paper/2211.12751/) (2022)
- [GEM: A Native Graph-based Index for Multi-Vector Retrieval](https://mlsanity.com/paper/2603.20336/) (2026)
- [LSH methods for data deduplication in a Wikipedia artificial dataset](https://mlsanity.com/paper/2112.11478/) (2021)
- [Pb-Hash: Partitioned b-bit Hashing](https://mlsanity.com/paper/2306.15944/) (2023)
- [From Zero to Hero: Detecting Leaked Data through Synthetic Data Injection and Model Querying](https://mlsanity.com/paper/2310.04145/) (2023)
- [Faster and Space Efficient Indexing for Locality Sensitive Hashing](https://mlsanity.com/paper/2503.06737/) (2025)
- [An Efficient Embedding Based Ad Retrieval with GPU-Powered Feature Interaction](https://mlsanity.com/paper/2511.22460/) (2025)

## Abstract (arXiv)

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.