  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 \emph{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.
