The field of querying and indexing is moving towards more efficient and scalable solutions. Recent developments have focused on improving the performance of various query types, such as nearest neighbor searches, rank aggregation, and approximate maximum inner product search. Notably, graph-based methods have shown promise in achieving superior efficiency and accuracy. Additionally, there is a growing interest in designing dynamic and self-balancing data structures, such as k-d trees, to support efficient insertion and deletion operations. Overall, the field is advancing towards more efficient, scalable, and robust querying and indexing techniques. Noteworthy papers include Efficient Computation of Trip-based Group Nearest Neighbor Queries, which proposes a novel query type and efficient computation techniques, and SINDI, which introduces an efficient index for approximate maximum inner product search on sparse vectors. Another notable paper is BAMG, which proposes a block-aware monotonic graph index for disk-based approximate nearest neighbor search, achieving up to 2.1x higher throughput and reducing I/O reads by up to 52% compared to state-of-the-art methods.
Advances in Efficient Querying and Indexing
Sources
Efficient Computation of Trip-based Group Nearest Neighbor Queries (Full Version)
Generalised M\"obius Categories and Convolution Kleene Algebras
BPI: A Novel Efficient and Reliable Search Structure for Hybrid Storage Blockchain
How to Compute a Moving Sum
CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search
Near-Duplicate Text Alignment under Weighted Jaccard Similarity
Computational Exploration of Finite Semigroupoids
Diverse Unionable Tuple Search: Novelty-Driven Discovery in Data Lakes [Technical Report]
Efficient Dynamic Rank Aggregation
BAMG: A Block-Aware Monotonic Graph Index for Disk-Based Approximate Nearest Neighbor Search
Compressed Dictionary Matching on Run-Length Encoded Strings
LayoutGKN: Graph Similarity Learning of Floor Plans
Toward Efficient and Scalable Design of In-Memory Graph-Based Vector Search
DISTRIBUTEDANN: Efficient Scaling of a Single DISKANN Graph Across Thousands of Computers
Engineering Select Support for Hybrid Bitvectors
A Dynamic, Self-balancing k-d Tree
SINDI: an Efficient Index for Approximate Maximum Inner Product Search on Sparse Vectors
Data Skeleton Learning: Scalable Active Clustering with Sparse Graph Structures