大数据下近似成员关系查询方法研究进展!.pdfVIP

大数据下近似成员关系查询方法研究进展 5211) 胡会南陈华辉(宁波大学浙江宁波31 摘 要：近似成员关系查询(ApproximateQuery，AMQ)要快速回答类似“数据对象q是否 Membership 掘、模式识别、生物检测等领域有许多应用。对AMQ问题及其处理方法进行了综述介绍。+LAMQ的定义出 发，对处理AMQ问题的相关基础技术进行了介绍，讨论了目前主要的AMQ算法，分析比较了各算法的区别 和优缺点，最后探讨了AMQ处理中尚需进一步研究的若干问题。 关键词：大数据；近似成员关系查询；布鲁姆过滤器；位置敏感哈希 1 引言 AMQ的基本做法是对给定的数据对象q，判断在q的 随着云计算、物联网、社交媒体等新兴技术的快 一个小的范围内是否有Js的元素，若有，则认为口是S 速发展，全球的数据量越来越大，也产生了越来越多 的一个近似成员。 的大数据检索、分析和挖掘的技术需求。成员关系查 AMQ可应用于许多实际领域中。如在图像处理 中，判断一图像是否和已有的图像数据库中某一图 询(MembershipQuery，MQ)，即对给定的大数据集合 像相似；在生物信息学中，医生需要判断一种罕见疾 Js和数据对象g，测试g是否属于．s，是大数据处理中的 一种有用操作。如在垃圾邮件过滤系统中，若已掌握 病是否和已知的疾病具有相似的特征，达到对病人 一个“好”的邮件地址集合，则对新到来的一封邮件， 的快速针对性治疗；在网络安全中，判断某个用户的 通过测试其发件地址是该集合的成员，可认定该邮 行为特征和过去入侵者的特征是否相似等。 件不是垃圾邮件。 本文对解决AMQ问题的主要方法进行了综述和 解决MQ问题的一个简单方法是对集合S构造的分析。第2节概括了与AMQ算法有关的技术，第3节首 哈希表进行哈希查找。而当集合s非常大，存储空间 先分析了早期传统的AMQ方法，然后根据AMQ算法 有限时，布鲁姆过滤器(Bloom 应用的对象和问题背景的不同，对近年来使用LSH与 Filter，BF)是解决MQ 问题的一种经典方法。BF是一种高效的数据结构，利 BF结合技术解决的AMQ问题进行了综述，第4节讨论 用位数组简洁地表示元素在集合中是否存在，通过 了AMQ算法的比较与分析，第5节展望了AMQ问题进 引入极少的假阳性错误换取存储空间的极大节省。 一步的研究方向。 经典BF只能用来快速地判断某一数据是否是集 合S的一个精确元素，但无法判断在s中是否有近似 2 AMQ算法相关技术 的成员。已有研究工作基于BF提出了近似成员2．1 AMQ问题的相关概念 MembershipQuery，AMQ)定义1(AMQ)给定数据集合s和参数r，对于查 关系查询(Approximate r’1月c] 技术“。’‘“。AMQ要回答类似“数据对象q是否和给定 的大数据集合S中的至少一个元素相似”的问题。 一个近似成员，即g对集合s的AMQ查询结果是阳性 万方数据 圈蔓鋈耻函幽iQ。 塑塑坚! 的，其中r≥D，dist是距离函数。 的基本思想是通过随机哈希函数将每个数据映射成 一个位数组中的一位，查询时只要判断q映射的比特 从AMQIhq题定义中得知，AMQI司题解决查询对 象q是否是5中任意成员的近邻。例如图l中，对于集位是否为l即可。由于哈希函数的冲突，同一位可能 被多次置1，这将导致某个元素不属于S而误判为属