论文部分内容阅读
泛在的网络环境中充斥着大量的高维数据,如音频、视频、图片等。传统的线性搜索和树形搜索方法已经不能满足高维数据的快速相似性搜索的需求。近年来提出的基于哈希技术的相似搜索算法能够很好地解决传统的搜索算法在面对高维数据时遇到的“维度灾难”问题。现今,基于哈希技术的算法中最受欢迎的就是基于P-稳定分布的位置敏感哈希(LSH)算法。然而,目前基于P-稳定分布的位置敏感哈希框架有两大不足。首先,它需要大量的哈希表来保证相似查询的性能,造成索引空间占用内存过大。其次,其搜索策略的不足使得搜索效率不高。在分析传统位置敏感哈希算法的基础上,本文改进了现有的基于LSH的哈希索引计算模型和哈希索引框架。本文提出了基于哈希桶的堆排序的位置敏感哈希算法(HSLSH)。首先,该算法采用单哈希表的策略,避免了传统位置敏感哈希框架中因哈希表数量过大造成索引空间占用内存过大的问题。其次,该算法采用了基于哈希桶的堆排序的思想,返回数据对象所在桶的相似桶。以桶代替数据对象,既降低了数据维度,又降低了数据比较的规模。另外采用堆排序的方法过滤掉不相似的桶,进一步提高查询的速度。为了进一步提高相似搜索的速度,本文提出了基于桶链模型的双层位置敏感哈希搜索框架(BCLSH)。BCLSH框架采用桶链模型在构建索引时保存每一个哈希桶的相似桶引用数组,使得在查询过程中能够在O(1)的时间内返回查询对象所在桶的相似桶。为了降低索引构建的时间复杂度,本文采用了双层位置敏感哈希框架。本文采用正交位置敏感哈希函数(BOLSH)构建第一层哈希表,将数据空间划分成多个子空间,既降低了每个子空间的数据规模,又可以使得每个子空间可以完全并行的构建各自的哈希表。其次,为了解决数据分布不均的问题,BCLSH支持跨分区搜索。同时,针对HSLSH算法中堆排序的比较规则做出了进一步改进,提出了新的比较算法。理论分析和实验证明,本文提出的HSLSH算法相较于C2LSH和FBLSH算法能够进一步缩短相似搜索的时间。本文提出的BCLSH框架相较于LSH forest和DPF框架,具有更优的查询效率和更快的构建哈希索引的速度。