Fast Approximate Furthest Neighbors with Data-Dependent Candidate Selection
| Autor: | Ryan R. Curtin, Andrew B. Gardner |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Speedup
Furthest Neighbor Computer science Random projection 0102 computer and information sciences 02 engineering and technology 01 natural sciences Empirical research 010201 computation theory & mathematics 020204 information systems 0202 electrical engineering electronic engineering information engineering Search problem Voronoi diagram Data dependent Algorithm Intuition |
| Zdroj: | Similarity Search and Applications ISBN: 9783319467580 SISAP |
| Popis: | We present a novel strategy for approximate furthest neighbor search that selects a candidate set using the data distribution. This strategy leads to an algorithm, which we call DrusillaSelect, that is able to outperform existing approximate furthest neighbor strategies. Our strategy is motivated by an empirical study of the behavior of the furthest neighbor search problem, which lends intuition for where our algorithm is most useful. We also present a variant of the algorithm that gives an absolute approximation guarantee; under some assumptions, the guaranteed approximation can be achieved in provably less time than brute-force search. Performance studies indicate that DrusillaSelect can achieve comparable levels of approximation to other algorithms while giving up to an order of magnitude speedup. An implementation is available in the mlpack machine learning library (found at http://www.mlpack.org). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|