构建无需依赖数据分布的线性规模近邻搜索结构
Graph-Based Nearest-Neighbor Search without the Spread
- 基于图结构设计线性大小的数据结构
- 在n个点上实现log n时间的近似最近邻查询
- 突破了传统方法对数据分散度的依赖
近期工作表明，可在给定d维空间中n个点集P上构造线性规模的近邻图，使得近似最近邻查询在数据分散度（spread）的对数时间内完成。然而，分散度可能随n无界增长，因此一个重要的理论问题是能否消除对分散度的依赖。本文提出一种外部线性规模的数据结构，与线性规模图结合后，可在n的对数时间内回答近似最近邻查询。
原文摘要 · Abstract (English)
$\renewcommand{\Re}{\mathbb{R}}$Recent work showed how to construct nearest-neighbor graphs of linear size, on a given set $P$ of $n$ points in $\Re^d$, such that one can answer approximate nearest-neighbor queries in logarithmic time in the spread. Unfortunately, the spread might be unbounded in $n$, and an interesting theoretical question is how to remove the dependency on the spread. Here, we show how to construct an external linear-size data structure that, combined with the linear-size graph, allows us to answer ANN queries in logarithmic time in $n$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。