Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Bounding the Fragmentation of B-Trees Subject to Batched Insertions
Michael A. Bender, Aaron Bernstein, Nairen Cao +5
The issue of internal fragmentation in data structures is a fundamental challenge in database design. A seminal result of Yao in this field shows that evenly splitting the leaves o…
cs.DS2025
Efficiently Constructing Sparse Navigable Graphs
Alex Conway, Laxman Dhulipala, Martin Farach-Colton +6
Graph-based nearest neighbor search methods have seen a surge of popularity in recent years, offering state-of-the-art performance across a wide variety of applications. Central to…
cs.DS2024
Faster Combinatorial k-Clique Algorithms
Amir Abboud, Nick Fischer, Yarin Shechter
Detecting if a graph contains a -Clique is one of the most fundamental problems in computer science. The asymptotically fastest algorithm runs in time , where i…