Approximate Furthest Neighbor in High Dimensions

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

doi:10.1007/978-3-319-25087-8_1

Approximate Furthest Neighbor in High Dimensions

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

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Abstract

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.

Original language	English
Title of host publication	Similarity Search and Applications : 8th International Conference, SISAP 2015, Glasgow, UK, October 12–14, 2015, Proceedings
Publisher	Springer
Publication date	2015
Pages	3-14
ISBN (Print)	978-3-319-25086-1
ISBN (Electronic)	978-3-319-25087-8
DOIs	https://doi.org/10.1007/978-3-319-25087-8_1
Publication status	Published - 2015

Series	Lecture Notes in Computer Science
Volume	9371
ISSN	0302-9743

Keywords

Approximate furthest neighbor
High-dimensional data structures
Random projections
Query optimization
Recommender systems

Access to Document

10.1007/978-3-319-25087-8_1

approx-furthest-neighbor-SISAP15Accepted author manuscript, 481 KB

http://www.itu.dk/people/pagh/papers/approx-furthest-neighbor-SISAP15.pdf

Cite this

@inproceedings{526b200e318f4661b7d5901bd1dc5faa,

title = "Approximate Furthest Neighbor in High Dimensions",

abstract = "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{\textquoteright}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.",

keywords = "Approximate furthest neighbor, High-dimensional data structures, Random projections, Query optimization, Recommender systems",

author = "Rasmus Pagh and Francesco Silvestri and Sivertsen, {Johan von Tangen} and Matthew Skala",

year = "2015",

doi = "10.1007/978-3-319-25087-8_1",

language = "English",

isbn = "978-3-319-25086-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "3--14",

booktitle = "Similarity Search and Applications",

address = "Germany",

}

Approximate Furthest Neighbor in High Dimensions. / Pagh, Rasmus; Silvestri, Francesco; Sivertsen, Johan von Tangen et al.
Similarity Search and Applications: 8th International Conference, SISAP 2015, Glasgow, UK, October 12–14, 2015, Proceedings. Springer, 2015. p. 3-14 (Lecture Notes in Computer Science, Vol. 9371).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

TY - GEN

T1 - Approximate Furthest Neighbor in High Dimensions

AU - Pagh, Rasmus

AU - Silvestri, Francesco

AU - Sivertsen, Johan von Tangen

AU - Skala, Matthew

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Approximate furthest neighbor

KW - High-dimensional data structures

KW - Random projections

KW - Query optimization

KW - Recommender systems

U2 - 10.1007/978-3-319-25087-8_1

DO - 10.1007/978-3-319-25087-8_1

M3 - Article in proceedings

SN - 978-3-319-25086-1

T3 - Lecture Notes in Computer Science

SP - 3

EP - 14

BT - Similarity Search and Applications

PB - Springer

ER -

Approximate Furthest Neighbor in High Dimensions

Abstract

Keywords

Access to Document

Fingerprint

Cite this