4 papers
Fairest Neighbors: Tradeoffs Between Metric Queries
Magnus Lie Hetland, Halvard Hummel
Metric search commonly involves finding objects similar to a given sample object. We explore a generalization, where the desired result is a fair tradeoff between multiple query ob…
Metrics and Ambits and Sprawls, Oh My
Magnus Lie Hetland
A follow-up to my previous tutorial on metric indexing, this paper walks through the classic structures, placing them all in the context of the recently proposed "sprawl of ambits"…
Optimal Metric Search Is Equivalent to the Minimum Dominating Set Problem
Magnus Lie Hetland
In metric search, worst-case analysis is of little value, as the search invariably degenerates to a linear scan for ill-behaved data. Consequently, much effort has been expended on…
Comparison-Based Indexing From First Principles
Magnus Lie Hetland
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 desc…