多维数据近似检索的分层LSH索引算法模型研究

房华蓉

摘要：该文鉴于数据管理技术发展的前瞻性考虑，以多维数据为处理对象，探索高性能數据过滤器的若干理论和实现技术，针对假阳性和假阴性过高的问题，以及对时空效率的要求，设计了适合多维数据近似检索的分层LSH索引算法模型。

关键词：多维数据；布鲁姆过滤器；局部敏感哈希；分层局部敏感哈希索引

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2018）02-0213-03

随着互联网、电子商务等信息技术的高速发展，数据规模呈海量增长，多个领域已经或正在积累TB、PB甚至EB级的大数据[1，2]。如沃尔玛超市数据库超过2.5PB，每小时需要处理100余万条用户请求；社交网络Facebook存储了超过500亿张的照片；互联网数据资源每两年翻一番；全球的工业设备、汽车、电表上有无数的传感器，随时产生多种多样的海量数据信息。这些都标志着大数据时代已经来到，学术界、工业界和政府都已经开始密切关注大数据及其检索问题。

2012年美国奥巴马政府发布了“Big Data Research and DevelopmentInitiative”[3]，投资2亿以上美元，计划在科学研究、环境、生物医学等领域利用大数据技术进行突破性研究，将“大数据战略”上升为国家战略。我国政府多部规划和项目指南都对“大数据”相关技术密切关注：《国家中长期科技发展规划纲要（2006-2020年）》提出“重点研究……海量信息处理及知识挖掘的理论与方法”；2014国家自然科学基金优先资助重点领域包括“大数据技术和应用中的挑战性科学问题”，并列出10个研究方向。

1 多维数据及其检索策略

信息存储空间的多元化给网络中数据资源的存储管理及新资源开发带来了新的挑战。大数据的存储与表示，大数据中知识快速且高效的挖掘是目前各互联网服务供应商关注的热点，普通网络用户也希望通过大数据获得更多的增值服务。数据量及数据复杂度急剧增长时，知识发现的难度及大大增加，计算量和响应时间也随之变化。研究与之对应的高效查询算法查找定位信息资源已经成为现代网络发展分布式信息共享中最常见的问题。精简结构的查询算法已经成为提升网络软件体系结构和完成大规模高效数据管理的关键。

由于大数据的数据体量巨大、类型繁多、价值大但有效信息比例低、要求处理速度快的特点，对当代信息传输、计算、存储以及面向各种应用的数据处理技术提出了前所未有的挑战。针对这些特征，学术界公认的大数据处理策略是先用过滤器快速过滤掉大部分无用的数据，留下可能有用的数据做进一步处理。但是，如何从静态或动态的海量数据中“提纯”出有价值的数据面临诸多困难，如：1）大数据时代的算法由于实时性的特点，其准确率不再是最主要指标，很多算法需要在实时性和准确率之间取得平衡；2）数据过滤必须更加谨慎，如果粒度过细，很容易将有用的信息过滤掉；如果过粗，又无法达到真正的清洗效果，因此需要在质和量之间仔细考虑和权衡。

大数据检索的实际应用中多采用近似查询，一般而言与目标距离越近，数据的价值就越高。为提高速度，可以设置一个多维数据过滤器，根据距离过滤掉大部分查询数据，少量剩下的数据可以再通过常规方法进一步处理，可以显著提高系统的整体性能。这个过滤器完成的就是近似成员查询（ApproximateMembership Query，AMQ），即回答“查询对象q是否接近于数据集合中的某个对象”。现有AMQ技术主要是结合局部敏感哈希（Locality Sensitive Hashing，LSH）和布鲁姆过滤器（Bloom Filter，BF）设计的，如DSBF和LSBF。不过布鲁姆过滤器存在假阳性错误，局部敏感哈希算法需要大量的哈希表来建立索引结构，这就导致了大量的内存消耗，查询时也会带来大量的I/O访问。此外，尽管LSH的查询时间效率已经比较高了，但是依然存在进一步优化的空间。典型DSBF和LSBF这两个技术都有一个限制，即它们仅能过滤给定距离的AMQ查询。因此研究BF和LSH算法的特性，针对BF及LSH的缺点提出改进方案或者提出性能更优的相似性检索算法具有重要的研究意义。为了提出性能及适应性更好的相似性检索算法，以优化LSH结构、提升AMQ的质量和效率：设计多维数据近似检索的分层LSH索引算法模型。

2 基于BF及LSH的不同维度数据检索技术

布鲁姆过滤器（Bloom Filter，BF）是由B.H.Bloom在1970提出的经典过滤器[4]，被广泛用在网络服务、数据包内容检测、信息检索、分布式数据库、协作缓存等领域。它对集合采用一个位串表示并能有效支持元素的哈希查找，对每个元素的表示只需要几个比特，是一种能够表示集合、支持集合查询的简洁数据结构，能够有效地过滤掉不属于集合的元素。布鲁姆过滤器结构的实质是将集合中的元素通过n个哈希函数映射到位串向量中，与传统的哈希查询算法中哈希存储表不同，布鲁姆过滤器中哈希表退化为一个位串，一个元素仅占用几个比特位。进行元素查询时，计算n个哈希函数，判断这个位串向量的n个对应比特位是否都为1。不过，布鲁姆过滤器作为一种集合查询的数据结构，在达到其高效简洁表示集合的同时，却存在可控的假阳性误判。

LSH技术是由P.Indyk等在1998年提出，它的思想是：先对数据集中的点进行哈希函数的映射，这样近距离点的冲突概率提高而远距离点的冲突概率降低。在查询时，将查询点按照相同的哈希函数哈希到桶中，然后取出桶中的所有点作为候选近似最近邻点，最后计算查询点与每个候选近似最近邻点的距离，通过该距离判断是否符合查询条件。使用哈希函数对整个数据集进行过滤，得到可能满足查询条件的点再计算距离，就避免点与数据集中所有点进行距离计算，提高了查询效率且无需降维。

2.1 单维数据布鲁姆过滤器

针对不同应用，布鲁姆过滤器有很多改进。计数布鲁姆过滤器CBF[5]将1位的比特扩展为3位或4位的计数器，能够处理元素删除操作。CBF可以正确地删除已经在集合中的元素，但如果这一先决条件不满足，就会产生假阴性（false negative）问题。为解决此问题，Guo等人[6]提出了一种新方案，在不减少0比特的情况下增加1比特，使得假阴性和假阳性一样减少。Time Decaying BF[7]在递减计数器值的同时也考虑时间因素。SBF[8]是另一个重复元素检测的解决方案，在SBF中0的预期分位数保持恒定，使得它适合在数据流中的重复检测，它还降低了假阳性和假阴性率。Space-code BF[9]关注测量精度、计算及存储复杂性之间的权衡。与标准的BF需要k次访问内存不同，Qiao等[10]提出Bloom-1只需要访问一次内存，他们还分析了不同的数据结构和性能，以获得查询代价和假阳性率都可接受的折中方案。endprint

2.2 低维数据布鲁姆过滤器

以上这些研究针对的是单维数据，而实际应用中，很多数据都是多维的。但目前多维布鲁姆过滤器研究还比较少，且主要集中在数据的集合判断问题。Guo等[11]提出了多维动态布鲁姆的过滤器（MDDBF）来判断多维数据是否属于一个集合，基本的想法是对于s维的集合，设置s个标准BF 过滤器。由于MDDBF方法失去了属性间的关联信息，将增加误报的概率。Xiao等[12]意识到这个问题，提出辅助结构捕捉所有属性的内在相关性。与MDDBF相比，能够处理多个属性，可以提供更快的查询服务，出现假阳性的概率要低得多，也节省了存储空间。联合多维布鲁姆过滤器（CMDBF）[13]新增一个用于表示数据整体的联合布鲁姆过滤器CBF，CMDBF中数据表示和查找分两步进行，即将MDBF的各属性的表示和查询作为第一步，第二步联合数据所有属性域，利用CBF完成数据整体的表示和查询确认。

以上这些多维布鲁姆过滤器的更新离不开原始数据，即将原始数据的各个维通过哈希运算后才能更新多維过滤器。但在实际应用中，为节省空间，一般只保留概要数据（即布鲁姆过滤器），于是无法根据某一属性删除的原始数据来更新过滤器。

2.3 多维数据的近似查询-LSH和BF的优化组合

传统算法中基于空间划分的树形检索算法，如各类树型算法，在检索对象低维度、低数据量的前提下，加速效果明显。随着数据维度的增加和数据量的加大，这些算法的加速效果明显降低。所以，面对高维度的海量数据，这些树形检索算法速度上的改进微乎其微，甚至还比不上暴力检索或者线性检索的速度。

目标函数中近邻关系确定是解决最近邻检索的速度瓶颈问题，有人提出近似的思想，把如果目标函数中的近近邻关系定为似最近邻，如此更改的原因是在多数情况下，近似最近邻的结果和最近邻是一致的，而且在大多数的应用场合下，近似最近邻同样也可以满足实际的需求。近似最近邻的概念最早是由Indyk和Motwani提出的[14]，近似最近邻的检索时间及数据容量成亚线性关系得到证明，他们舍弃釆用以往的基于空间划分的方法，比如树形分割法，提出了一种新的基于哈希索引的思想实现近似最近邻检索，即局域敏感哈希（LSH）。此算法的核心思想是设计几个哈希函数来映射数据点，每个哈希函数要能保证距离近的点被映射到同一个桶的概率（又叫碰撞概率）比距离远的点被映射到同一个桶的概率大得多；查询时，使用对应的哈希函数可以把询问点也映射到对应的桶中，检索到的桶中的点即为近邻点。基于这种映射思想，他们在汉明空间（{0，l}d）中提出了一种局域敏感哈希函数，跟以往的树形结构算法相比，他们用实验验证了这种算法的快速性。2004年，斯坦福大学的Indy等提出了基于P稳态分布的局域敏感哈希，成功地用在了原始的非汉明空间，即P范数空间。

LSH是一种近似的近邻检索算法，最近邻数据点的检索概率很高，但也不是绝对准确，有人通过使用多个哈希函数构建多个哈希表来提高检索的准确率，这样做的问题是存储空间浪费太大。为了解决这个问题， multi-probe LSH[15]连续探测多个可能包含查询对象的桶，而不是只探测一个桶，以提高空间和时间效率。Collision Counting LSH（C2LSH）[16]采用了多个LSH函数构造动态复合哈希函数，并设定碰撞阈值来提高精确度。BayesLSH[17]能迅速剪枝大多数的假阳性候选对象，显著提高处理的速度。

这些查询都具有多维、实时、且多数查询都不命中等三个特征。为提高速度，可以设置一个多维数据过滤器，根据距离过滤掉大部分查询数据，少量剩下的数据可以再通过常规方法进一步处理，可以显著提高系统的整体性能。这个过滤器完成的就是近似成员查询AMQ，即回答“查询对象q是否接近于数据集合中的某个对象”。现有AMQ过滤器主要是结合LSH和Bloom filter 设计的，如DSBF和LSBF。如今，LSH技术及其变种是高维空间检索最先进的索引技术之一。

DSBF首次综合LSH和BF来过滤AMQ查询，返回组成员的近似查询结果。它可以改善网络和数据库应用的速度和空间，从而避免很多代价昂贵的比较操作，如最近邻查询等。LSBF使用LSH 函数来构造BF过滤AMQ查询，LSBF还采用了额外的位向量来降低假阳性率。DSBF和LSBF这两个技术都有一个限制，即他们仅能过滤给定距离的AMQ 查询。然而，给定一个合适的距离并不容易，过大或过小的距离值，可能会导致不可接受的查询结果。一旦距离值被确定，就不能改变，除非根据原始数据重新构造过滤器。然而，为节省空间，原始数据一般并不保存。另外，这两种过滤器也占用较多的空间开销，错误率相对较大。

2.4 已有技术的不足

从上面分析可知：（1）单维数据过滤器的研究和应用相对比较充分；（2）低维数据过滤器的研究局限在判断数据是否在集合中，在没有原始数据支持下，无法根据某一属性删除数据的布鲁姆过滤器更新其余维度的过滤器（项目组成员在这个问题方面已经实现了2维数据的关联删除技术的研究，并已投稿国际顶级会议被录用）；（3）多维数据过滤器的过滤距离固定，无法支持多粒度的过滤距离；（4）多维数据的近似查询中LSH索引表建立时，耗费过多内存资源；查询时，频繁进行I/O操作，耗费过多的计算时间。

3 分层LSH索引算法模型

3.1 分层LSH算法流程

针对已有的结合BF和LSH在近似近邻检索算法，由于内存消耗过大和时空效率不高（频繁进行I/O处理）问题，提出了分层LSH索引算法流程如下：

1） 索引建立：首先对原始多维数据利用已有基于p稳定分布的哈希函数族G（多维哈希）进行局部敏感哈希到多个哈希表中，对每个数据在多哈希表散列的桶号进行编码，形成桶编号；然后对桶编号进行一维哈希散列到一维向量（BF）中，相邻数据点有着相近的桶编号，那么相近的桶编号散列到一维向量中也是相近位；再对一维向量中存放的桶编号散列的位进行地址合并，完成索引建立。endprint

2） 查詢处理：查询时，首先对查询点做多维哈希函数族的局部敏感哈希到多个桶，将这些桶中的数据作为其候选近邻数据点（这样可以避免假阳性偏高问题，如果相应桶中数据个数已达查询结果要求，则结束）；如果没有查找到足够的候选近邻则继续对桶编号散列到BF中位的近邻进行查询（这样可以避免假阴性偏高问题），直至查到查询目标。

3.2 分层LSH索引算法模型设计

结合传统LSH在近似近邻检索算法中，由于内存消耗过大、时空效率不高和假阳性、假阴性过多问题，我们提出了分层LSH索引算法流程，如图1所示。

分层LSH索引构建流程：对多维的原始数据进行多哈希函数的局部敏感哈希，先建立一个哈希表，每个哈希表对应哈希函数族G中随机选出[l]个g函数[g1，g2，...，gl]中的一个g函数，这个方法能大大提高近邻点的碰撞概率。而每个数据点散列到[l]个哈希表的不同桶中，对这些桶号进行编码形成查询数据的哈希桶编号，然后对这些哈希桶编号再进行一次一维哈希函数的散列，将散列地址映射到BF的有关位中。设计过程中，考虑到多维数据的近似性，近似数据的桶编号经过一维哈希函数的散列后的地址在BF中具有高概率的相邻性，因此可以考虑对BF的这些相邻位进行合并，完成索引的优化。

分层LSH中数据的查找流程：查找数据时首先对查询点进行哈希函数族的局部敏感哈希，将其映射到各哈希表的不同桶中形成其散列桶的桶编号，然后将这个桶编号对应的桶中数据作为候选近似查询目标，如果目标的数目达到了预期的查询数，就锁定这些数据作为候选查询点；如果没有达到，那么在查询点所对应的哈希桶编号再散列的BF位的相邻位所对的哈希桶编号的数据点也作为候选近邻成员。

4 小结

本文针对已有的结合BF和LSH在近似近邻检索算法进行了总结，基于已有技术的内存消耗过大和时空效率不高（频繁进行I/O处理）问题，提出了分层LSH索引算法设计分层LSH索引算法模型，既能避免假阳性和假阴性过高的问题，也能提升算法的时空效率。

参考文献：

[1] 王珊，王会举，覃雄派，等. 架构大数据：挑战、现状与展望[J]. 计算机学报，2011， 34（10）：1741-1752.

[2] 李建中，刘显敏. 大数据的一个重要方面：数据可用性[J]. 计算机研究与发展，2013， 50（06）：1147-1162.

[3] 孟小峰，慈祥. 大数据管理：概念、技术与挑战[J]. 计算机研究与发展，2013，50（01）：146-169.

[4] B.H.Bloom. Space/Time Trade-Offs in Hash Coding with Allowable Errors. Comm. ACM， 1970， 13（7）：422-426.

[5] L.Fan， P. Cao， J. Almeida， and A. Z. Broder. Summary Cache： A Scalable Wide-Area Web Cache Sharing Protocol.IEEE/ACM Trans. Networking.2000，8（3）：281-293.

[6] D.Guo， Y. Liu， X. Li， P. Yang.False Negative Problem of Counting Bloom Filter. IEEE Trans.Knowl.Data Eng.2010， 22（5）：651-664.

[7] K.Cheng，L.Xiang， M.Iwaihara， H.Xu， and M.M.Mohania. Timedecaying Bloom filters for Data Streams with Skewed Distributions. in Proc. 15th International Workshop on Research Issues in Data Engineering： Stream Data Mining and Applications. Washington， DC， USA： IEEE Computer Society，2005： 63-69.

[8] F.Deng and D. Rafiei. Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters. in Proc. 2006 ACM SIGMOD International Conference on Management of Data.New York， NY，USA： ACM， 2006： 25-36.

[9] A.Kumar，J.Xu，J.Wang，O.Spatschek， and L.Li.Space-code Bloom Filter for Efficient Per-flow Traffic Measurement. In Proc. IEEE INFOCOM.Hongkong， China， 2004（3）：1762-1773.

[10] Y.Qiao， T.Li， S.Chen.Fast Bloom Filters and Their Generalization.IEEE Transactions on Parallel and Distributed Systems. 2014， 25（1）：93-103.

[11] D.Guo，J. Wu， H.Chen， and X. Luo. Theory and Network Application of Dynamic Bloom Filters.Proc.IEEE INFOCOM， 2006.

[12] B. XIAO， Y HUA. Using Parallel Bloom Filters for Multiattribute Representation on Network Services.IEEE Trans on Parallel and Distributed Systems， 2010， 21（1）：20-32.

[13] 谢鲲， 秦拯， 文吉刚， 等. 联合多维布鲁姆过滤器查询算法[J]. 通信学报，2008， 29 （1）：56-64.

[14] Indyk Piotr，andMotwani Rajeev， Approximate nearest neighbors： towards removing the curse of dimensionality. In the thirtieth Annual ACM Symposium on Theory of Computing，1998，pp.604-613.

[15] Q.Lv，W.Josephson， and Z. Wang. Multi-Probe LSH： Efficient Indexing for High-Dimensional Similarity Search. In VLDB， pages 950-961， 2007.

[16] J.Gan，J.Feng， and Q. Fang. Locality-sensitive Hashing Scheme Based on Dynamic Collision Counting.In SIGMOD， pages 541-552， 2012.

[17] V.Satuluri， and S. Parthasarathy. Bayesian Locality Sensitive Hashing for Fast Similarity Search. In VLDB， pages 430-441， 2012.endprint