2023/09/11 by Morgan E. Prior, Prior, Morgan E., Thomas J. Howard +8
Computer Science · #68P05 #68P10 #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #E.1 #F.2.1 #FOS: Computer and information sciences #H.3.3
paper · pdf · doi:10.48550/arxiv.2309.05491
openalex publication_date 2023/09/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The ongoing Big Data explosion has created a demand for efficient and scalable algorithms for similarity search. Most recent work has focused on approximate k-NN search, and while this may be sufficient for some applications, exact k-NN search would be ideal for many applications. We present CAKES, a set of three novel, exact algorithms for k-NN search. CAKES's algorithms are generic over any distance function, and they do not scale with the cardinality or embedding dimension of the dataset, but rather with its metric entropy and fractal dimension. We test these claims on datasets from the ANN-Benchmarks suite under commonly-used distance functions, as well as on a genomic dataset with Levenshtein distance and a radio-frequency dataset with Dynamic Time Warping distance. We demonstrate that CAKES exhibits near-constant scaling with cardinality on data conforming to the manifold hypothesis, and has perfect recall on data in metric spaces. We also demonstrate that CAKES exhibits significantly higher recall than state-of-the-art k-NN search algorithms when the distance function is not a metric. Additionally, we show that indexing and tuning time for CAKES is an order of magnitude, or more, faster than state-of-the-art approaches. We conclude that CAKES is a highly efficient and scalable algorithm for exact k-NN search on Big Data. We provide a Rust implementation of CAKES under an MIT license at https://github.com/URI-ABD/clam