iDistance是一种索引与查询处理技术，旨在高效处理多维度量空间中点数据的k近邻（kNN）查询。kNN查询是多维数据上最困难的问题之一，尤其是在维度较高时。iDistance通过将多维点映射到一维空间来应对这一挑战，从而能够使用B+-树进行索引和查询处理。该技术对偏斜数据分布表现极为出色，而偏斜分布常见于现实数据集，并遵循过滤与精炼原则（FRP），在验证真实近邻之前先剪枝搜索空间。
iDistance索引还可以与机器学习模型相结合，以学习数据分布，从而改进多维数据的搜索与存储。这种集成使索引能够适应底层数据特征，在动态环境中提升查询性能。
索引构建
构建iDistance索引涉及两个主要步骤。首先，在数据空间中选择若干参考点。选择参考点有多种方法，其中聚类中心是最为高效的方式。基于这些精心选择的参考点，数据点被划分到Voronoi单元中，确保每个点与其最近的参考点相关联。
其次，计算数据点与其最近参考点之间的距离。该距离加上一个缩放值，构成该点的iDistance。通过这种方式，多维空间中的点被映射为一维值，随后B+-树可以以iDistance为键对点进行索引。这种映射简化了索引结构，并支持高效的范围查询。
已有多种扩展被提出以改进参考点选择，从而提升查询性能，其中包括利用机器学习来学习参考点的识别。这些扩展旨在针对特定数据分布和查询负载优化索引。
查询处理
为处理kNN查询，查询被映射为多个一维范围查询，这些查询可以在B+-树上高效执行。查询点被映射为B+-树中的一个值，而kNN搜索球被映射为一个范围。搜索球逐渐扩大，直到找到k个最近邻，这对应于B+-树中范围搜索的逐步扩展。
iDistance技术可以被视为加速顺序扫描的一种方式。它不是从数据文件的开头到结尾扫描记录，而是从最有可能尽早获得最近邻的位置开始扫描。这种有针对性的扫描减少了检查的记录数量，从而缩短了查询响应时间。
两阶段搜索策略包括对候选区域的初始过滤，随后对结果进行精炼。这种方法与数据库搜索算法中使用的过滤与精炼原则（FRP）一致，即索引首先剪枝搜索空间以排除不太可能的候选，然后在精炼步骤中验证真实近邻。
应用
iDistance已被应用于许多领域，包括图像检索、视频索引、对等（P2P）系统中的相似性搜索、移动计算以及推荐系统。在图像检索中，该技术能够实现视觉特征的快速相似性匹配。对于视频索引，它支持对时空数据的高效查询。在P2P系统中，iDistance促进了分布式相似性搜索，而在移动计算中，它有助于管理基于位置的查询。推荐系统则受益于iDistance在高维特征空间中查找相似物品或用户的能力。
该技术对偏斜数据的鲁棒性使其特别适用于数据分布通常不均匀的现实应用。其与机器学习的集成进一步扩展了其在动态数据环境中的适用性。
历史背景
iDistance由Cui Yu、Beng Chin Ooi、Kian-Lee Tan和H. V. Jagadish于2001年首次提出。后来，他们与Rui Zhang合作，在2005年对该技术进行了改进并开展了更全面的研究。最初的提案引入了参考点选择和一维映射的核心概念，而后续工作则完善了该方法，并对其性能特征进行了更深入的分析。
iDistance的发展为高维索引这一更广泛的领域做出了贡献，解决了数据增强及其他数据密集型应用中出现的挑战。其过滤与精炼范式影响了后续关于模型剪枝和查询优化技术的研究。
参见
- 过滤与精炼原则
- 可学习函数
- 残差网络