Dissertation > Excellent graduate degree dissertation topics show

Copy detection algorithm based on distributed text indexing

Author: Zhang
Tutor: HuangZuoZuo
School: Fudan University
Course: Applied Computer Technology
Keywords: Near Duplicate Detection Copy Detection Map-Reduce
CLC: TP391.1
Type: Master's thesis
Year: 2012
Downloads: 28
Quote: 0
Read: Download Dissertation

Abstract


In internet, there are a lot of duplicated web pages. How to efficiently detect near duplicate in large scale document corpus has been a hot topic for a long time. A effective and efficient near duplicate detection algorithm is useful in many ways, such as reducing duplicated result in search engine, plagiarizing detection and text clustering. As the corpus size increases, near duplicate detection algorithm for single-node computer is intractable. Distributed computing framework such as Map-Reduce has been introduced in this task. To perform near duplicate detection on a distributed platform, several problems have to be solved. The first problem is how to split data across different nodes. The second one is how to reduce data traffic between different nodes. The third one is how to balance the load on every node. Previous research fails to handle these three problems properly. In this paper, we introduce two efficient near duplicate detection algorithms that could solve these problems and have good scalability.Usually. near duplicate detection algorithms use inverted index to improve their efficiency. In this paper, we first investigate the index structure on a distributed computing platform. We present an effective index structure--Doc-Split Index. DSI. In DSI, each block contains the index of a subset of the whole corpus. Therefore, at each time only one index block is needed in a single computing node. This will reduce the data transport between different nodes and balance the load on every node.。Based on the discussion on index structure, we propose two distributed algorithms for duplicate detection, PQ on DSI and PCP on DSI. These two algorithms are both efficient. Beside of that, the algorithms are implemented on Map-Reduce and in hence, have good scalability.In the experiments, we firstly perform parameter selection on an Oracle Set which is randomly selected from the real corpus with duplicated documents manually marked up. Then on the WT10G, we compared our algorithms (PQ on DSI, PCP on DSI) with two other algorithms (PQ, PCP) which were proposed by former researchers. The experiment shows our algorithms are better than theirs in efficiency.

Related Dissertations

  1. Research and Application of Map/Reduce Based Distributed Log Analyzer,TP311.52
  2. 3D Mannequins Generating Engine Based on eMTM with MapReduce,TP391.41
  3. Research on Local Feature Based Image Copy Detection,TP391.41
  4. An Intrusion Detection System for High-Speed Networks,TP393.08
  5. A Video Copyright Registration and Identification System Based on Copy Detection,TP311.52
  6. The Research of Text Classification Based on Hadoop,TP391.1
  7. Research and Implementation on a Distributed Service Registry Based on HADOOP Platform,TP393.09
  8. Resarch of Task-level Data Processing Based on Multicore CPU and Test of Its Performance on Cluster Platform,TP274
  9. Hadoop data center deployment and tracking systems research,TP308
  10. Fault Tolerance for MapReduce in the Cloud Environment,TP302.8
  11. A scalable prototype design and implementation of MapReduce,TP311.52
  12. The Research of Distributed Text-based Data Filtering Technology and System Implementation Based on MapReduce,TP391.1
  13. Based on large-scale cloud computing platform manifold learning algorithm,TP311.13
  14. Large-scale approximation paragraph fingerprint - based page detection algorithm research,TP393.092
  15. The Optimization of High Performance MapReduce FairScheduler and the Implementation on Simulator of Huge Scale Cluster,TP311.13
  16. Research and Application of column storage management technology based on RFID data,TP315
  17. Analysis and Optimization of Massive Data Processing on High Performance Computing Architecture,TP338
  18. Information Flow Control Model in Distributed Systems,TP316.4
  19. Job Scheduling Technologies in Data Intensive Supercomputing Systems,TP311.13
  20. IaaS cloud computing - based Web application technology research,TP393.09
  21. Content-based video copy detection research,TP391.41

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer applications > Information processing (information processing) > Text Processing
© 2012 www.DissertationTopic.Net  Mobile