Comparison-Based Indexing From First Principles
This work provides a foundational framework for indexing methods, which could benefit researchers and practitioners in database systems and information retrieval, though it appears incremental as it builds on and unifies current approaches.
The paper tackles the problem of comparison-based indexing by establishing foundational assumptions and deriving a general design space, resulting in a unified index structure called the sprawl of ambits that generalizes existing methods and enables future designs.
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.