根据查询分布学习最优近邻搜索树，显著提升查询效率。
Learning Partition Trees for Nearest Neighbor Search
- 基于数据驱动设计，学习针对特定查询分布的平衡半空间树。
- 在高斯假设下，实现接近o(nd)的查询时间复杂度。
- 提出高效近似算法，适用于实际中难以找到最优分割的情况。
我们从数据驱动算法设计的角度研究最近邻搜索：给定一个大小为n、位于ℝ^d中的数据集P，以及对ℝ^d上查询分布的样本访问权限，目标是学习一个针对该特定分布优化的数据结构。我们聚焦于平衡半空间树这一类，其自然抽象了局部敏感哈希等空间划分框架。在数据集与查询分布满足类似高斯边缘条件的前提下，我们给出一个高效算法，可在存在完美树的情况下实现o(nd)的查询时间。算法核心是平衡半空间切割问题：给定ℝ^d × ℝ^d上的分布，需找到一个平衡半空间以最小化被切割点对的比例。我们证明，在无分布假设下，寻找最优平衡半空间是NP难的。为克服此计算障碍，我们设计了一种高效的非正确学习算法：若最优半空间切割α比例的点对，我们的算法可输出一个次数为~O(1/ε²)的平衡多项式阈值函数，其切割比例不超过O(√(α+ε))。
原文摘要 · Abstract (English)
We study nearest neighbor search from the perspective of data-driven algorithm design: given a dataset $P \subset \mathbb{R}^d$ of size $n$ and sample access to a query distribution over $\mathbb{R}^d$, the goal is to learn a data structure optimized for queries drawn from that specific distribution. We focus on the class of balanced halfspace trees, which naturally abstracts space-partitioning frameworks like locality-sensitive hashing. Assuming Gaussian-like marginal conditions on the dataset and query distribution, we give an efficient algorithm that learns a tree achieving $o(nd)$ query time, provided that a perfect tree exists. At the core of our algorithmic approach is the balanced halfspace cut problem, where we are given a distribution over $\mathbb{R}^d \times \mathbb{R}^d$ and must find a balanced halfspace that minimizes the fraction of cut pairs. We prove that without distributional assumptions, finding the optimal balanced halfspace is NP-hard. To circumvent this computational barrier, we design an efficient improper learning algorithm: if the optimal halfspace cuts an $α$ fraction of pairs, our algorithm outputs a balanced polynomial threshold function of degree $\tilde{O}(1/\varepsilon^2)$ that cuts at most an $O(\sqrt{α+\varepsilon})$ fraction.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。