利用多层块索引在高维数据中实现高效的限时kNN搜索，并扩展到多属性过滤

《ACM Transactions on Knowledge Discovery from Data》：Efficient Time-Restricted kNN Search in High-Dimensional Data Using Multi-Level Block Indexing, with Extensions to Multi-Attribute Filtering

如何高效索引增长的高维向量数据并支持时间窗口内的快速k近邻查询，本文提出多级块索引（MBI）方法。通过增量分层索引结构，将数据按时间戳分块，实现时间窗口内k近邻搜索的效率提升，实验显示查询速度比传统方法快10.88倍，插入时间随数据量增长呈对数级。该方法还扩展至多属性k近邻问题，支持年龄、身高等多约束条件查询，保持稳定性能。

　　

摘要 AI摘要

要查看此由AI生成的摘要，您必须具有高级访问权限。

了解更多 登录

摘要

摘要

我们如何有效地索引随着时间增长而不断增加的大量高维向量数据，以便在指定的时间窗口内快速准确地进行近似搜索？一种基于时间限制的最近邻（T-kNN）查询方法旨在在指定时间窗口内找到与查询向量最接近的k个向量。尽管高维和随时间累积的数据非常普遍，且高效管理此类数据变得越来越重要，但在这种背景下，T-kNN搜索尚未受到太多关注。在本文中，我们提出了多层块索引（MBI）方法，这是一种专为高效T-kNN搜索量身定制的索引方法。MBI采用了一种增量式层次索引结构，根据时间戳将数据划分为多个块。这种结构确保了无论查询时间窗口的长度如何，都能高效处理查询，并便于随着时间的推移添加新数据。此外，我们将T-kNN扩展到多属性查询问题，引入了诸如年龄、身高和体重（在医疗数据中）或学术论文的引用次数等附加属性，使查询能够整合多个数值约束。实验结果表明，MBI优于传统方法，查询处理速度提高了多达10.88倍，并且随着数据量的增加，数据插入时间具有对数级扩展性。此外，在多属性查询中，MBI保持了稳定的索引性能，查询速度提高了多达1.99倍，证明了其在大规模多属性搜索中的有效性。

AI摘要

要查看此由AI生成的简单语言摘要，您必须具有高级访问权限。