DOI 10.1007/s10586-015-0506-0
Efficient top-k similarity document search utilizing distributed file systems and cosine similarity
Mahmoud Alewiwi1 · Cengiz Orencik1 · Erkay Savascedil;1
Received: 19 February 2015 / Revised: 29 September 2015 / Accepted: 29 October 2015 / Published online: 9 November 2015
copy; Springer Science Business Media New York 2015
Abstract Document similarity has important real life applications such as finding duplicate web sites and iden- tifying plagiarism. While the basic techniques such as k-similarity algorithms have been long known, overwhelm- ing amount of data, being collected such as in big data setting, calls for novel algorithms to find highly similar documents in reasonably short amount of time. In particular, pairwise com- parison of documentsrsquo; features, a key operation in calculating document similarity, necessitates prohibitively high storage and computation power. In this paper, we propose a new fil- tering technique that decreases the number of comparisons between the query set and the search set to find highly similar documents. The proposed filtering technique utilizes Z -order prefix, based on the cosine similarity measure, in which only the most important features are used first to find highly sim- ilar documents. We propose a three-phase approach, where the phases are near duplicate detection, common important terms and join phase. We utilize the Hadoop distributed file system and the MapReduce parallel programming model to scale our techniques to big data setting. Our experimental results on real data show that the proposed method performs better than the previous work in the literature in terms of the number of joins, and therefore, speed.
Keywords Z-order · Document similarity · MapReduce ·
Hadoop · Cosine similarity
B Cengiz Orencik cengizo@sabanciuniv.edu
Mahmoud Alewiwi alewiwi@sabanciuniv.edu
Erkay Savascedil; erkays@sabanciuniv.edu
1 Faculty of Science and Engineering, Sabanci University, Istanbul, Turkey
Introduction
Big data, referring to not only the huge amount of data being collected, but also associated opportunities, has big potential for major improvements in many fields from health care to business management. Therefore, there is an ever-increasing demand for efficient and scalable tools that can analyze and process immense amount of, possibly unstructured, data, which keeps increasing in size and complexity. Finding similarities (or duplicates) among multiple data items, or documents, is one of the fundamental operations, which can be extremely challenging due to the nature of big data. In particular, similarity search on a huge data set, where the documents are represented as multi-dimensional feature vec- tors, necessitates pair-wise comparisons, which requires the computation of a distance metric, and therefore can be very time and resource consuming, if not infeasible.
A commonly used technique, known as filtering, decreases the number of pairwise comparisons by skipping the com- parison of two documents if they are not potentially similar; e.g., they do not share any common feature. Also, represen- tation, storage, management and processing of documents play an important role in the performance of similarity search method. A distributed file system and a parallel programming model such as MapReduce [9] are necessary components of a scalable and efficient solution in big data applications.
This work focuses on the general problem of detecting the k-most similar documents for each document within a given data set (henceforth self join), and between two arbitrary sets of documents (R–S join), namely query set and data set. The problem is formalized as follows.
Definition 1 (R–S join top-k set similarity) Let D be a set of documents {d1,..., dn}, di isin; D. Let Q be a set of query doc- uments {q1,..., qm}, q j isin; Q. Then R–S top-k set similarity
is defined as:
forall;qj isin; Q, top-k(qj , D) = {d j1,..., d jk },
where d ji is the i th nearest record to q j in D.
Definition 2 (Self join top-k set similarity) Let be a set of documents d1,..., dn , di . Then self join top-k set similarity is defined as:
{ } isin; D
D
forall;dj isin; D, top-k(dj , D) = {d j1,..., d jk },
where d ji /= d j is the i th nearest record to d j in D. Intuitively, the self join case is the generalization of the
R–S join case such that .
Q = D
The trivial solution for the set similarity problem, for two sets of items and , is to compare each element in Q with each element in . This solution has (delta;mn) complex- ity, where m and n are the number of elements in and respectively, and delta; is the number of dimensions (i.e., fea- tures) in and . Recent trends and research are concerned a
剩余内容已隐藏，支付完成后下载完整资料
基于分布式文件系统和余弦相似度算法的TOP-K文档相似度对比
摘要
文档相似度对比在现实生活中有着很多实际应用，比如网站去重和剽窃判定。虽然类似K相似度算法等基本算法早已被大量应用，但大数据平台下的大规模数据集相似度处理，急需新的算法在短时间内比对出高度相似的文档。在相似度处理中，对文档特征值的成对比较是计算文档相似性的关键步骤，需要有一定规模的存储和计算能力。本文提出了一种新的过滤算法，该算法可以减少查询集和搜索集之间的比较次数，来更快的找出高度相似的文档。算法利用基于Z阶前缀的余弦相似性度算法，优先使用权重最大的特征来寻找高度相似的文档。算法提出了一种基于重复检测、公共重要项和连接相结合的三相方法。我们利用Hadoop分布式文件系统和MapReduce并行编程模型将我们的技术扩展到大数据平台。实验结果表明，本文提出的方法在数据规模和速度方面相比引用文献中的方法有着更好的实际效果。
1 介绍
大数据不仅指收集到的大量数据，也意味着在医疗保健和业务管理等许多领域都有很大的改进的机会。因此，随着数据的规模和复杂性在不断增加，对能够分析和处理大量（可能是非结构化的）数据的高效且可扩展的工具的需求在不断增加。在多组数据或文档之间查找相似性（或重复数据）是基本操作之一，由于大数据的特殊性质，这变得极具挑战性。特别是，在大数据集上进行相似性搜索，其中文档被抽象为多维特征向量，需要成对比较，这需要计算两两之间的距离向量，因此在常规手段下即使相似度对比是可行的，也非常耗费时间和资源。
一种常用的被称为过滤的技术，在对比文档时如果发现两份文档间不具有潜在的相似性，则通过跳过两个文件的比较来减少成对比较的数量;例如，它们不拥有任何类似的特征。此外，文档的表示，存储，管理和处理流程在相似性对比方法的性能中起着重要作用。分布式文件系统和并行编程模型是大数据应用程序中可扩展、高效的解决方案。
这项工作主要检测查询集和数据集中，每个文档的k-最相似文档以及任意两个文档集（R-S连接）之间的相似度问题，即问题形式化如下。
定义1（R连接top-k集相似性）设D是一组
文件{d1，...，dn}，diisin; D。 设Q是一组查询文档{q1，...，qm}，qjisin;Q。 然后R-S top-k集相似度定义为：
forall;q j isin; Q, top-k(q j, D) = {dj1,..., djk },
其中dji是D中最接近q j的记录。
定义2（自联接top-k集相似性）设D为集合
文件{d1，...，dn}，diisin;D。然后自联接top-k集
相似性定义为：forall;djisin;D，top-k（dj，D）= {d j1，...，d jk}，
其中d ji ne; d j是D中最接近d j的记录。
直观地说，自联合的情况是概括的R-S连接情况，使得Q = D.
对于两组数据，集合相似性问题的简单解决方案是将Q中的每个元素与其他元素进行比较。该解决方案具有（delta;mn）复杂度，其中m和n分别是和中的元素的数量，delta;是特征的数量。最近的研究趋势是如何以高效和高性能的方式实现集合相似性连接算法，本文提出了减少比较次数的新的集合相似性连接算法。
目前的研究主要采用过滤技术，过滤出具有低于给定阈值的相似性的对。显然，采用的过滤算法在相似性搜索的效率和有效性方面发挥着最大的作用。在这项工作中，我们提出了一种新的基于余弦相似度的过滤技术，以提高相似度计算的性能。
在我们的解决方案中，我们建议采用新的基于Z顺序的过滤技术，以便在执行计算余弦相似度的昂贵操作之前消除不同的文档。数据集中的文档表示为文档特征的多维空间上的Z阶空间填充曲线上的点。基于文档最重要特征的投影用于过滤掉不具有共同重要特征的不同文档。所提出的方法还过滤掉仅共享低重要性特征的文档，这些特征对数据对象之间的相似性几乎没有影响。该技术在快速搜索高度相似的文档场景提供了显着的改进。最后，我们将实现所提出技术的算法，实现可以利用Hadoop [2] MapReduce并行编程框架的并行程序。
本文的其余部分安排如下。在章节2，提供了文献中相关方法的概述。在章节3中介绍基于Z阶前缀的过滤方法和MapReduce框架，
在章节4中基于Z阶前缀的过滤技术对具有lambda迭代前缀（ZOLIP）过滤算法进行了解释
章节5给出了实验结果，展示了所提方法的准确性和有效性。
章节6为结论。
2相关工作
在以往的研究中，考虑单机上的集合相似性问题在文献[3,5,7,19]中。这些文献主要集中在降低矢量相似性连接的复杂性。Angiulli et al. [1]使用Z阶空间填充曲线，以便使用Minkowski向量来找到两个高维空间数据集之间的相似性。该方法适用于在高维数据中查找近似对，但不适用于基于文本的相似性检测。对于基于文本的相似性，如在文档相似性问题的情况下，余弦相似度算法比Minkowski向量算法更合适。
Connor和Kumar [8]提出了另一种文件相似性检测技术。他们使用二进制搜索方法，在选定的Z阶空间中找到k-NN。其他文献中的一种流行方法是采用过滤技术来过滤掉不能超过给定相似性阈值的对。该技术通过消除与本次搜索不共享任何重要向量的文档来减少候选文档的数量，并以此减少相似性连接操作的数量。
文献中使用了各种过滤技术。 Chaudhuri等人提出了一种前缀过滤方法。 [7]。在工作中使用了长度过滤方法[3]和[5]。 Xiao等人提出了位置和后缀过滤方法。 [22]。 Sarawagi和Kirpal [19]提出了一种名为PPJoin 的方法，该方法利用反向索引并使用Pair-Count算法生成共享一定数量令牌的对。 Arasu [3]提出了一种基于签名的方法，其中文档的特征由签名表示，并且使用底层签名的相似性计算文档之间的相似性。朱 [25]提出了一种基于余弦相似性的搜索技术。他们提出了一种利用对角遍历策略过滤掉不相关文档的算法。在该算法中，数据集中的元素由二进制向量表示，这意味着仅考虑关系的存在，忽略它们在数据集中的频率或重要性。
MapReduce计算模型也被考虑用于相似性搜索问题，这引出了存储在云服务器上的大数据集的并行连接算法。 Elsayed [10]提出了一种采用全过滤技术的MapReduce模型。他们使用了一个简单的过滤器，只找共享共同特征的数据对。所提出的方法由两个阶段组成。第一阶段解析并为每个文档中的术语创建索引，
第二阶段找到共享这些术语的类似对。 Vernica [21]使用PPJoin 方法[19]来执行自连接操作。杨 [23]提出了一种方法，它使用带有两个MapReduce阶段的前缀和后缀过滤器。倒序索引在[14]中与前缀过滤结合使用。 Baraglia等人提出了一种改进的双通MapReduce前缀过滤方法。 [4]潘等人[17]使用布隆过滤算法来构建相似度对
在之前的相似性搜索文献的工作中，没有考虑到这些术语的重要性。这会影响文档之间的语义相似性（即，某些文档可能具有相同的术语但在不同的上下文中）。 在我们的算法中，为了解决这个问题，我们利用基于余弦相似度的过滤技术，利用文档中术语的相对重要性来寻找类似的文档。
第3章
本节提供了所提出的ZOLIP过滤算法中使用的主要原理。
首先，我们给出用于计算文档相似性的相关性评分方法。
接下来，描述Z顺序映射的原理。 在最后一部分，
我们解释了MapReduce框架工作，它用于有效地实现所提出的方法。
3.3 Hadoop和MapReduce框架
在这项工作中，我们利用MapReduce编程框架，该框架采用并行执行和协调模型，可用于管理海量数据集的大规模计算[6,18]。支持MapReduce模型的众所周知的开源框架之一是Apache Hadoop框架[2]，它设计用于在集群上运行。这些文件存储在称为分布式文件系统（DFS）的特殊文件系统中。
数据复制是提高Hadoop框架有效性的关键因素之一，Hadoop框架在利用大量集群节点进行数据密集型计算时能够避免节点故障。我们使用Hadoop框架中的MapReduce模型实现了我们的算法，使得网络通信，进程管理，进程间通信，高效的海量数据移动和容错的细节对用户都是透明的。通常，开发人员只需提供配置参数和几个应用程序。 Hadoop框架被包括谷歌，雅虎，IBM在内的公司使用
图4 MapReduce执行流程
主要用于涉及搜索引擎和大规模数据处理（例如大数据应用程序）的应用程序。 MapReduce模型基于map和reduce两个函数。 map函数负责将表示为键值对的数据项列表分配给集群节点。 map函数接收键值对，并将结果作为中间数据发送到reducer。 reducer函数获取映射数据并应用处理操作。它将中间数据作为键和值列表接收为(key,[values])。这两个的签名
功能是
map：（k1，v1）→[（k2，v2）]
reduce：（k2，[v2]）→[（k3，v3）]。
图4中的map和reduce函数之间的混洗过程负责将具有相同值的所有键指定给同一计算节点。
4实验
在本节中，我们首先描述系统模型和我们实验中使用的数据集。然后，我们将提出的方法与Vernica等人的方法进行比较 [21]。所提出的方法使用不同的参数设置进行测试，以显示其在大数据环境中的效率和可扩展性。最后，我们讨论了我们的方法的准确性和增加lambda;参数对其准确性和效率的影响。
4.1设置和数据描述
我们使用带有3节点集群的Cloudera CDH4安装：两个节点，Xeon处理器E5-1650 3.5 GHz 12核，15.6 GB RAM和1 TB硬盘;一个节点采用Core i7 3.07 GHz的8核，15.7 GB的RAM和0.5 TB的硬盘。在每个节点上，安装了Ubuntu 12.04 LTS，64位操作系统，并使用Java 1.6 JVM。我们使用默认的Cloudera DFS块大小（即128 MB），因此数据被分区为128 MB块，并为每个块分配映射器。由于假设系统没有关于查询大小的功能，因此在将数据块分配给映射器之前不会应用其他分区。注意，数据和查询集存储在DFS中的不同数据块中。
映射器的输出直接发送到reducer，无需任何额外的组合器功能。注意，标有“Q”的查询元素与标有“D”的数据元素进行比较。由于查询和数据映射器的输出类型不同，因此无法在映射后使用组合器操作进行聚合计算。
在我们的实验中，我们主要使用安然数据集[11]，它是真实电子邮件文件的数据集。该数据集包含510,000个电子邮件文件，相当于总计2,686,224 KB的数据。文件大小范围为4 KB到2 MB。首先，从邮件标题中清除数据并切分单词。这些术语源自Lucene [15]中包含的雪球词干，它是一个用于信息检索的开源库。然后，我们计算每个文件中每个术语的tf-idf值。最后，我们创建了tf-idf值的稀疏向量，它们代表了文档。对于安然数据集，得到的稀疏矢量具有30,000个维度（即，项），平均密度为160 / 30,000。密度定义为具有非零分数的项数与数据集中的项总数之比[23]。
此外，为了观察算法在不同数据集上的性能，我们使用路透社数据集[13]，其中包含20,000个28 MB的新闻记录，字典大小为136个术语。
4.2性能分析
我们将算法的性能与Vernica等人提出的算法的性能进行了比较。 [21]。图8显示了针对前10个结果（即k 10）的安然数据集上的各种查询集大小的两种算法的实现的绝对运行时间。由于安然数据集规模非常大，这对于实验中使用的小型三节点Hadoop集群而言无法负载，因此Java堆内存受到[21]中算法的超负载影响。因此，本文省略了Vernica方法的自连接情况的时序结果。此问题的解决方法是使用具有更多节点的计算集群。
我们进行了不同的实验来观察不同参数设置对所提方法性能的影响。用于不同lambda;值的方法的性能在图9中示出。图9示出了对于lambda;的小值，查询大小的影响非常低。然而，对于lambda;8，搜索时间随着查询大小的增加而急剧增加，这是由于连接操作的数量的明显增加（即，一对文档之间的相似性计算）。减少计算时间的一个简单方法是使用具有更多节点的计算集群。
图10显示了不同查询集大小的每个阶段的运行时间，即NDD，CIT和JP。我们发现
图8提出的算法（ZOLIP）和Vernica等人的方法之间的性能比较。 [21]当k = 10
图9增加lambda;对效率的影响k = 10
图10每相的运行时间为lambda;= 8
CIT阶段的运行时间随着查询文档的数量而增加，这是预期的，因为该阶段是算法的主要部分，其中比较了共享共同重要术语的所有文档。 NDD阶段与查询文档的数量一致。尽管该阶段的复杂性相对于字典大小（delta;）是线性的，但是当我们使用静态数据集时它会执行常量。我们还分析了k的增加对方法效率的影响，并说明了图11中的结果。如图所示，k对相似性搜索时间没有主要影响。其原因与k无关，给定查询文档，我们的算法与所有其他与查询文档共享重要术语的文档计算相似性得分，然后选择前k个结果。但是，如果第一阶段（NDD）成功找到k或更多结果，则不执行第二阶段;因此，对于小的k值，该算法可以表现得更好。
通常，从我们的实验中我们观察到从第一阶段（即，接近重复检测阶段）返回的文档与查询文档的相似性（即c（q，di））超过80％。
|
lt;
剩余内容已隐藏，支付完成后下载完整资料 资料编号：[441925]，资料为PDF文档或Word文档，PDF文档可免费转换为Word |
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
