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

相似性连接查询,即查找相似的数据对象对,具有广泛的应用领域,例如相似网页检测、实体解析、数据清洗和相似图像检索等。相似性连接查询是当前大数据处理领域的热点问题之一。讨论了相似性连接查询面临的挑战;根据不同的标准对现有的相似性连接查询进行了分类;总结并比较了现有的字符串、集合、向量和图相似性连接算法;探讨了今后的研究重点和发展趋势。     

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

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

核聚变实验中相似波形智能检索方法研究综述

随着核聚变实验数据量的与日俱增,需要针对相似波形开发智能检索方法来加速数据识别和分析。波形的相似性查询包括全序列相似查询和子序列相似查询2个方面。日本的LABCOM小组和欧盟的JET-EFDA小组在这方面做了大量的研究工作,并取得一系列成果。通过详细评述波形相似性查询方法的基本思想和关键技术,对这些方法进行分析和比较,总结了这些方法的优点和不足,并对进一步的研究方向作出了展望。      

基于语义的网络大数据组织与搜索

随着信息技术的飞速发展,网络空间中出现海量异构的数据资源,网络大数据逐渐引起了人们的关注.从网络大数据中发现并获取用户所需的数据资源,需要对网络大数据进行有效地组织管理并进行基于数据语义的相似搜索.为此,需要从网络数据资源中抽取其特征/属性构造高维语义空间,并将数据资源及用户查询信息抽象为语义空间中的特征向量或高维点,进而通过比较特征向量间夹角余弦值或高维点之间的距离来衡量语义相似性.高维索引技术可以对高维语义空间中的数据资源进行有效组织管理,实现基于数据语义的相似性搜索;而降维技术可以消除语义空间维数过高所引发的“维灾”影响.文中对现有的高维数据索引及降维技术进行了系统的综述,然后介绍了现有的基于分布式技术实现高维数据语义相似性搜索的研究工作,最后并展望了未来工作.     

基于关系数据库有效地实现RPE查询

各种XML查询语言的共同特点就是利用正则路径表达式(RPE)来导航XML文档的查询。本文结合我们提出的一种新的XML数据的关系存储模式，对有效地实现RPE查询的相关研究工作进行了总结，并提出了两个有效地实现包含连接的索引改进归并连接算法。算法采用索引定位技术、短路技术和预侦技术来减少连接代价。因此，不仅能够在当前上下文计算环境下有效地实现包含连接的计算，而且能够大量地避免包含连接中不必要的扫描和搜索。     

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

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

基于本体和用户相关反馈的扩展查询研究

描述了一种扩展查询(QE)的新方法,这是一种连接用户相关反馈和本体的混合扩展查询技术,有两大贡献：一是连接了用户相关反馈和本体技术,二是采用FirteX作为实验平台。与目前广泛应用的基于余弦相似性的扩展查询技术相比,实验结果表明方法平均精度达到15%,高于基于余弦相似性的扩展查询技术的13%,并且将平均反馈率提高到了16%。     

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

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

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

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

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

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

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

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

激光散乱点云K最近邻搜索算法

针对激光散乱点云的数据量大,且具有面型的特点,为降低存储器使用量,提高散乱点云的处理效率,提出了一种散乱点云K最近邻（KNN）搜索算法。首先,利用多级分块、动态链表的存储方式,只存储非空的子空间编号。对相邻子空间进行3进制编码,利用编码的对偶关系,建立相邻子空间之间的指针连接,构造出包含KNN搜索所需的各类信息的广义表,然后再搜索KNN。KNN搜索过程中,在计算被测点到候选点距离时,直接删除筛选立方体内切球之外的点,可将参入按距离排序的候选点数减少为现有算法的一半。依赖K值和不依赖K值的分块原则,均可计算不同的K邻域。实验结果表明,该算法不仅具有低的存储器使用量,而且具有较高的效率。     

The <Emphasis Type="Italic">k</Emphasis>-Nearest Neighbour Join: Turbo Charging the KDD Process

The similarity join has become an important database primitive for supporting similarity searches and data mining. A similarity join combines two sets of complex objects such that the result contains all pairs of similar objects. Two types of the similarity join are well-known, the distance range join, in which the user defines a distance threshold for the join, and the closest pair query or k-distance join, which retrieves the k most similar pairs. In this paper, we propose an important, third similarity join operation called the k-nearest neighbour join, which combines each point of one point set with its k nearest neighbours in the other set. We discover that many standard algorithms of Knowledge Discovery in Databases (KDD) such as k-means and k-medoid clustering, nearest neighbour classification, data cleansing, postprocessing of sampling-based data mining, etc. can be implemented on top of the k-nn join operation to achieve performance improvements without affecting the quality of the result of these algorithms. We propose a new algorithm to compute the k-nearest neighbour join using the multipage index (MuX), a specialised index structure for the similarity join. To reduce both CPU and I/O costs, we develop optimal loading and processing strategies.     

大数据查询综述

大数据具有传统数据所不具有的数量大、种类多、速度快、真实性等特点,传统的数据查询技术满足不了日益增长的大数据查询需求,大数据查询技术应运而生并迅速发展。从大数据查询的角度出发,着重分析大数据存储技术、大数据处理平台以及大数据查询引擎等。分别对比介绍传统关系型数据库、NoSQL、NewSQL和它们在大数据查询处理上的应用,介绍当前流行的大数据处理平台以及在这些平台上运行的大数据查询引擎,对其优缺点进行了综合阐述。      

高维不确定数据的子空间聚类算法

如何降低不确定数据对高维数据聚类的影响是当前的研究难点。针对由不确定数据与维度灾难导致的聚类精度低的问题,采用先将不确定数据确定化,后对确定数据聚类的方法。在将不确定数据确定化的过程中,将不确定数据分为值不确定数据与维度不确定数据,并分别处理以提高算法效率。采用结合期望距离的K近邻（KNN）查询得到对聚类结果影响最小的不确定数据近似值以提高聚类精度。在得到确定数据之后,采用子空间聚类的方式避免维度灾难的影响。实验结果证明,基于Clique的高维不确定数据聚类算法（UClique）在UCI数据集上有较好的表现,有良好的抗噪声能力和伸缩性,在高维数据上能得到较好的聚类结果,在不同的不确定数据集实验中能够得到较高精度的实验结果,体现出算法具有一定的健壮性,能够有效地对高维不确定数据集聚类。     

基于私有云的混合型大数据匿名化加密仿真

针对目前混合型大数据匿名安全方法的用户查询相似度偏低,导致匿名数据可用性不理想的问题,提出基于私有云的混合型大数据匿名化加密方法.设计混合型大数据平台架构,将物理服务器和私有云主机的大数据平台相混合,以提高其可扩展性能.利用信息损失指标对混合数据实现泛化处理.构建用户查询项模型,通过散度进行查询项的相似度运算,相似程度...     

面向高速公路大数据的短时流量预测方法

针对高速公路传统的短时交通流预测方法适用数据规模小、全网预测效率较低、数据的时空关系被忽视等问题，提出一种结合了K近邻（KNN）模型且面向高速大数据的短时交通流预测方法。首先，对模型的K值和距离度量进行调优，利用交叉验证进行模型参数的对比实验；然后，考虑数据内在的业务时空关联，建模基于时空特性的特征向量；最后，在大数据环境下建立回归预测模型，以最优参数的模型实现预测。实验结果表明，与传统时间序列模型相比，所提方法一次可预测出全站点的流量，单次运行速度快，效率提高了77%，平均绝对百分比误差（MAPE）和绝对百分比误差中位数（MDAPE）均有明显减低，且具有良好的水平扩展性。