论文部分内容阅读
高维空间中的相似性检索(High-Dimensional Similarity Search)问题在数据库、数据挖掘以及计算几何等领域有着广泛的应用。给定一个相似性函数,相似性检索问题是指在数据库找到一个数据对象,使得它与一个给定的查询对象的相似度最大。根据度量函数的不同,相似性检索问题有不同的形式。本文着重研究相似性检索在欧氏空间中三个非常重要的问题:最近邻检索、最远邻检索和最大内积检索。由于受到维度灾难的影响,在高维空间中找到精确的结果代价非常大,因此近似相似性检索在近20年得到了广泛的关注。然而,目前近似相似性检索问题仍然存在一些挑战:(1)对于高维c-近似最近邻问题,位置敏感哈希(Locality Sensitive Hashing,简称LSH)及其变体是目前最有影响的方法。然而,当前LSH函数由于采用查询无关的分桶策略,容易导致误分桶,并限制了业界领先的外存方法LSBForest和C2LSH只能支持c≥2的近似最近邻检索;(2)对于高维c-近似最远邻问题,目前尚没有一个高效的外存算法可以处理高维空间中的近似最远邻检索;(3)对于高维c-近似最大内积问题,业界领先的方法Sign-ALSH和Simple-LSH没有充分利用数据的分布和查询的信息,导致检索的精度和效率偏低。针对上述这些问题,本文以LSH函数族和LSH机制为切入点,对高维欧氏空间中的c-近似最近邻检索、c-近似最远邻检索和c-近似最大内积检索做了深入的研究。总的来说,本文的主要工作有以下几点:对于高维c-近似最近邻问题,本文首先提出了一种针对lp距离的查询引导的LSH函数,其中p∈(0,2]。与传统的LSH函数相比,该函数使用查询的哈希值作为锚点,临时的对数据对象进行分桶,可以有效避免误分桶操作。基于查询引导的LSH函数,本文提出了基于外存的新型的查询引导的位置敏感哈希机制(QueryAware LSH,简称QALSH)。本文通过理论证明,QALSH对于近似最近邻检索有理论保证,并且可以支持任意的近似比例c>1。本文的实验结果表明,QALSH胜过业界领先的LSB-Forest,C2LSH和SRS算法,并且在高维空间中表现尤其出色。对于高维c-近似最远邻问题,本文首先提出了反转LSH函数族的概念,并设计了一个切实有效的反转查询引导的位置敏感哈希函数族。基于这个新的函数族,本文提出了两个针对近似最远邻的外存算法RQALSH和RQALSH*。本文通过理论分析表明,RQALSH对于近似最远邻检索有理论保证。本文的实验结果表明,RQALSH和RQALSH*的性能,要明显优于业界领先的QDAFN和DrusillaSelect算法。对于高维c-近似最大内积问题,本文通过利用数据的分布和查询的位置信息,提出了一个基于同心超球的非对称的位置敏感哈希机制(Asymmetric LSH scheme based on Homocentric Hypersphere,简称H2-ALSH)。H2-ALSH机制对于近似最大内积检索具有理论保证,并且支持任意近似比例0<c<1。本文的实验结果表明,H2-ALSH机制可以有效提升查询的精度,并且H2-ALSH机制的效率明显胜过业界领先的Sign-ALSH和Simple-LSH算法。