Approximate Nearest Neighbor Search with Window Filters
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909216284868608 |
|---|---|
| author | Engels, Joshua Landrum, Benjamin Yu, Shangdi Dhulipala, Laxman Shun, Julian |
| author_facet | Engels, Joshua Landrum, Benjamin Yu, Shangdi Dhulipala, Laxman Shun, Julian |
| contents | We define and investigate the problem of $\textit{c-approximate window search}$: approximate nearest neighbor search where each point in the dataset has a numeric label, and the goal is to find nearest neighbors to queries within arbitrary label ranges. Many semantic search problems, such as image and document search with timestamp filters, or product search with cost filters, are natural examples of this problem. We propose and theoretically analyze a modular tree-based framework for transforming an index that solves the traditional c-approximate nearest neighbor problem into a data structure that solves window search. On standard nearest neighbor benchmark datasets equipped with random label values, adversarially constructed embeddings, and image search embeddings with real timestamps, we obtain up to a $75\times$ speedup over existing solutions at the same level of recall. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_00943 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximate Nearest Neighbor Search with Window Filters Engels, Joshua Landrum, Benjamin Yu, Shangdi Dhulipala, Laxman Shun, Julian Data Structures and Algorithms Information Retrieval Machine Learning We define and investigate the problem of $\textit{c-approximate window search}$: approximate nearest neighbor search where each point in the dataset has a numeric label, and the goal is to find nearest neighbors to queries within arbitrary label ranges. Many semantic search problems, such as image and document search with timestamp filters, or product search with cost filters, are natural examples of this problem. We propose and theoretically analyze a modular tree-based framework for transforming an index that solves the traditional c-approximate nearest neighbor problem into a data structure that solves window search. On standard nearest neighbor benchmark datasets equipped with random label values, adversarially constructed embeddings, and image search embeddings with real timestamps, we obtain up to a $75\times$ speedup over existing solutions at the same level of recall. |
| title | Approximate Nearest Neighbor Search with Window Filters |
| topic | Data Structures and Algorithms Information Retrieval Machine Learning |
| url | https://arxiv.org/abs/2402.00943 |