基于分层索引的高维数据对象检索

发布时间：2021-01-20 07:12

　　随着海量信息检索技术的发展,对文本、图片和视频等高维数据对象的相似性检索要求不断提高。局部敏感哈希（LSH）是解决高维数据近邻检索的主要方法之一,但存在索引存储代价高及查询效率低等问题。提出了一种基于二级混合索引模型构造方法,先利用溢出树（Spill tree）对数据集进行划分,再对每个部分构建基于LSH的哈希表,形成混合索引,支撑高维数据检索。试验表明,该方法缩小了高维数据对象的索引存储空间,提高了查询效率和查询质量。 

【文章来源】：指挥信息系统与技术. 2019,10(06)

【文章页数】：5 页

【部分图文】：

LSS tree算法分层索引结构

图2(c)中,若查询半径r取值较大,则易于找到满足条件的k个近邻点,但是会牺牲查询质量;反之,若查询半径r取值较小,则需耗费更多时间进行检索,影响查询效率。除了查询时间指标外,对算法性能评估还需考虑查询质量指标。暴力搜索属于精确查询,而Spill tree算法在叶节点同样采用暴力搜索,只要划分的数据点中有k个点置于该叶节点,即可精确满足近邻查询,因此本文不对暴力搜索和Spill tree算法进行比较分析。本文仅对LSB和LSS tree 2种算法在不同k值情况下的查准率Ratio进行对比,其对比结果如表1所示。可见,k值选择对查准率有一定影响,这是由于LSH算法存在一定的随机性,而LSB和LSS算法均基于LSH算法,因此k值上升会导致查准率Ratio下降。LSB和LSS算法的查准率较接近,均达到了较高水平。在查准率接近情况下,由于LSS算法的查询消耗时间较短,因此LSS算法的性能相比其他算法有显著提升。

【参考文献】：
期刊论文
[1]基于搜索引擎日志的用户查询意图分类[J]. 杨杰,徐越,余建桥,蒋建华.  指挥信息系统与技术. 2019(02)
[2]一种基于主成分的多表图像哈希检索方法[J]. 邓清文,林志贤,郭太良.  计算机工程与应用. 2018(03)
[3]一种基于LSH面向二元混合类型数据的相似性查询方法[J]. 朱命冬,申德荣,寇月,聂铁铮,于戈.  计算机学报. 2018(08)

硕士论文
[1]基于位置敏感哈希的近似kNN查询算法研究[D]. 邱文明.大连理工大学 2014



本文编号：2988624