2019/08/17 by Magnus Lie Hetland, Hetland, Magnus Lie
Computer Science · #Advanced Database Systems and Queries #Constraint Satisfaction and Optimization #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Retrieval (cs.IR) #cs.DS #cs.IR
paper · pdf · doi:10.48550/arxiv.1908.06318
arxiv created 2019/08/17 · openalex publication_date 2019/08/17 · arxiv updated 2019/08/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Basic assumptions about comparison-based indexing are laid down and a general design space is derived from these. An index structure spanning this design space (the sprawl) is described, along with an associated family of partitioning predicates, or regions (the ambits), as well as algorithms for search and, to some extent, construction. The sprawl of ambits forms a unification and generalization of current indexing methods, and a jumping-off point for future designs.