大数据相似性连接查询技术研究进展

为了深入理解和全面把握大数据相似性连接查询技术的研究进展，更好地促进其在图片聚类、实体解析、相似文档检测、相似轨迹检索等领域的广泛应用，对大数据相似性连接查询技术相关研究工作进行了深入调研和分析。首先对相似性连接查询的基本概念进行了介绍，然后分别对集合、向量、空间数据、概率数据、字符串等不同类型大数据的相似性连接查询相关研究工作进行了深入研究，对其优缺点进行了分析和总结。最后，指出了大数据相似性连接查询面临的若干挑战性问题及未来的研究重点。     

基于MapReduce框架的海量数据相似性连接研究进展

海量数据相似性连接作为海量数据处理的基本操作,在文本聚类、剽窃检测、实体解析等研究领域具有重要作用.另一方面,MapReduce编程模型因为具有良好的可扩放性、容错性和易用性,被广泛地应用于海量数据处理.因此,基于MapReduce框架的海量数据相似性连接查询技术成为海量数据处理领域的热点问题之一.首先,概括了海量数据固有特点和MapReduce编程框架的缺陷给现有相似性连接查询技术带来的巨大挑战;其次,提出了海量数据相似性连接的定义,按3种不同的分类标准对其进行了分类;接着,重点分析了集合、字符串和向量数据类型的海量相似性连接查询最新技术,并从效率和适用范围等方面分别对这些技术进行了比较;最后,讨论了海量数据相似性连接查询技术亟待解决的关键问题,并提出了一些有前景的解决方案.     

基于MapRed uce的增量式数据集的相似性连接

相似性连接,即利用相似函数度量数据之间的相似程度,满足条件后进行连接操作。MapReduce框架下已存在很多相似性连接算法,但仍然存在一些不足,如大量的索引加大时间、空间的开销;现有算法不能有效地完成增量式数据集的相似性连接等。针对海量增量式数据集进行了研究,采用抽样技术得到有效中枢,形成更为合理的分区,建立分区索引和分配原则,完成新增数据的相似性连接操作。实验证明,该算法能够有效地解决海量增量式数据集的相似性连接问题,验证了分区索引的建立,可以提高新增数据的相似性连接操作的效率。     

基于卡方分布的高维数据相似性连接查询算法

为了解决高维数据相似性连接查询中存在的维度灾难和计算代价高等问题,基于p-稳态分布,将高维数据映射到低维空间。根据卡方分布的性质,证明了如果低维空间的距离大于kε,则原始空间距离大于ε的概率具有一定的下界,从而可以在低维空间以较低的计算代价进行有效过滤。在此基础上,提出了基于卡方分布的高维数据相似性连接查询算法。为了进一步提高查询效率,提出了基于双重过滤的高维数据相似性连接查询算法。利用真实数据集进行了实验,实验结果表明所提方法具有较好的性能。基于卡方分布的相似性连接查询算法召回率可以达到90%以上。基于双重过滤的相似性连接查询算法可以进一步提高性能,但是会损失一定的召回率。对时间性能要求比较高、对召回率要求不太严格的查询任务可以采用基于双重过滤的相似性连接查询算法;反之,可以采用基于卡方分布的相似性连接查询算法。     

基于实体的相似性连接算法

按照元组描述的实体对其进行组织和查询处理,是一种管理劣质数据的有效方法.考虑到同一个实体的同一属性存在多个描述的值,因此,基于实体的数据库上的连接是支持多个值的相似性连接.与字符串的相似性连接相比较,实体的相似性连接在数据清洗、信息集成、模糊关键字查询、诈骗检测和文本聚集等领域有着更好的应用效果.通过建立双层索引结构,提出了实体数据库上相似性连接算法ES-JOIN.同时,该方法适用于解决集合中字符串模糊匹配的相似性连接问题,而传统的集合相似性连接只针对集合中元素精确匹配的情况.为了加速连接,还提出了过滤措施对算法进行优化,进一步给出了优化算法OPT_ES-JOIN.实验验证了ES-JOIN算法和OPT_ES-JOIN算法具有很好的效率和可扩展性.实验结果表明,过滤措施具有很好的过滤效果.     

序列数据相似性查询技术研究综述

序列数据在文本、Web访问日志文件、生物数据库等应用中普遍存在,对其进行相似性查询是一种提取有用信息的重要手段.近年来,随着各种科学计算的发展和序列数据的大量产生,序列相似性查询已经成为数据分析领域一个研究热点.其涉及到的几个重要问题有面向各种应用领域的相似性度量及其相互之间的关系;随机序列数据中距离分布的统计信息及其对分析查询算法性能的作用;在大规模数据中,各种高效回答相似性查询的关键技术及各自的优缺点比较.总结了序列数据的分类和特点,给出了几种序列数据相似性度量和随机序列之间距离分布的统计信息,并进一步分析了这些度量之间的关系.接着给出了几种序列相似性查询的类型,以及序列相似性查询要解决的核心问题.在此基础上,针对各种序列相似性查询关键技术进行分类和评价.最后,讨论了关于序列数据相似性查询研究所面临的挑战,并归结了未来的研究方向.     

一种序列模式的相似性查询算法

数值型序列在很多应用中存在,如超市的POS销售记录和证券交易所的股票买卖数据等.在此类数据中查询与给定序列模式相似的子模式具有重要的现实意义.提出一种趋势融合的序列相似性查询算法NSS_QA,首先对所有序列进行单调区间的“融合”处理,然后根据各区间的长度比例和幅度比例产生序列模式的候选集,最后定义了一种新的相似性度量来...     

双缀过滤的大数据相似性连接处理算法

相似性连接技术是实体识别和数据集成的关键技术之一,是挖掘数据中有价值信息的重要手段。随着大数据发展,传统的集中式相似性连接已经无法满足人们对数据处理的时效性需求,并且利用分布式计算可以提高相似性连接的执行效率。因此,深入研究了基于Spark的分布式相似性连接处理算法。针对仅使用后缀位置信息过滤方法的不足,提出了利用一条记录前缀与另一条记录后缀间共同元素位置信息来进行过滤的分布式相似性连接PSJoin,提高了相似性连接的处理效率,减少了相似性连接的执行时间。同时,针对基于权重的相似度连接算法的过滤问题,结合双缀过滤原理,通过一条记录前缀共同元素之后的第一个元素的权重与另一条记录后缀中元素权重大小的关系,提出了基于双缀过滤的分布式权重相似性连接WTPSJoin。为面向大数据的相似性连接计算提供了两种可靠的解决方案。两种算法在多数据源混合数据集上进行测试实验,实验结果表明,所提算法相对于已有的过滤算法过滤效果好,执行时间少,同时具有良好的加速比。     

RM树:一种支持字符串相似性操作的索引

字符串相似性操作在很多领域中被广泛应用,如数据清洁、信息集成等.现有研究工作主要为基于q-Gram和倒排索引的内存方法,在处理大量数据时具有以下缺点:内存消耗大、更新效率低、支持操作类型有限.现有的外存索引Bed树无法将相似的字符串聚类,在查询处理过程中导致了较大的I/O代价.该文设计了支持多种字符串相似性操作的RM树...     

利用反馈的时序模式挖掘算法研究

针对时序数据相似性挖掘方法进行研究，提出一种利用反馈的时序数据相似性挖掘算法，由用户赋予各初始范围查询得到的相似序列相应的权值，通过反馈与给定序列叠加产生新的查询序列，再次进行范围查询，获得相似序列，将该算法用于某钢铁企业的电力负荷时序数据，计算结果表明了算法的有效性。     

Similarity query support in big data management systems

Similarity query processing is becoming increasingly important in many applications such as data cleaning, record linkage, Web search, and document analytics. In this paper we study how to provide end-to-end similarity query support natively in a parallel database system. We discuss how to express a similarity predicate in its query language, how to build indexes, how to answer similarity queries (selections and joins) efficiently in the runtime engine, possibly using indexes, and how to optimize similarity queries. One particular challenge is how to incorporate existing similarity join algorithms, which often require a series of steps to achieve a high efficiency, including collecting token frequencies, finding matching record id pairs, and reassembling result records based on id pairs. We present a novel approach that uses existing runtime operators to implement such complex join algorithms without reinventing the wheel; doing so positions the system to automatically benefit from future improvements to those operators. The approach includes a technique to transform a similarity join plan into an efficient operator-based physical plan during query optimization by using a template expressed largely in the system’s user-level query language; this technique greatly simplifies the specification of such a transformation rule. We use Apache AsterixDB, a parallel Big Data management system, to illustrate and validate our techniques. We conduct an experimental study using several large, real datasets on a parallel computing cluster to assess the similarity query support. We also include experiments involving three other parallel systems and report the efficacy and performance results.     

实体数据库中多相似连接顺序选择策略

按照元组描述的实体对其进行组织和查询处理是一种管理劣质数据的有效方法。考虑到同一个实体的同一属性存在多个描述值,因此基于实体的数据库上的连接是支持多个值的相似性连接。由于多表连接操作的连接顺序对连接性能有着重要的影响,研究了实体数据库上多表连接顺序选择方法,采用基于实体的马尔可夫链蒙特卡洛(Markov chain Monte Carol,MCMC)方法估计出实体数据库的相似性连接操作的结果大小,并以连接结果大小和有无索引作为主要代价,提出了基于实体的多连接顺序优化策略。进一步,通过实验证明了估计连接结果大小的算法在大规模数据上有着显著的优势。     

Ed-Sjoin:一种优化的字符串相似连接算法

相似连接(similarity join)在数据清洗、生物信息、模式识别等应用领域中有着广泛应用,其中基于编辑距离的字符串相似连接是一种重要的相似连接.尽管当前有一些基于编辑距离的字符串连接算法提出,然而,当前的算法存在着大量的多余计算,影响了算法的效率.为了高效计算基于编辑距离的字符串连接,提出了一种优化的算法Ed-sjoin,分别从优化筛选算法和基于前缀的重复消减策略两方面对算法进行优化,这些优化策略可以实现更加有效的剪枝,并且避免了部分重复计算,从而加速算法的执行.实验结果表明,提出的方法优于现有方法.     

多元飞行数据相似模式查询

飞行数据是一种典型的多元时间序列数据,基于奇异值分解提取飞行数据序列的特征,通过奇异值距离过滤获得相似模式查询的候选集,依据线性空间中的坐标变换原理构造多元时间序列的相似性度量模型,从而实现候选集上的精确匹配并获得最终的结果集。给出了相似子序列的冲突消解策略,深入分析了查询的完备性问题,指出该方法可能导致误判或成为误判的根源,提出融入先验规则来减少误判并提高查询效率的方法。在真实飞行数据上的实验结果验证了方法的有效性。     

面向移动计算环境的单连接查询处理模式研究

在移动计算环境下，基于准确的操作代价估算结果来选择合适的连接查询处理模式，可以减少数据的传输量和移动设备的能量消耗。探讨了该环境下移动设备能量消耗的一个新的非对称特征，提出了一种操作代价估算方法，并从数据传输量和能量消耗两个方面对连接查询处理模式进行了代价估算和性能比较，提出了4个实用准则，以指导连接查询处理模式的选择。试验结果充分论证了估算方法和准则的正确性，且比现有同类估算模型和结论具有更加广泛的应用范围。     

图像重排序中与查询相关的图像相似性度量

现今的图像搜索引擎主要利用图像周围文本信息为图像排序,根据图像内容重排序可以进一步提高搜索性能。图像相似性的度量对重排序算法的性能至关重要。然而已有的相似性度量没有考虑针对不同的查询,图像的相似性应该不同。提出一种与查询相关的相似性度量方法,将基于全局特征的相似性,基于局部特征的相似性,以及视觉单词同时出现率融合到一个迭代算法中,挖掘出与查询相关的图像信息,计算图像相似性。在Bing图像搜索引擎上的实验结果证明本文提出的相似性度量方法优于基于全局特征,局部特征,或它们线性组合的相似性。     

基于相关反馈的时间序列相似性搜索

传统的基于相关反馈的时间序列相似性搜索是将正反馈和负反馈融合在一起创建新查询向量,这样并没有充分利用负反馈序列的价值,而且容易对初始查询向量进行过多的更改。本文提出一种基于反馈的时间序列相似搜索方法,将反馈的正相关和负相关序列分开处理,最终的相似序列不但要与正相关序列相似,还要尽量与负相关序列不相似。在UCR数据集上的实验结果表明,本文提出的相似搜索方法与传统的基于反馈的相似搜索方法相比,在某些数据集上可以提高查询的准确率以及查全率。