基于最优排序的局部敏感哈希索引

• 作者: 冯小康 刘英帆 崔江涛 彭延国 李辉
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 近似最近邻 高维索引 局部敏感哈希 空间线序 局部分布
• 年，卷（期）: 2020,（5）
• 所属期刊栏目: 自然语言与数据处理
• 页码范围: 930-947
• 页数: 18页
• 分类号: TP311
• 字数: 14807字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2020.00930

摘要

针对外存环境中海量高维数据近似最近邻(Approximate Nearest Neighbor,ANN)查询面临的“维度灾难”和I/O性能瓶颈难题,本文提出了一种基于最优排序的局部敏感哈希(Locality-Sensitive Hashing,LSH)索引方案O2LSH(Optimal Order LSH).通过引入空间填充曲线为复合哈希键值建立线序并排序,使近邻候选点更多地分布在相同或相邻磁盘页面,实现用少量顺序I/O加载到足够多的候选点.本文对多种常用空间曲线技术进行了量化分析,发现:(1)基本排序方案SK-LSH使用的row-wise曲线具有“维度优先遍历”的特性,容易对ANN查询造成多种局限;(2)另一类“邻域优先遍历”特性的曲线能够产生更好的候选点局部分布,且排序性能更加稳定.通过对比,我们选取了一种最优的“邻域优先遍历”曲线构造线序,该线序能够最大程度地改善近邻候选点的局部分布,进一步提升磁盘访问效率和查询精度.在多个真实多媒体数据集上进行了对比实验,证实了O2LSH相对于先进LSH方案(包括C2LSH、SK-LSH、SRS以及QALSH)在查询精度和I/O效率上的优越性.特别地,O2LSH克服了基本排序方案SK-LSH对LSH关键参数的敏感性,算法实用性进一步提升.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	崔江涛	西安电子科技大学计算机科学与技术学院	39	445	11.0	20.0
2	李辉	西安电子科技大学网络与信息安全学院	17	57	5.0	6.0
4	冯小康	西安电子科技大学计算机科学与技术学院	1	0	0.0	0.0
5	彭延国	西安电子科技大学计算机科学与技术学院	5	16	2.0	4.0
6	刘英帆	香港中文大学系统工程与工程管理系	1	0	0.0	0.0