A Chunk-based Copy Detection Approach for Multimedia Documents

INTRODUCTION

---

Currently, Internet and digital libraries provide vast amounts of digitized information on-line. Thus, it is easy to copy someone else’s work and submit it as someone’s own. One can copy documents with illegal purposes, that is the plagiarism. Internet makes it easier to plagiarize other’s ideas. Thus, it is a great challenge to detect and prevent plagiarism.

Nowadays, there are many content-based document copy detection systems. For example, COPS (Xiao et al., 2011), Koala (Urvoy et al., 2008), SCAM (Stajano and Wilson, 2011), Shingling (Elmagarmid et al., 2007), I-Match (Puppin et al., 2010), etc. Nowadays, there are huge amount of multimedia documents on the Internet. Multimedia documents are much more complicated. Thus, many techniques used in the above systems for normal documents are not suitable for multimedia documents, such as stemming and anchor strategy (Potthast et al., 2011).

Moreover, the current copy detection systems mainly focus on document-level copy detection and struggle to measure the amount of overlap in document-level. But these systems are not always reliable for total copy detection of documents with varying size, not to mention partial copy detection. In this study, a Fingerprinting-based Heuristic Algorithm (FHA) is presented to calculate document-level and passage-level similarity for multimedia documents. Firstly, the documents are split into fixed-length chunks. Then, the overlap of these chunks is used to deal with total and partial copy detection.

CHUNK-BASED COPY DETECTION APPROACH

Generally, copy detection is to detect whether a document is the copy of other documents. In this study, a document is regarded as a set of tokens. These tokens can be characters, words, sentences, passages, etc., Let A and B be the chunk sets of two documents. Then, the relations of them include: (1) If A≈B, A is a copy of B. This is the total copy; (2) If A∈B and A≠B, A is the subset of B. This is the partial copy.

In this study, the similarity of two documents is measured in two levels: Document-level and passage-level. From the distinct set of chunks of two documents, the absolute similarity between documents is calculated using the concept of intersection of sets. Then it is possible to verify how much of candidate document is contained in another plagiarized document, as shown:

(1)

where, CK (D) represents the set of whole chunks of document D.

Fig. 1:	FHA: Fingerprinting-based heuristic algorithm

In the same way, the concept of intersection and union of set is used to calculate the similarity of chunks in documents, as shown:

(2)

where, FP (C) represents the set of whole fingerprints of chunk C.

In practice, the numerator represents the total number of fingerprints in chunks of the plagiarized document and candidate document and the denominator represents the sum number of fingerprints occurring simultaneously in chunks of two documents plus the number of fingerprints of chunks that occurs in each of the documents that do not occur in the other one.

Figure 1 showed the instantiation FHA of the copy detection approach. As in the untimed case the algorithm is based on a document-set, DocSet, containing all the documents and a chunk-set, ChunkSet, containing all the chunks of a document.

Document parsing: In the proposed copy detection approach, each document is first passed through a stopword-removal process, which removes all the stopwords. Stopwords in a document should first be removed since stopwords, such as articles, conjunctions, prepositions, punctuation marks, numbers and non-alphabetic characters, often do not play a significant role in document. This process reduces the size of a document for comparison and subsequently the complexity on copy detection.

Prior researches on copy-detection prototype systems, e.g., SCAM, Koala and Shingling, have the common approaches that they split the document into chunks. It is showed by Bar-Yossef et al. (2009) that the length of chunks should be somewhere between 40 and 60 characters for plagiarism-detection purposes. But this selection strategy of chunk does not fit to the copy detection for complicated multimedia document.

In this study, the document is split into fixed-length chunks. Some kind of culling strategy is used to select representative chunks. A short chunk is not very representative of a text. The fact that two files share a short chunk does not lead us to suspect that they share ancestry. In contrast, very long chunks are very representative, but unless a plagiarizer is quite lazy, it is unlikely that a copy will retain a long section of text. It’s better to retain similar chunks for any file.

Chunk parsing: It has been experimented with two culling methods for chunks. For candidate documents, they should be stored in the database, so non-overlap culling method of chunk is used to save space of database. For plagiarized document, they should be detected carefully, so overlap culling method of chunk is used to get higher precision.

If the proposed approach is widely used and the size of chunks is published, plagiarizer can managed to elude copy detection. It should set variable parameters to change the size and location of chunks. Then the location of chunks is:

(3)

where, l is the size of chunk, θ is variable size parameter of chunk. l and θ should be changed aperiodically to assure the algorithm security.

Fingerprint parsing: In this study, there are different methods to measure document-level and passage-level fingerprints. Full fingerprint is used for document-level, overlapped fingerprint for passage-level. For chunk is fixed-length, its fingerprint resolution is also fixed. Let g (g>1 word) be the fingerprint granularity, SizeC be the chunk size, n be the overlap rate. For document-level, the location of fingerprints in chunk is: 0, 1, 2, …, SizeC. For passage-level, the location of fingerprints in chunk is: 0, g-n, 2(g-n), …, SizeC.

In fingerprinting, Karp-Rabin hash algorithm Puppin et al. (2010) is adopted to generate fingerprints. And a 64-bit hash value is produced to ensure better distribution of hashing.