Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Approximate Furthest Neighbor in High Dimensions
verfasst von : Rasmus Pagh, Francesco Silvestri, Johan Sivertsen, Matthew Skala
Erschienen in: Similarity Search and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Much recent work has been devoted to approximate nearest neighbor queries. Motivated by applications in recommender systems, we consider
approximate furthest neighbor
(AFN) queries. We present a simple, fast, and highly practical data structure for answering AFN queries in high-dimensional Euclidean space. We build on the technique of Indyk (SODA 2003), storing random projections to provide sublinear query time for AFN. However, we introduce a different query algorithm, improving on Indyk’s approximation factor and reducing the running time by a logarithmic factor. We also present a variation based on a query-independent ordering of the database points; while this does not have the provable approximation factor of the query-dependent data structure, it offers significant improvement in time and space complexity. We give a theoretical analysis, and experimental results.