基于键值线序优化的LSH索引技术

摘要

本文阐述高维空间中的最近邻(Nearest Neighbor,NN)查询是多媒体数据库领域中的一个基本问题.局部敏感哈希(Locality-Sensitive Hashing,LSH)索引结构能有效克服“维数灾难”现象,是解决c-近似最近邻(c-ANN)问题的一种有效手段.为进一步降低I/O开销,SK-LSH方法为复合哈希键值建立线序,通过优化候选点在磁盘上分布的局部聚敛性,能有效兼顾最近邻查询精度和磁盘访问效率.本文通过分析空间线序机理对最近邻候选点分布局部聚敛性的影响,指出SK-LSH中键值线序的不足,提出一种基于线序优化的LSH外存索引技术,O2LSH(Optimized Order LSH).使用曲线性能更加优秀的z-order代替SK-LSH中的row-wise曲线指导键值排序,借助z-order更好的局部空间优先遍历的性质更快地召回最近邻,从而在保证查询精度的前提下,进一步提升磁盘访问效率、节省多索引哈希表的构建开销.在实际的多媒体数据集上进行的对比实验表明:优化了键值线序后,O2LSH在最近邻查询精度和效率上相对于SK-LSH有较大地提升.