Comparison-Based Indexing From First Principles

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.

• Publication year

  2019

• Venue

  arXiv.org

• Publication date

  2019-08-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1908.06318
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Parameterized Algorithms

  2020influential reference
• Extending partial isometries of generalized metric spaces

  2015cited by this paper
• A Comprehensive Survey of Clustering Algorithms

  2015cited by this paper
• Encyclopedia of Distances

  2014cited by this paper
• On indexing metric spaces using cut-regions

  2014cited by this paper
• On Asymmetric Distances

  2013cited by this paper
• On quasihomomorphisms with noncommutative targets

  2013cited by this paper
• A Course in Model Theory

  2012cited by this paper
• The Multiplicative Weights Update Method: a Meta-Algorithm and Applications

  2012influential reference
• Metric Index: An efficient and scalable solution for precise and approximate similarity search

  2011cited by this paper
• Weak homomorphisms between functorial algebras

  2011cited by this paper
• The Scientific Papers of James Clerk Maxwell: On the Description of Oval Curves and those having a plurality of Foci; with remarks by Professor Forbes

  2011cited by this paper
• Probabilistic Metric Spaces

  2011cited by this paper
• The Design of Approximation Algorithms

  2011cited by this paper
• Boolean Functions: Theory, Algorithms, and Applications

  2011cited by this paper
• Indexing inexact proximity search with distance regression in pivot space

  2010cited by this paper
• On applications of parameterized hyperplane partitioning

  2010cited by this paper
• An Introduction to the Theory of Functional Equations and Inequalities

  2008influential reference
• A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs

  2008cited by this paper
• Unified framework for fast exact and approximate search in dissimilarity spaces

  2007cited by this paper
• A Survey of Clustering Data Mining Techniques

  2006cited by this paper
• Similarity Search: The Metric Space Approach (Advances in Database Systems)

  2005cited by this paper
• Pivoting M-tree: A Metric Access Method for Efficient Similarity Search

  2004cited by this paper
• An Access Structure for Similarity Search in Metric Spaces

  2004cited by this paper
• Index-driven similarity search in metric spaces (Survey Article)

  2003cited by this paper
• Indexing Schemes for Similarity Search: an Illustrated Paradigm

  2002cited by this paper
• Separable Splits of Metric Data Sets

  2001cited by this paper
• Searching in metric spaces

  2001cited by this paper
• Pivot selection techniques for proximity searching in metric spaces

  2001cited by this paper
• Directed Hypergraphs: Problems, Algorithmic Results, and a Novel Decremental Approach

  2001influential reference
• Dynamic spatial approximation trees

  2001cited by this paper
• A Course in Model Theory: An Introduction to Contemporary Mathematical Logic

  2000cited by this paper
• The soft heap: an approximate priority queue with optimal error rate

  2000cited by this paper
• Logic Programs, Well-Orderings, and Forward Chaining

  1999influential reference
• INTRODUCTION TO METRIC-PRESERVING FUNCTIONS

  1999cited by this paper
• Spaghettis: an array based algorithm for similarity queries in metric spaces

  1999cited by this paper
• Searching in metric spaces by spatial approximation

  1999cited by this paper
• A subset of metric preserving functions

  1998cited by this paper
• Excluded middle vantage point forests for nearest neighbor search

  1998cited by this paper
• A fast branch & bound nearest neighbour classifier in metric spaces

  1996cited by this paper
• Generalized Search Trees for Database Systems

  1995cited by this paper
• Near Neighbor Search in Large Metric Spaces

  1995cited by this paper
• Lectures on Polytopes

  1994cited by this paper
• A new version of the nearest-neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements

  1994cited by this paper
• Directed Hypergraphs and Applications

  1993cited by this paper
• An optimal convex hull algorithm in any fixed dimension

  1993cited by this paper
• Satisfying General Proximity/Similarity Queries with Metric Trees

  1991cited by this paper
• Multivariable Functional Interpolation and Adaptive Networks

  1988cited by this paper
• The theory of the egglipse—a new curve with three focal points

  1987cited by this paper
• ON METRIC PRESERVING FUNCTIONS

  1987cited by this paper
• An algorithm for finding nearest neighbours in (approximately) constant average time

  1986cited by this paper
• Fuzzy Set Theory - and Its Applications

  1985influential reference
• A Data Structure and an Algorithm for the Nearest Point Problem

  1983cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• A Generalization of Algebraic Surface Drawing

  1982cited by this paper
• Logic of Programs

  1981influential reference
• On a product of metric spaces

  1981cited by this paper
• The Design and Analysis of Computer Algorithms

  1974influential reference
• Time Bounds for Selection

  1973influential reference
• Metric spaces, generalized logic, and closed categories

  1973cited by this paper
• Organization and maintenance of large ordered indexes

  1972cited by this paper
• A mathematical introduction to logic

  1972cited by this paper
• L-fuzzy sets

  1967cited by this paper
• Model Theory: Third Edition (Dover Books On Mathematics) By C.C. Chang;H. Jerome Keisler;Mathematics

  1966cited by this paper
• De la puissance des ensembles parfaits de points

  1884cited by this paper
• Metric Spaces

  year unknowncited by this paper

• Fairest Neighbors: Tradeoffs Between Metric Queries

  2021cites this paper
• Metrics and Ambits and Sprawls, Oh My

  2020cites this paper