基于划分的增量式字符串相似性连接方法

字符串相似性连接是数据质量管理的基本操作,也是数据价值发现的关键步骤。针对目前已有的方法不能满足面向大数据的增量式处理需求的问题,提出一种面向流式数据的增量式字符串相似性连接方法——Inc-Join,并对方法的索引技术进行了优化。该方法以Pass-Join字符串连接算法为基础,首先,采用字符串划分技术将字符串划分成多个互不相交的子串;然后,建立字符串的反向索引列表并将其作为状态;最后,新增数据只需根据状态进行相似性计算,每次连接操作结束后都对状态进行更新。实验结果表明,Inc-Join方法在不影响连接准确率的同时,有效将长、 短字符串重复匹配次数减少为√n(n是批处理方式的匹配次数)。 实验对3种数据集进行处理,发现使用批处理方式进行相似性连接的响应时间是Inc-Join的1至4.7倍,并呈现急剧递增的趋势;而且优化后Inc-Join方法的响应时间最小只占优化前的3/4,并随处理数据的增多所占比例越来越小。同时优化后的Inc-Join不需要保存状态,再一次减小了算法执行的时间和空间开销。     

Part-Join:基于划分的字符串相似性连接

目前,已有许多高效的字符串相似性连接算法被提出,但是这些算法在过滤的过程中利用的往往是字符串本身的局部信息,而忽略了字符串集合的整体信息,故性能没有得到充分的提高.为此,提出了一种基于划分的算法Part-Join,它从频率向量、字母表、频率分布三方面对数据集进行子集划分,并给出子集间的过滤策略用于排除不相似的字符串对.扩展实验表明,Part-Join比已有算法Pass-Join效率提高了10％ ～ 15％.     

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

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

一种基于文档拓扑的相似性搜索算法

从海量文档中快速有效地搜索到相似文档是一个重要且耗时的问题。现有的文档相似性搜索算法是先找出候选文档集,再对候选文档进行相关性排序,找出最相关的文档。提出了一种基于文档拓扑的相似性搜索算法——Hub-N,将文档相似性搜索问题转化为图搜索问题,应用相应的剪枝技术,缩小了扫描文档的范围,提高了搜索效率。通过实验验证了算法的有效性和可行性。     

Efficient similarity search within user-specified projective subspaces

Many applications — such as content-based image retrieval, subspace clustering, and feature selection — may benefit from efficient subspace similarity search. Given a query object, the goal of subspace similarity search is to retrieve the most similar objects from the database, where the similarity distance is defined over an arbitrary subset of dimensions (or features) — that is, an arbitrary axis-aligned projective subspace — specified along with the query. Though much effort has been spent on similarity search in fixed subspaces, relatively little attention has been given to the problem of similarity search when the dimensions are specified at query time. In this paper, we propose new methods for the subspace similarity search problem for real-valued data. Extensive experiments are provided showing very competitive performance relative to state-of-the-art solutions.     

Fast similarity join for multi-dimensional data

The efficient processing of multidimensional similarity joins is important for a large class of applications. The dimensionality of the data for these applications ranges from low to high. Most existing methods have focused on the execution of high-dimensional joins over large amounts of disk-based data. The increasing sizes of main memory available on current computers, and the need for efficient processing of spatial joins suggest that spatial joins for a large class of problems can be processed in main memory. In this paper, we develop two new in-memory spatial join algorithms, the Grid-join and EGO*-join, and study their performance. Through evaluation, we explore the domain of applicability of each approach and provide recommendations for the choice of a join algorithm depending upon the dimensionality of the data as well as the expected selectivity of the join. We show that the two new proposed join techniques substantially outperform the state-of-the-art join algorithm, the EGO-join.     

一种基于PageRank的文献相似性搜索算法

在分析了PageRank算法基础上,提出了PageRank应用于科技文献相似性搜索的可行性,针对PageRank的不足提出了一种改进算法,该算法结合了对文献内容和文献间的引用关系的分析,综合计算文献间相似度,提高了搜索结果的准确率,并通过实验验证了算法的有效性和可行性。     

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

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

基于本体相似的Web服务搜索

随着越来越多的Web服务被提交到UDDI注册中心注册,搜索一个合适的Web服务开始变得和在互联网上找到一个合适的页面同样困难。现有的技术主要是通过关键字匹配的技术来对UDDI注册中心Web服务的描述信息进行检索。但鉴于Web服务描述信息非常稀疏的特点,传统的信息检索技术并不能得到很好的效果,因此提出了基于本体的Web服务检索技术。在已有的对Web服务检索流程的改进的基础上,充分利用了从UDDI注册中心得到的Web服务描述信息,用本体来描述其内部的关系,并在此基础上应用本体相似技术来比较和匹配Web服务描述信息。     

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

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

外存中高效的字符串相似性查询处理

字符串相似性查询是众多应用的基础操作,如数据清洁、拼写校验、生物信息学和信息集成等.随着数据的爆炸性增长,大规模字符串数据日益普遍,现代的信息系统中也广泛使用字符串作为数据的表达形式.现有支持字符串相似性查询的方法大多是基于q-gram的内存倒排索引,在处理大规模字符串集合会消耗无法忍受的内存容量,甚至在数据量过大时造成内存容量不足而无法支持查询处理.现有的外存倒排索引Behm-Index在查询的过滤阶段只支持少数过滤器,不能有效地减少查询I/O代价.提出了LPA-Index：一种支持长度过滤器和位置过滤器的外存倒排索引,并通过选择查询时使用的倒排表来有效地降低查询I/O代价.实验结果表明,与现有性能最好的外存索引Behm-Index相比,LPA-Index能够大幅降低查询的I/O代价,获得了更短的查询响应时间.     

一种高效的多变量时间序列相似查询算法

为了高效地执行多变量时间序列（MTS）相似查询,提出一种基于距离的索引结构（Dbis）相似查询算法。采用主成分分析方法对MTS数据进行降维处理;聚类MTS主成分序列,选择每类质心作为参考点;依据参考点将每类变换到一维空间,这样可以利用B+ 树结构进行索引查询;MTS序列比较相似采用的是扩展的Frobenius范数（Eros）。通过对股票数据集实验验证了Dbis算法的高效性。     

Adaptive similarity search for the retrieval of rare events from large time series databases

Improving the recall of information retrieval systems for similarity search in time series databases is of great practical importance. In the manufacturing domain, these systems are used to query large databases of manufacturing process data that contain terabytes of time series data from millions of parts. This allows domain experts to identify parts that exhibit specific process faults. In practice, the search often amounts to an iterative query–response cycle in which users define new queries (time series patterns) based on results of previous queries. This is a well-documented phenomenon in information retrieval and not unique to the manufacturing domain. Indexing manufacturing databases to speed up the exploratory search is often not feasible as it may result in an unacceptable reduction in recall. In this paper, we present a novel adaptive search algorithm that refines the query based on relevance feedback provided by the user. Additionally, we propose a mechanism that allows the algorithm to self-adapt to new patterns without requiring any user input. As the search progresses, the algorithm constructs a library of time series patterns that are used to accurately find objects of the target class. Experimental validation of the algorithm on real-world manufacturing data shows, that the recall for the retrieval of fault patterns is considerably higher than that of other state-of-the-art adaptive search algorithms. Additionally, its application to publicly available benchmark data sets shows, that these results are transferable to other domains.     

基于PPR的煤矿瓦斯监测数据相似搜索方法

研究基于时间序列相似搜索技术的煤矿瓦斯涌出分析新途径,提出基于PPR的煤矿瓦斯监测数据相似搜索方法。实验采用玉华煤矿的真实煤矿瓦斯监测数据,评价指标为信息损失量及相似查询效率。与基于离散傅立叶变换(DFT)和离散小波变换(DWT)的时间序列相似搜索算法的对比实验显示：在相同压缩比下,3种方法的信息损失相近;但是基于PPR的相似搜索算法的平均查询效率分别比基于DFT和基于DWT方法高32%和34%。因此PPR算法适合用于瓦斯监测数据相似搜索。     

异构信息网中基于元路径的动态相似性搜索

现有的相似性搜索算法通常没有考虑时间因素,为此,提出一种异构信息网中基于元路径的动态相似性搜索算法PDSim。PDSim算法首先计算给定元路径下实体的链接矩阵,得到实体之间的元路径实例数比值,同时基于建立时间的不同,计算其时间差异度;在此基础上针对给定的元路径,获得异构信息网中动态相似性的度量。在多个相似性搜索实例中,PDSim能够捕获到实体随时间变化而产生的兴趣的变化;应用于聚类时,相对于PathSim和PCRW方法,其标准互信息聚类精度可以提高0.17%~9.24%。实验结果表明,PDSim方法与传统的基于链接的相似性搜索算法相比,显著提高了异构信息网中动态相似性搜索的效率和用户满意度,是一种研究实体随时间而发生动态变化的相似性搜索方法。     

融合《知网》和搜索引擎的词汇语义相似度计算

针对当前《知网》的词语语义描述与人们对词汇的主观认知之间存在诸多不匹配的问题,在充分利用丰富的网络知识的背景下,提出了一种融合《知网》和搜索引擎的词汇语义相似度计算方法。首先,考虑了词语与词语义原之间的包含关系,利用改进的概念相似度计算方法得到初步的词语语义相似度结果;然后,利用基于搜索引擎的相关性双重检测算法和点互信息法得出进一步的语义相似度结果;最后,设计了拟合函数并利用批量梯度下降法学习权值参数,融合前两步的相似度计算结果。实验结果表明,与单纯的基于《知网》和基于搜索引擎的改进方法相比,融合方法的斯皮尔曼系数和皮尔逊系数均提升了5%,同时提升了具体词语义描述与人们对词汇的主观认知之间的匹配度,验证了将网络知识背景融入到概念相似度计算方法中能有效提高中文词汇语义相似度的计算性能。     

A parallel computational approach for similarity search using Bloom filters

Finding similar items in a large and unstructured dataset is a challenging task in many applications of data science, such as searching, indexing, and retrieval. With the increasing data volume and demand for real time responses, similarity search has gained much consideration. In this paper, a parallel computational approach for similarity search using Bloom filters (PCASSB) has been proposed, which uses Bloom filter for the representation of features of document and comparison with user's query. Query features are stored in integer query array (^IQ_A), an array of integer. The PCASSB, an approximate similarity search technique, has been implemented on graphics processing unit with compute unified device architecture as the programming platform. To compute the similarity score between query and reference dataset, Dice coefficient has been used as a baseline method. The accuracy of the results generated by PCASSB is compared with the baseline method and other state‐of‐the‐art methods. The experimental results show that the proposed technique is quite effective in processing large number of text documents as it takes less computational time.     

Scaling up top-K cosine similarity search

Recent years have witnessed an increased interest in computing cosine similarity in many application domains. Most previous studies require the specification of a minimum similarity threshold to perform the cosine similarity computation. However, it is usually difficult for users to provide an appropriate threshold in practice. Instead, in this paper, we propose to search top-K strongly correlated pairs of objects as measured by the cosine similarity. Specifically, we first identify the monotone property of an upper bound of the cosine measure and exploit a diagonal traversal strategy for developing a TOP-DATA algorithm. In addition, we observe that a diagonal traversal strategy usually leads to more I/O costs. Therefore, we develop a max-first traversal strategy and propose a TOP-MATA algorithm. A theoretical analysis shows that TOP-MATA has the advantages of saving the computations for false-positive item pairs and can significantly reduce I/O costs. Finally, experimental results demonstrate the computational efficiencies of both TOP-DATA and TOP-MATA algorithms. Also, we show that TOP-MATA is particularly scalable for large-scale data sets with a large number of items.     

图数据库中的相似性搜索算法研究与应用*

图数据库的相似性搜索是一个非常重要的研究内容,图的相似性匹配属于图同构的判定问题,是NP完全问题,传统的高开销搜索的方法已经不能满足复杂图查询的需要;另外,由于图数据库的复杂性和特殊性,已有的优化算法不能直接使用。为了提高图数据库的搜索效率,提出了一种基于索引的相似性搜索算法,通过数据库中的频繁结构建立特征索引,算法可高效准确地滤除大量的非相似图集合,避免了图之间精确匹配即图同构的计算,最后将本算法应用于化学数据库,实验结果证明了该方法的有效性和可行性。