Clustered Hierarchical Entropy-scaling Search Of Astronomical And Biological Data

Abstract

Both astronomy and biology are experiencing explosive growth of data, resulting in a "big data" problem that stands in the way of a "big data" opportunity for discovery. One common question asked of such data is that of approximate search (\(\rho-\)nearest neighbors search). We present a hierarchical search algorithm for such data sets that takes advantage of particular geometric properties apparent in both astronomical and biological data sets, namely the metric entropy and fractal dimensionality of the data. We present CHESS (Clustered Hierarchical Entropy-Scaling Search), a search tool with virtually no loss in specificity or sensitivity, demonstrating a \(13.6\times\) speedup over linear search on the Sloan Digital Sky Survey's APOGEE data set and a \(68\times\) speedup on the GreenGenes 16S metagenomic data set, as well as asymptotically fewer distance comparisons on APOGEE when compared to the FALCONN locality-sensitive hashing library. CHESS demonstrates an asymptotic complexity

Stats

• citations4
• S2 citations—
• github stars0
• HF likes0
• heat score5.24
• arxiv keyishaq2019clustered

Related papers

• Let Them Have CAKES: A Cutting-edge Algorithm For Scalable, Efficient, And Exact Search On Big Data (2023)2.68
• Hierarchical Locality Sensitive Hashing For Structured Data: A Survey (2022)0.00
• Hd-index: Pushing The Scalability-accuracy Boundary For Approximate Knn Search In High-dimensional Spaces (2018)14.02
• Climber++: Pivot-based Approximate Similarity Search Over Big Data Series (2024)2.26
• PECANN: Parallel Efficient Clustering With Graph-based Approximate Nearest Neighbor Search (2023)0.00
• A Memory-efficient Distributed Algorithm For Approximate Nearest Neighbour Search With Arbitrary Distances (2024)0.00
• Improving Similarity Search With High-dimensional Locality-sensitive Hashing (2018)0.00
• Accelerating Large-scale Graph-based Nearest Neighbor Search On A Computational Storage Platform (2022)11.29