Pith. sign in

REVIEW 2 major objections 3 minor 71 references

Comparison-Based Indexing From First Principles

T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A single formal object — the sprawl — exactly captures every monotone comparison-based index traversal.

desk verdict Genuinely useful unification of comparison-based indexing, but the central representation theorem has a real gap for infinite workloads that needs fixing before the paper's strongest claims hold. read the letter →

arxiv 1908.06318 v1 pith:2KY7AKIB submitted 2019-08-17 cs.DS cs.IR

Magnus Lie Hetland This is my paper · ORCID
classification cs.DScs.IR MSC 68P0568P2005C65
keywords comparison-basedindexingmetrictraversalrepertoiresprawlambitsimilaritysearchdirectedhypergraphregionlabeling
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper derives the design space of comparison-based indexing from a small set of axioms about how a search can explore a ground set. Its central theorem states that any monotone traversal scheme — a family of exploration languages indexed by queries, satisfying the monotonicity axiom that narrowing a query never opens new nodes — is exactly the traversal scheme of a sprawl, and vice versa. This means that search trees, metric pivot methods, and other exact comparison-based indexes can all be described and compared in one formal structure. The paper then introduces the ambit, a general region type defined as the preimage of a ball under a structure-preserving remoteness map, which specializes to balls, shells, planes, ellipses, Voronoi cells, and cut regions. If the theorem holds, index design becomes a matter of choosing a sprawl and its region family rather than inventing a new structure from scratch.

What carries the argument

The central object is the sprawl, a finite directed hypergraph $\langle V,E,P,N\rangle$ over a ground set $V$, with each hyperedge $e$ labeled by a family $P(e)$ of positive regions and a family $N(e)$ of negative regions; the traversal algorithm activates an edge once all its sources are traversed and then consults region–query intersections to discover or eliminate the edge's target. The companion object is the traversal repertoire, a language of node sequences satisfying axioms T1–T4 (non-emptiness, simplicity, heredity, and the interval property), which Theorem 2.1.5 shows to be exactly the repertoires of signed directed hypergraphs. The machinery that converts repertoires into sprawls is Construction A.1, which adds maximal-query complement sets as regions; monotonicity axiom T5 then guarantees that these regions behave correctly under query inclusion. For the region side, the ambit is the preimage of a ball in a target structure, $B[p,r;f] = C[p,\{x : f(x) \leq r\}]$, where $f$ is a structure-preserving remoteness map on comparison features; linear ambits yield overlap checks such as $r+s \geq aZc^t$ in quasimetric spaces.

What would settle it

For a small finite universe, enumerate every workload and monotone traversal scheme satisfying T1–T5, apply Construction A.1 to build the corresponding sprawl, and check that resolving the sprawl on each query reproduces the original traversal repertoire; any mismatch falsifies Theorem 2.2.4. A more targeted check: find a scheme with monotone languages whose feasible-continuation sets cannot be expressed as "query intersects all positive regions and misses at least one negative region" for any choice of region families.

Watch

Extended reading notes

Core claim

The load-bearing equivalence is Theorem 2.2.4: for any workload in a universe, a family of traversal languages is a monotone traversal scheme if and only if it is the traversal scheme of some sprawl. A sprawl is a directed hypergraph whose edges carry positive and negative region labels: an edge becomes active once its sources are traversed, and a query then triggers discovery of the edge's target if the query intersects every positive region, or elimination if it misses some negative region. Given a monotone scheme, the construction in Appendix A builds the regions from maximal queries that would block discovery or cause elimination, and the monotonicity axiom is exactly what lets arbitrary edge predicates be replaced by region intersection. The converse direction shows that any sprawl yields a monotone scheme because enlarging a query can only add positive edges and remove negative ones. In the paper's own words, "the sprawl exactly maps out the design space of monotone traversal schemes."

Load-bearing premise

The load-bearing premise is monotonicity: narrowing a query must never make additional nodes available, and if that fails — as with k-nearest-neighbor queries whose radius shrinks during search — the paper's exact equivalence between traversal schemes and sprawls is not proven.

Editorial extensions

If this is right

  • Every existing exact comparison-based index that satisfies monotonicity can be emulated as a sprawl, so correctness and pruning arguments can be stated once in the shared framework.
  • New index designs can be specified by a monotone traversal scheme and mechanically converted to a sprawl via Construction A.1, then implemented with any suitable region family.
  • The ambit family subsumes balls, spheres, shells, planes, ellipses, hyperbolas, Voronoi cells, and cut regions, so the same overlap machinery applies across metric indexing methods.
  • Existing metric structures can be queried by ambits, not just single objects, supporting weighted multi-object queries with negative contrast weights.
  • For responsible and acyclic sprawls, correctness can be checked locally through region responsibility axioms L1–L3, which is how most practical indexes avoid the general coNP-complete correctness problem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the representation theorem rests on monotonicity, dropping T5 — for example to model k-nearest-neighbor queries whose description shrinks during search — opens a distinct design space the paper only sketches; one concrete extension would be sprawls with query-dependent edge activation updated as the query bound tightens.
  • The sprawl normal form suggests a programmatic search over designs: enumerate monotone traversal schemes or region families and rank them by expected overlap probability, turning the qualitative unification into a quantitative design tool.
  • The ambit query modality could be tested directly by wrapping an existing metric index and issuing weighted polyellipse-style queries, comparing precision and pruning against standard ball queries; the paper reports preliminary experiments but not definitive benchmarks.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper develops an axiomatic foundation for comparison-based indexing. It starts from traversal axioms T1–T4 and a monotonicity axiom T5, and proves that the resulting monotone traversal schemes are exactly the traversal schemes of a new data structure, the sprawl (Theorem 2.2.4). It then introduces the ambit family of regions, derives linear and nonlinear overlap conditions, gives optimization procedures for ambit coefficients and focus selection, and provides complexity results for sprawl correctness and focus selection. The paper also shows how classical index structures and regions—trees, AESA, PM-tree, balls, shells, planes, ellipses, and similar objects—arise as special cases of the framework.

Significance. If the central representation theorem is made fully rigorous, this paper offers a genuinely useful unification: it reduces a heterogeneous family of index structures to a single design space and gives explicit constructions plus a route for inventing new structures. The overlap checks in Section 3.1 and the complexity reductions in Sections 2.3 and 3.4 are valuable contributions in their own right. The central results are derived from axioms rather than fitted to data, and the optimization sections are explicitly presented as construction heuristics, which is a strength. The paper is also appropriately cautious about empirical claims, describing experiments as preliminary in Section 4. However, the main representation theorem has a nontrivial proof gap for infinite workloads, and the formal construction is in tension with the paper's 'fully implementable' claim.

major comments (2)
  1. [Appendix A, Construction A.1 / Theorem 2.2.4] The direction (i)⇒(ii) of Theorem 2.2.4 constructs P(e) and N(e) from the 'maximal queries' of certain families, but such maximal elements need not exist for infinite workloads. For example, take U=N, V={0,1}, workload {Q_n={0,...,n}: n∈N}∪{N}; let L_N be all simple sequences over V and let L_Qn={ε,⟨1⟩}. This is a monotone traversal scheme. The edge ∅→0 is positive only for the query N, so the bad queries for this edge are exactly the Q_n, which form an infinite ascending chain with no maximal element; Construction A.1 therefore cannot define P(e) for this edge. The proof's Case 2 ('Let Q_j be a maximal query...') has no object to pick. The gap is repairable by using all bad queries rather than only maximal ones, but then the resulting labels are typically infinite, which raises a separate implementability problem.
  2. [Section 1 and Section 2.4] The introduction describes the sprawl as a 'fully general yet fully implementable' index, but Section 2.4 admits that the formal construction steps 'will generally produce an infinite number of regions,' and the repair of Construction A.1 described above can require infinite P(e)/N(e) labels. This is not merely a wording issue: Definition 2.0.1 distinguishes a 'finite sprawl' by finiteness of its labels, and finite labels are what an implementation can store. The paper needs either to restrict the main equivalence to workloads for which the construction yields finite labels, or to give an explicit finite representation of the infinite region families and revise the implementability claim accordingly.
minor comments (3)
  1. [Section 3.3.2, proof of Proposition 3.3.2] The displayed inequality '|ui−vi| < ui + ui' appears to be a typo; it should presumably read '|ui−vi| < ui + vi'. As printed, the inequality is incorrect and the surrounding argument is harder to follow.
  2. [Section 2.0.4] The discussion of kNN queries is only a sketch: it says the query description could be updated during search, but this is not integrated into the formal definitions or into Theorem 2.2.4. The paper should state explicitly that the formal results apply to fixed, formally described query sets, and that evolving kNN-style queries are an informal extension.
  3. [Appendix A, Observation A.2] There is a typo in the first sentence of the proof: 'than' should be 'then'. More importantly, the sentence 'If σj(τ~,x) = −1, than any traversal τ that is an ordering of τ~ will result in the elimination of x' should be expanded slightly, because the traversal order independence of elimination is exactly what is being used.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 2.2.4 is a constructive equivalence proved from axioms T1-T5, and the optimization heuristics are not presented as predictions.

full rationale

The paper's central claim is a representation theorem, not a circular derivation. Construction A.1 starts from a given monotone traversal scheme and builds a sprawl by defining each edge's positive and negative regions as complements of the maximal queries that would suppress or negate that edge; the Appendix A proof then verifies, case by case, that the sprawl's traversal scheme coincides with the original scheme. Monotonicity (T5) is exactly the property that makes this encoding possible, and the converse direction is checked rather than assumed, so the equivalence is not true by definition. No fitted parameter is renamed as a prediction: the linear programs in Sect. 3.3 optimize ambit coefficients and radii as construction heuristics, and the paper explicitly describes the objective as a heuristic proxy for overlap probability. The only self-citation, [26] for estimating E[z] from training queries, is incidental to the central equivalence and does not carry a load-bearing theorem. One genuine concern is a completeness gap: Construction A.1 quantifies over 'maximal queries,' which need not exist for infinite workloads (e.g., an ascending chain of finite queries has no maximal element), so Theorem 2.2.4 is not fully established in the stated generality. That is a mathematical correctness issue, not circularity; it does not involve fitting inputs, self-referential definitions, or a conclusion identical to an assumption.

Assumptions & free parameters 7 free parameters · 6 assumptions · 3 invented entities

The central equivalence theorem rests on the explicitly stated traversal and monotonicity axioms, plus standard model-theoretic facts. The ambit construction introduces free parameters (foci, remoteness map, radius, facet count, transform parameters) that are chosen by the designer or fit to data, but these do not affect the main representation theorem. The introduced entities are formally defined structures with proofs and are not ungrounded postulates.

free parameters (7)
  • number of foci m = chosen by designer
    The ambit degree m (Def 3.0.1) is a free design parameter; Sect 3.4 studies optimal focus selection when m is not fixed.
  • linear ambit coefficients a (matrix A) = optimized via LP (3.10) or convex hull (3.3.1)
    Coefficients are fit to responsibility feature vectors and training queries to maximize expected filtering, not derived from first principles.
  • radius r = optimized together with a in (3.10) or (3.12a)
    The radius is part of the fitted ambit definition.
  • number of facets k = heuristic choice
    The clustering heuristic in Sect 3.3 selects k facets; k is a free parameter.
  • power transform exponent alpha = tunable, e.g., via heuristic optimization
    In (3.13), alpha in [0,1] controls blobbiness; the paper suggests optimizing it but provides no fixed value.
  • metaball parameters a_i, b_i = tunable
    In (3.14), a_i, b_i > 0 are free parameters of the metaball remoteness map.
  • foci p1..pm = selected from data (Sect 3.4)
    Focus selection is a free choice; the paper proves approximating the optimal choice is W[2]-hard.
assumptions (6)
  • domain assumption Traversal axioms T1-T4 (non-emptiness, simplicity, heredity, interval property)
    Def 1.2.7 assumes any comparison-based index traversal satisfies these axioms, e.g., nodes visited once and availability depends only on the set of traversed nodes.
  • domain assumption Monotonicity axiom T5
    Def 1.2.10 assumes narrowing the query does not make more nodes available; this is the key premise enabling representation by region intersection in Theorem 2.2.4.
  • domain assumption Atomistic workload for local characterization
    Obs 2.3.10 assumes queries are singleton sets; the local L1-L3 characterization of responsibility depends on it.
  • domain assumption Quasimetric triangle inequality
    Sect 3.1 uses the oriented triangle inequality (3.4) to derive the linear ambit overlap check (Theorem 3.1.2).
  • standard math Model-theoretic preservation theorems
    Theorem 3.6.1 relies on preservation results from Hodges [36]: Horn theories preserved by products, existential formulas by embeddings, positive existential by homomorphisms.
  • domain assumption Comparison function delta is given as a black box
    The paper assumes access to a comparison oracle delta (Def 1.2.2) and does not model its computational cost.
invented entities (3)
  • Sprawl independent evidence
    purpose: A region-labeled directed hyperdigraph representing any monotone traversal scheme; the central unifying index structure.
    Def 2.0.1 defines it constructively, and Theorem 2.2.4 proves it is equivalent to monotone traversal schemes, giving it formal grounding beyond a postulate.
  • Ambit independent evidence
    purpose: A comparison-based region defined as the preimage of a ball under a remoteness map; generalizes balls, shells, planes, Voronoi cells, polyellipses and metaballs.
    Def 3.0.1 gives a precise definition; Table 1 shows existing regions as special cases, providing external anchoring.
  • Responsibility assignment independent evidence
    purpose: A relation res(e) describing the set of nodes an edge is responsible for, used to give a local correctness criterion.
    Def 2.3.4 and Obs 2.3.10 provide formal conditions and proofs, not an ad hoc postulate.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Comparison-Based Indexing From First Principles." pith.science (2026). https://pith.science/paper/2KY7AKIB

@misc{pith2026190806318,
  author       = {Pith},
  title        = {Pith review of: Comparison-Based Indexing From First Principles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2KY7AKIB}},
  note         = {Machine review of arXiv:1908.06318}
}
read the original abstract

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.

Figures

Figures reproduced from arXiv: 1908.06318 by the authors.

Figure 1
Figure 1. A sprawl of am￾bits. The regions act as hy￾peredges—gatekeepers for their targets, defined in part by their sources.3 In a realistic setting, the re￾gions would typically con￾tain their target points. R R 1 [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. In a sorted search tree (a), the nodes are linearly o [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. A DNF formula represented by a sprawl, with [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Bifocal ambits with linear (a–d), non-linear (e) a [PITH_FULL_IMAGE:figures/full_fig_p017_4.png]
Figure 5
Figure 5. Figure 5: For an unknown metric, any point in the hatched box c [PITH_FULL_IMAGE:figures/full_fig_p019_5.png]
Figure 6
Figure 6. Figure 6: The optimal linear ambit is given by a convex hull in [PITH_FULL_IMAGE:figures/full_fig_p022_6.png]
Figure 7
Figure 7. Figure 7: Optimal ambits with fixed facet counts. The first two [PITH_FULL_IMAGE:figures/full_fig_p024_7.png]
Figure 8
Figure 8. Figure 8: Ambits of varying blobbiness, using the power tran [PITH_FULL_IMAGE:figures/full_fig_p029_8.png]
Figure 9
Figure 9. Figure 9: The ambit construction, as it applies to an egglips [PITH_FULL_IMAGE:figures/full_fig_p033_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

71 extracted references · 71 canonical work pages

  1. [2]

    The Multiplicative W eig hts Update Method: A Meta- Algorithm and Applications

    S. Arora, E. Hazan, and S. Kale. “The Multiplicative W eig hts Update Method: A Meta- Algorithm and Applications”. Theory of Computing 8 (2012)

    work page 2012

  2. [1]

    The Design and Analysis of Computer Algorithms

    A. V. Aho, J. E. Hopcroft, and J. D. Ullman. “The Design and Analysis of Computer Algorithms”. Addison-Wesley (1974)

    work page 1974

  3. [3]

    Directed hypergraphs: Problems, Algo- rithmic Results, and a Novel Decremental Approach

    G. Ausiello, P. G. Franciosa, and D. Frigioni. “Directed hypergraphs: Problems, Algo- rithmic Results, and a Novel Decremental Approach”. Theoretical Computer Science . Vol. 2202. Lecture Notes in Computer Science. Springer, 200 1, pp. 312–328

    work page

  4. [4]

    Organization and maintenanc e of large ordered indexes

    R. Bayer and E. McCreight. “Organization and maintenanc e of large ordered indexes”. Acta Informatica 1.3 (1972), pp. 173–189

    work page 1972

  5. [5]

    A survey of clustering data mining techniqu es

    P. Berkhin. “A survey of clustering data mining techniqu es”. Grouping Multidimen- sional Data . Springer, 2006, pp. 25–71

    work page 2006

  6. [6]

    A Generalization of Algebraic Surface Draw ing

    J. F. Blinn. “A Generalization of Algebraic Surface Draw ing”. ACM Trans. Graph. 1.3 (1982), pp. 235–256

    work page 1982

  7. [7]

    Time bounds for selection

    M. Blum et al. “Time bounds for selection”. Journal of Computer and System Sciences 7.4 (1973), pp. 448–461

    work page 1973

  8. [8]

    On a Product of Metric Spaces

    J. Borsík and J. Doboš. “On a Product of Metric Spaces”. Mathematica Slovaca 31.2 (1981), pp. 193–205

    work page 1981

Show all 71 references
  1. [9]

    Near Neighbor Search in Large Metric Spaces

    S. Brin. “Near Neighbor Search in Large Metric Spaces”. Proceedings of 21th Interna- tional Conference on Very Large Data Bases . Ed. by U. Dayal, P. M. D. Gray, and S. Nishio. Morgan Kaufmann, 1995, pp. 574–584

    1995

  2. [10]

    Approximate multiple string matchin g using spatial indexes

    E. Bugnion et al. “Approximate multiple string matchin g using spatial indexes”. Pro- ceedings of the 1st South American Workshop on String Proces sing. 1993, pp. 43–54

    1993

  3. [11]

    Pivot Selection T echniques for Proximity Search- ing in Metric Spaces

    B. Bustos, G. Navarro, and E. Chávez. “Pivot Selection T echniques for Proximity Search- ing in Metric Spaces”. Pattern Recognition Letters 24.14 (2003), pp. 2357–2366

    2003

  4. [12]

    De la puissance des ensembles parfaits de po ints

    G. Cantor. “De la puissance des ensembles parfaits de po ints”. Acta Mathematica 4.1 (1884), pp. 381–392

  5. [13]

    Spaghe ttis: An Array Based Algo- rithm for Similarity Queries in Metric Spaces

    E. Chávez, J. L. Marroquín, and R. Baeza-Yates. “Spaghe ttis: An Array Based Algo- rithm for Similarity Queries in Metric Spaces”. Proceedings of the String Processing and Information Retrieval Symposium & International Workshop on Groupware (SPIRE) . IEEE Computer Society, 19...

    1999

  6. [14]

    Searching in metric spaces

    E. Chávez et al. “Searching in metric spaces”. ACM Computing Surveys 33.3 (2001), pp. 273–321

    2001

  7. [15]

    An optimal convex hull algorithm in any fix ed dimension

    B. Chazelle. “An optimal convex hull algorithm in any fix ed dimension”. Discrete & Computational Geometry 10.4 (1993), pp. 377–409

    1993

  8. [16]

    The soft heap: An approximate priority qu eue with optimal error rate

    B. Chazelle. “The soft heap: An approximate priority qu eue with optimal error rate”. Journal of the ACM (JACM) 47.6 (2000), pp. 1012–1027

    2000

  9. [17]

    G. Conant. Extending partial isometries of generalized metric spaces . 2016. arXiv: 1509.04950v3 [math.LO] . 43

    2016 arXiv

  10. [18]

    Introduction to Metric-Preserving Funct ions

    P. Corazza. “Introduction to Metric-Preserving Funct ions”. The American Mathemati- cal Monthly 106.4 (1999), pp. 309–323

    1999

  11. [19]

    Crama and P

    Y. Crama and P. L. Hammer. Boolean Functions: Theory, Algorithms, and Applica- tions. Vol. 142. Encyclopedia of Mathematics and its Application s. Cambridge Univer- sity Press, 2011

    2011

  12. [20]

    Cygan et al

    M. Cygan et al. Parameterized Algorithms. Springer, 2015

    2015

  13. [21]

    M. M. Deza and E. Deza. Encyclopedia of Distances . Springer, 2013

    2013

  14. [22]

    A survey of metric preserving functions

    J. Doboš. “A survey of metric preserving functions”. Questions and Answers in General Topology 13.2 (1995), pp. 129–134

    1995

  15. [23]

    J. Doboš. Metric Preserving Functions . Štroffek, 1998

    1998

  16. [24]

    An Access Structure for Similarity Search i n Metric Spaces

    V. Dohnal. “An Access Structure for Similarity Search i n Metric Spaces”. EDBT Work- shops. Ed. by W. Lindner et al. Vol. 3268. Lecture Notes In Computer Science. Springer, 2004, pp. 133–143

    2004

  17. [25]

    Separable Splits of Metric Data Sets

    V. Dohnal et al. “Separable Splits of Metric Data Sets”. Proceedings of the Nono Con- vegno Nazionale Sistemi Evoluti per Basi di Dati . 2001

    2001

  18. [26]

    Indexing inexact proximi ty search with distance regres- sion in pivot space

    O. Edsberg and M. L. Hetland. “Indexing inexact proximi ty search with distance regres- sion in pivot space”. Proceedings of the Third International Conference on Simil arity Search and Applications . ACM. 2010, pp. 51–58

    2010

  19. [27]

    H. B. Enderton. A Mathematical Introduction to Logic . Harcourt Academic Press, 2001

    2001

  20. [28]

    Fixed point theorems on sp aces endowed with vector- valued metrics

    A.-D. Filip and A. Petrusel. “Fixed point theorems on sp aces endowed with vector- valued metrics”. Fixed Point Theory and Applications 2010.1 (2010)

    2010

  21. [29]

    On quasihomomorphisms wi th noncommutative tar- gets

    K. Fujiwara and M. Kapovich. “On quasihomomorphisms wi th noncommutative tar- gets”. Geometric and Functional Analysis (2016), pp. 1–42

    2016

  22. [30]

    A branch and bound algor ithm for computing k- nearest neighbors

    K. Fukunaga and P. M. Narendra. “A branch and bound algor ithm for computing k- nearest neighbors”. IEEE Transactions on Computers 100.7 (1975), pp. 750–753

    1975

  23. [31]

    Directed hyperg raphs and applications

    G. Gallo, G. Longo, and S. Pallottino. “Directed hyperg raphs and applications”. Dis- crete Applied Mathematics 42.2 (1993), pp. 177–201

    1993

  24. [32]

    M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman and Company, 1979

    1979

  25. [33]

    L-fuzzy sets

    J. A. Goguen. “L-fuzzy sets”. Journal of Mathematical Analysis and Applications 18.1 (1967), pp. 145–174

    1967

  26. [34]

    Gener alized Search Trees for Database Systems

    J. M. Hellerstein, J. F. Naughton, and A. Pfeffer. “Gener alized Search Trees for Database Systems”. Proceedings of the 21st International Conference on Very La rge Data Bases . 1995, pp. 562–573

    1995

  27. [35]

    Index-driven similarity search in metric spaces

    G. R. Hjaltason and H. Samet. “Index-driven similarity search in metric spaces”. ACM Transactions on Database Systems, TODS 28.4 (2003), pp. 517–580

    2003

  28. [36]

    W. Hodges. Model Theory. Vol. 42. Encyclopedia of Mathematics and its Applications . Cambridge University Press, 1993

    1993

  29. [37]

    A Data Structure and an Al gorithm for the Nearest Point Problem

    I. Kalantari and G. McDonald. “A Data Structure and an Al gorithm for the Nearest Point Problem”. IEEE Transactions on Software Engineering 9.5 (1983), pp. 631–634

    1983

  30. [38]

    Korte, L

    B. Korte, L. Lovász, and R. Schrader. Greedoids. Vol. 4. Algorithms and Combinatorics. Springer, 1991

    1991

  31. [39]

    A nearly linear-tim e PTAS for explicit fractional packing and covering linear programs

    C. Koufogiannakis and N. E. Young. “A nearly linear-tim e PTAS for explicit fractional packing and covering linear programs”. Algorithmica 70.4 (2014), pp. 648–674

    2014

  32. [40]

    M. Kuczma. An Introduction to the Theory of Functional Equations and In equalities : Cauchy’s Equation and Jensen ’s Inequality . Second. Birkhäuser, 2009

    2009

  33. [41]

    Metric spaces, generalized logic, and c losed categories

    F. W. Lawvere. “Metric spaces, generalized logic, and c losed categories”. Rendiconti del seminario matématico e fisico di Milano 43.1 (1973), pp. 135–166

    1973

  34. [42]

    On applications of parameteriz ed hyperplane partitioning

    J. Lokoč and T. Skopal. “On applications of parameteriz ed hyperplane partitioning”. Proceedings of the Third International Conference on Simil arity Search and Applica- tions. ACM. 2010, pp. 131–132

    2010

  35. [43]

    On indexing metric spaces using cut-reg ions

    J. Lokoč et al. “On indexing metric spaces using cut-reg ions”. Information Systems 43 (2014), pp. 1–19. 44

    2014

  36. [44]

    Multivariable functional in terpolation and adaptive net- works

    D. Lowe and D. Broomhead. “Multivariable functional in terpolation and adaptive net- works”. Complex Syst 2 (1988), pp. 321–355

    1988

  37. [45]

    Logic programs , well-orderings, and forward chaining

    V. W. Marek, A. Nerode, and J. B. Remmel. “Logic programs , well-orderings, and forward chaining”. Annals of Pure and Applied Logic 96 (1999), pp. 231–276

    1999

  38. [46]

    On the Description of Oval Curves, and th ose having a plurality of Foci: with remarks by Professor Forbes

    J. C. Maxwell. “On the Description of Oval Curves, and th ose having a plurality of Foci: with remarks by Professor Forbes”. Proceedings of the Royal Society of Edinburgh 2 (1851), pp. 89–91. Comm. by J. Forbes

  39. [47]

    On asymmetric distances

    A. C. G. Mennucci. “On asymmetric distances”. Analysis and Geometry in Metric Spaces 1 (2013), pp. 200–231

    2013

  40. [48]

    A fast branch & bo und nearest neighbour classifier in metric spaces

    L. Micó, J. Oncina, and R. C. Carrasco. “A fast branch & bo und nearest neighbour classifier in metric spaces”. Pattern Recognition Letters 17.7 (1996), pp. 731–739

    1996

  41. [49]

    A new version of the n earest-neighbour approx- imating and eliminating search algorithm (AESA) with linea r preprocessing time and memory requirements

    M. L. Micó, J. Oncina, and E. Vidal. “A new version of the n earest-neighbour approx- imating and eliminating search algorithm (AESA) with linea r preprocessing time and memory requirements”. Pattern Recognition Letters 15.1 (1994), pp. 9–17

    1994

  42. [50]

    Constant-time array initialization in li ttle space

    G. Navarro. “Constant-time array initialization in li ttle space”. Proceedings of the 31st International Conference of the Chilean Computer Science S ociety. IEEE CS Press, 2012

    2012

  43. [51]

    Searching in metric spaces by spatial appr oximation

    G. Navarro. “Searching in metric spaces by spatial appr oximation”. The VLDB Journal 11.1 (2002), pp. 28–46

    2002

  44. [52]

    Dynamic Spatial Approximatio n Trees

    G. Navarro and N. Reyes. “Dynamic Spatial Approximatio n Trees”. Proceedings of the XXI Conference of the Chilean Computer Science Society . 2001, pp. 213–222

    2001

  45. [53]

    Metric index: An effici ent and scalable solution for precise and approximate similarity search

    D. Novak, M. Batko, and P. Zezula. “Metric index: An effici ent and scalable solution for precise and approximate similarity search”. Information Systems 36.4 (2011), pp. 721– 733

    2011

  46. [54]

    Indexing schemes for sim ilarity search: An illustrated paradigm

    V. Pestov and A. Stojmirović. “Indexing schemes for sim ilarity search: An illustrated paradigm”. Fundamenta Informaticae 70.4 (2006), pp. 367–385

    2006

  47. [55]

    B. Poizat. A Course in Model Theory: An Introduction to Contemporary Ma thematical Logic. Springer, 2000

    2000

  48. [56]

    An algorithm for finding nearest neighbours in (approximately) constant average time

    E. V. Ruiz. “An algorithm for finding nearest neighbours in (approximately) constant average time”. Pattern Recognition Letters 4.3 (1986), pp. 145–157

    1986

  49. [57]

    The theory of the egglipse: A new curv e with three focal points

    P. V. Sahadevana. “The theory of the egglipse: A new curv e with three focal points”. In- ternational Journal of Mathematical Education in Science a nd Technology 18.1 (1987), pp. 29–39

    1987

  50. [58]

    W eak homomorphisms between functori al algebras

    F. M. Schneider. “W eak homomorphisms between functori al algebras”. Demonstratio Mathematica 44.4 (2011), pp. 801–818

    2011

  51. [59]

    Schweizer and A

    B. Schweizer and A. Sklar. Probabilistic Metric Spaces . Elsevier, 1983

    1983

  52. [60]

    Pivoting M-tree: A Metric Access Method for Efficient Similarity Search

    T. Skopal. “Pivoting M-tree: A Metric Access Method for Efficient Similarity Search”. Proceedings of the Annual International Workshop on Databa ses, Texts, Specifications and Objects . Ed. by V. Snášel, J. Pokorný, and K. Richta. Vol. 98. Technic al University of Aachen, 2004

    2004

  53. [61]

    Unified framework for fast exact and approxi mate search in dissimilarity spaces

    T. Skopal. “Unified framework for fast exact and approxi mate search in dissimilarity spaces”. ACM Transactions on Database Systems (TODS) 32.4 (2007), p. 29

    2007

  54. [62]

    Tent and M

    K. Tent and M. Ziegler. A Course in Model Theory . Cambridge University Press, 2012

    2012

  55. [63]

    Metric trees

    J. K. Uhlmann. “Metric trees”. Applied Mathematics Letters 4.5 (1991), pp. 61–62

    1991

  56. [64]

    Satisfying general proximity/similar ity queries with metric trees

    J. K. Uhlmann. “Satisfying general proximity/similar ity queries with metric trees”. In- formation Processing Letters 40.4 (1991), pp. 175–179

    1991

  57. [65]

    D. P. Williamson and D. B. Shmoys. The Design of Approximation Algorithms . Cam- bridge University Press, 2011

    2011

  58. [66]

    A Comprehensive Survey of Clustering Algorithms

    D. Xu and Y. Tian. “A Comprehensive Survey of Clustering Algorithms”. Annals of Data Science 2.2 (2015), pp. 165–193

    2015

  59. [67]

    P. N. Yianilos. Excluded Middle Vantage Point Forests for Nearest Neighbor Search. Tech. rep. NEC Research Institute, 1999. 45

    1999

  60. [68]

    Zezula, P

    P. Zezula, P. Ciaccia, and F. Rabitti. M-tree: A Dynamic Index for Similarity Queries in Multimedia Databases . Technical Report 7. Hermes Esprit L tr Project, 1996

    1996

  61. [69]

    Zezula et al

    P. Zezula et al. Similarity Search: The Metric Space Approach . Springer, 2006

    2006

  62. [70]

    G. M. Ziegler. Lectures on Polytopes. Vol. 152. Graduate Texts in Mathematics. Springer, 1995

    1995

  63. [71]

    Zimmermann

    H.-J. Zimmermann. Fuzzy set theory and its applications . Springer, 2001. 46

    2001

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.