根据查询样本构建高效范围搜索树，提升查询速度与空间效率。
A Query-Driven Approach to Space-Efficient Range Searching
- 基于查询采样构造近优的划分树，减少平均访问节点数。
- 利用浅层神经网络加速节点分类，实测查询效率显著提升。
- 采用稀疏几何分隔符构建平衡树，兼顾节点处理快与访问少。
我们提出一种查询驱动的范围搜索划分树设计方法。模型假设数据结构需针对未知查询分布构建，可通过采样预言机访问，并需在期望性能上优化。首个贡献是证明：近线性规模的查询样本足以构建出预期访问节点数接近最优的划分树。我们进一步将节点处理视为分类问题，利用快速分类器（如浅层神经网络）实现高效的实验查询时间。第二个贡献是使用稀疏几何分隔符构建划分树。基于查询样本的预处理算法构建平衡树，节点关联的分隔符最小化期望查询击中次数，从而在保证单节点处理速度快的同时，大幅减少访问节点数量，显著降低查询时间。
原文摘要 · Abstract (English)
We initiate a study of a query-driven approach to designing partition trees for range-searching problems. Our model assumes that a data structure is to be built for an unknown query distribution that we can access through a sampling oracle, and must be selected such that it optimizes a meaningful performance parameter on expectation. Our first contribution is to show that a near-linear sample of queries allows the construction of a partition tree with a near-optimal expected number of nodes visited during querying. We enhance this approach by treating node processing as a classification problem, leveraging fast classifiers like shallow neural networks to obtain experimentally efficient query times. Our second contribution is to develop partition trees using sparse geometric separators. Our preprocessing algorithm, based on a sample of queries, builds a balanced tree with nodes associated with separators that minimize query stabs on expectation; this yields both fast processing of each node and a small number of visited nodes, significantly reducing query time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。