Diverse types of edge data, such as 2D geo-locations and 3D point clouds, are collected by sensors like lidar and GPS receivers on edge devices. On-device searches, such as k-nearest neighbor (kNN) search and radius search, are commonly used to enable fast analytics and learning technologies, such as k-means dataset simplification using kNN. To maintain high search efficiency, a representative approach is to utilize a balanced multi-way KD-tree (BMKD-tree). However, the index has shown limited gains, mainly due to substantial construction overhead, inflexibility to real-time insertion, and inconsistent query performance. In this paper, we propose UnIS to address the above limitations. We first accelerate the construction process of the BMKD-tree by utilizing the dataset distribution to predict the splitting hyperplanes. To make the continuously generated data searchable, we propose a selective sub-tree rebuilding scheme to accelerate rebalancing during insertion by reducing the number of data points involved. We then propose an auto-selection model to improve query performance by automatically selecting the optimal search strategy among multiple strategies for an arbitrary query task. Experimental results show that UnIS achieves average speedups of 17.96x in index construction, 1.60x in insertion, 7.15x in kNN search, and 1.09x in radius search compared to the BMKD-tree. We further verify its effectiveness in accelerating dataset simplification on edge devices, achieving a speedup of 217x over Lloyd's algorithm.

翻译：多种类型的边缘数据，如二维地理坐标和三维点云，由激光雷达和GPS接收器等传感器在边缘设备上采集。设备端搜索，如k近邻（kNN）搜索和半径搜索，常用于支持快速分析与学习技术，例如利用kNN进行k均值数据集简化。为维持高搜索效率，一种代表性方法是采用平衡多路KD树（BMKD-tree）。然而，该索引的增益有限，主要源于显著的构建开销、对实时插入的僵化适应以及不一致的查询性能。本文提出UnIS以解决上述局限。我们首先通过利用数据集分布预测分割超平面，加速BMKD-tree的构建过程。为使持续生成的数据可搜索，我们提出一种选择性子树重建方案，通过减少涉及的数据点数量来加速插入过程中的再平衡。随后，我们提出一种自动选择模型，通过为任意查询任务自动选择多种策略中的最优搜索策略，以提升查询性能。实验结果表明，与BMKD-tree相比，UnIS在索引构建、插入、kNN搜索和半径搜索中分别实现了平均17.96倍、1.60倍、7.15倍和1.09倍的加速。我们进一步验证了其在边缘设备上加速数据集简化的有效性，相比Lloyd算法实现了217倍的加速。