模型自学习构建数据结构，能自动发现近邻搜索最优算法。
Discovering Data Structures: Nearest Neighbor Search and Beyond
- 端到端训练模型自主设计数据结构，无需预设算法。
- 一维场景下学到二分查找等最优算法，高维中逼近k-d树与哈希方案。
- 适合研究新数据结构或想自动化设计查询算法的学者。
我们提出一种端到端学习数据结构的通用框架，可自适应数据分布，并精细控制查询与空间复杂度。关键在于数据结构从零学习，无需人工初始化或预设候选算法。首先应用于最近邻搜索，在多个设置下可逆向解析出学习到的结构与查询算法：一维场景下发现最优的分布无关算法（如二分查找、插值查找变体）；高维情况下，部分情形下结构类似k-d树，另一些则包含局部敏感哈希特征。模型还能学习高维数据的有效表示并用于构建高效数据结构。该框架进一步拓展至数据流频率估计问题，我们认为其亦可成为发现新问题的强大工具。
原文摘要 · Abstract (English)
We propose a general framework for end-to-end learning of data structures. Our framework adapts to the underlying data distribution and provides fine-grained control over query and space complexity. Crucially, the data structure is learned from scratch, and does not require careful initialization or seeding with candidate data structures/algorithms. We first apply this framework to the problem of nearest neighbor search. In several settings, we are able to reverse-engineer the learned data structures and query algorithms. For 1D nearest neighbor search, the model discovers optimal distribution (in)dependent algorithms such as binary search and variants of interpolation search. In higher dimensions, the model learns solutions that resemble k-d trees in some regimes, while in others, they have elements of locality-sensitive hashing. The model can also learn useful representations of high-dimensional data and exploit them to design effective data structures. We also adapt our framework to the problem of estimating frequencies over a data stream, and believe it could also be a powerful discovery tool for new problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。