Approximate Furthest Neighbor in High Dimensions

Rasmus Pagh, Francesco Silvestri, Johan von Tangen Sivertsen, Matthew Skala

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review


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.
TitelSimilarity Search and Applications : 8th International Conference, SISAP 2015, Glasgow, UK, October 12–14, 2015, Proceedings
ISBN (Trykt)978-3-319-25086-1
ISBN (Elektronisk)978-3-319-25087-8
StatusUdgivet - 2015
NavnLecture Notes in Computer Science


Dyk ned i forskningsemnerne om 'Approximate Furthest Neighbor in High Dimensions'. Sammen danner de et unikt fingeraftryk.