A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems
View/ Open
Date
2021-06-20Author
Augustine, Jees
Shetiya, Suraj
Esfandiari, Mohammadreza
Basu Roy, Senjuti
Das, Gautam
Metadata
Show full item recordAbstract
In this paper, we revisit a suite of popular proximity problems
(such as, KNN, clustering, minimum spanning tree) that repeatedly
perform distance computations to compare distances during their
execution. Our effort here is to design principled solutions to minimize distance computations for such problems in general metric
spaces, especially for the scenarios where calling an expensive oracle to resolve unknown distances are the dominant cost of the
algorithms for these problems. We present a suite of techniques,
including a novel formulation of the problem, that studies how distance comparisons between objects could be modelled as a system
of linear inequalities that assists in saving distance computations,
multiple graph based solutions, as well as a practitioners guide to
adopt our solution frameworks to proximity problems. We compare
our designed solutions conceptually and empirically with respect to
a broad range of existing works. We finally present a comprehensive
set of experimental results using multiple large scale real-world
datasets and a suite of popular proximity algorithms to demonstrate
the effectiveness of our proposed approaches.