t-Spanners as a Data Structure for Metric Space Searching
Gonzalo Navarro, Rodrigo Paredes and Edgar Chávez
A t-spanner, a subgraph that approximates graph distances within
a precision factor t, is a well known concept in graph theory. In this
paper we use it in a novel way, namely as a data structure for searching
metric spaces. The key idea is to consider the t-spanner as an
approximation of the complete graph of distances among the objects, and
use it as a compact device to simulate the large matrix of distances
required by successful search algorithms like AESA [Vidal 1986]. The
t-spanner provides a time-space tradeoff where full AESA is just
one extreme. We show that the resulting algorithm is competitive against
current approaches, e.g., 1.5 times the time cost of AESA using only 3.21%
of its space requirement, in a metric space of strings. We also show that
t-spanners provide better space-time tradeoffs than classical
alternatives such as pivot-based indexes. Furthermore, we show
that the concept of t-spanners has potential for large improvements.