Plagiarism and its automatic retrieval have attracted considerable attention from research and industry: various papers have been published on the topic, and many commercial software systems are being developed. However, when asked to name the best algorithm or the best system for plagiarism detection, hardly any evidence can be found to make an educated guess among the alternatives. One reason for this is that the research field of plagiarism detection lacks a controlled evaluation environment. This leads researchers to devise their own experimentation and methodologies, which are often not reproducible or comparable across papers. Furterhmore, it is unknown which detection quality can at least be expected from a plagiarism detection system.
To close this gap we have organized an international competition on plagiarism detection. We have set up, presumably for the first time, a controlled evaluation environment for plagiarism detection which consists of a largescale corpus of artificial plagiarism and de-
Research on plagiarism detection has been surveyed by Maurer, Kappe, and Zaka (2006) and Clough (2003). Particularly the latter provides well thought-out insights into, even today, "[...] new challenges in automatic plagiarism detection", among which the need for a standardized evaluation framework is already mentioned.
With respect to the evaluation of commercial plagiarism detection systems, Weber-Wulff and Köhler (2008) have conducted a manual evaluation: 31 handmade cases of plagiarism were submitted to 19 systems. The sources for the plagiarism cases were selected from the Web and the systems were judged by their capability to retrieve them. Due to the use of the Web, the experiment is not controlled which limits reproducibility, and since each case is only about two pages long there are concerns with respect to the study's representativeness. However, com-Stein, Rosso, Stamatatos, Koppel, Agirre (Eds.): PAN'09, pp. 1-9, 2009. mercial systems are usually not available for a close inspection which may leave no other choice to evaluate them.
The literature on the subject often puts plagiarism detection on a level with the identification of highly similar sections in texts or other objects. But this does not show the whole picture. From our point of view plagiarism detection divides into two major problem classes, namely external plagiarism detection and intrinsic plagiarism detection.
Both of which include a number of subproblems and the frequently mentioned step-bystep comparison of two documents is only one of them.
For external plagiarism detection Stein, Meyer zu Eissen, and Potthast (2007) introduce a generic three-step retrieval process. The authors consider that the source of a plagiarism case may be hidden in a large reference collection, as well as that the detection results may not be perfectly accurate. Figure 1 illustrates this retrieval process. In fact, all detection approaches submitted by the competition participants can be explained in terms of these building blocks (cf. Section 4).
The process starts with a suspicious document d q and a collection D of documents from which d q 's author may have plagiarized. Within a so-called heuristic retrieval step a small number of candidate documents D x , which are likely to be sources for plagiarism, are retrieved from D. Note that D is usually very large, e.g., in the size of the Web, so that it is impractical to compare d q one after the other with each document in D. Then, within a so-called detailed analysis step, d q is compared section-wise with the retrieved candidates. All pairs of sections (s q , s x ) with s q ∈ d q and s x ∈ d x , d x ∈ D x , are to be retrieved such that s q and s x have a high similarity under some retrieval model. In a knowledge-based post-processing step those sections are filtered for which certain exclusion criteria hold, such as the use of proper citation or literal speech. The remaining suspicious sections are presented to a human, who may decide whether or not a plagiarism offense is given.
Intrinsic plagiarism detection has been studied in detail by Meyer zu Eissen and Stein (2006). In this setting one is given a suspicious document d q but no reference collection D. Technology that tackles instances of this problem class resembles the human ability to spot potential cases of plagiarism just by reading d q .
We have set up a large-scale corpus (D q , D, S) of "artificial plagiarism" cases for the competition, where D q is a collection of suspicious documents, D is a collection of source documents, and S is the set of annotations of all plagiarism cases between D q and D. The competition divided into two tasks and into two phases for which the corpus was split up into 4 parts; one part for each combination of tasks and phases. For simplicity the sub-corpora are not denoted by different symbols.
• External Plagiarism Detection Task.
Given D q and D the task is to identify the sections in D q which are plagiarized, and their source sections in D.
• Intrinsic Plagiarism Detection Task.
Given only D q the task is to identify the plagiarized sections.
• Training Phase. Release of a training corpus (D q , D, S) to allow for the development of a plagiarism detection system.
• Competition Phase. Release of a competition corpus (D q , D) whose plagiarism cases were to be detected and submitted as detection annotations, R.
Participants were allowed to compete in either of the two tasks or both. After the competition phase the participants' detections were evaluated, and the winner of each task as well as an overall winner was determined as that participant whose detections R best matched S in the respective competition corpora.
The PAN plagiarism corpus, PAN-PC-09, comprises 41 223 text documents in which 94 202 cases of artificial plagiarism have been inserted automatically (Webis at Bauhaus-Universität Weimar and NLEL at Universidad Politécnica de Valencia, 2009). The corpus is based on 22 874 book-length documents from the Project Gutenberg.1 All documents are, to the best of our knowledge, public domain; therefore the corpus is available free of charge to other researchers. Important parameters of the corpus are the following:
• Document Length. 50% of the documents are small (1-10 pages), 35% medium (10-100 pages), and 15% large (100-1000 pages).
• Suspicious-to-Source Ratio. 50% of the documents are designated as suspicious documents D q , and 50% are designated as source documents D (see Figure 2).
• Plagiarism Percentage. The percentage θ of plagiarism per suspicious document d q ∈ D q ranges from 0% to 100%, whereas 50% of the suspicious documents contain no plagiarism at all. Figure 3 shows the distribution of the plagiarized documents for the external test corpus. For the intrinsic test corpus applies the hashed part of the distribution.
• Plagiarism Length. The length of a plagiarism case is evenly distributed between 50 words and 5000 words. • Plagiarism Languages. 90% of the cases are monolingual English plagiarism, the remainder of the cases are cross-lingual plagiarism which were translated automatically from German and Spanish to English.
• Plagiarism Obfuscation. The monolingual portion of the plagiarism in the external test corpus was obfuscated (cf. Section 2.1). The degree of obfuscation ranges evenly from none to high.
Note that for the estimation of the parameter distributions one cannot fall back on large case studies on real plagiarism cases. Hence, we decided to construct more simple cases than complex ones, where "simple" refers to short lengths, a small percentage θ, and less obfuscation. However, complex cases are overrepresented to allow for a better judgement whether a system detects them properly.
Plagiarists often modify or rewrite the sections they copy in order to obfuscate the plagiarism. In this respect, the automatic synthesis of plagiarism obfuscation we applied when constructing the corpus is of particular interest. The respective synthesis task reads as follows: given a section of text s x , create a section s q which has a high content similarity to s x under some retrieval model but with a (substantially) different wording than s x .
An optimal obfuscation synthesizer, i.e., an automatic plagiarist, takes an s x and creates an s q which is human-readable and which creates the same ideas in mind as s x does when read by a human. Today, such a synthesizer cannot be constructed. Therefore, we approach the task from the basic understanding of content similarity in information retrieval, namely the bag-of-words model. By allowing our obfuscation synthesizers to construct texts which are not necessarily human-readable they can be greatly simplified. We have set up three heuristics to construct s q from s x :
• Random Text Operations. Given s x , s q is created by shuffling, removing, inserting, or replacing words or short phrases at random. Insertions and replacements are, for instance, taken from the document d q , the new context of s q .
• Semantic Word Variation. Given s x , s q is created by replacing each word by one of its synonyms, antonyms, hyponyms, or hypernyms, chosen at random. A word is retained if neither are available.
• POS-preserving Word Shuffling. Given s x its sequence of parts of speech (POS) is determined. Then, s q is created by shuffling words at random while the original POS sequence is maintained.
The corpus has been conceived and constructed only just in time for the competition so that there may still be errors in it. For instance, the participants pointed out that there are a number of unintended overlaps between unrelated documents. These accidental similarities do not occur frequently, so that an additional set of annotations solves this problem.
The obfuscation synthesizer based on random text operations produces anomalies in some of the obfuscated texts, such as sequences of punctuation marks and stop words. These issues were not entirely resolved so that it is possible to find some of the plagiarism cases by applying a kind of anomaly detection. Nevertheless, this was not observed during the competition.
Finally, by construction the corpus does not accurately simulate a heuristic retrieval situation in which the Web is used as reference collection. The source documents in the corpus do not resemble the Web appropriately. Note, however, that sampling the Web is also a problem for many ranking evaluation frameworks.
A measure that quantifies the performance of a plagiarism detection algorithm will resemble concepts in terms of precision and recall. However, these concepts cannot be transferred one-to-one from the classical information retrieval situation to plagiarism detection. This section explains the underlying connections and introduces a reasonable measure that accounts for the particularities.
Let d q be a plagiarized document; d q defines a sequence of characters each of which is either labeled as plagiarized or nonplagiarized. A plagiarized section s forms a contiguous sequence of plagiarized characters in d q . The set of all plagiarized sections in d q is denoted by S, where ∀s i , s j ∈ S : i = j → (s i ∩ s j = ∅), i.e., the plagiarized sections do not intersect. Likewise, the set of all sections r ⊂ d q found by a plagiarism detection algorithm is denoted by R. See Figure 4 for an illustration. If the characters in d q are considered as basic retrieval units, precision and recall for a given d q , S, R compute straightforwardly. This view may be called micro-averaged or system-oriented. For the situation shown in Figure 4 the micro-averaged precision is 8/16, likewise, the micro-averaged recall is 8/13. The advantage of a micro-averaged view is its clear computational semantics, which comes at a price: given an imbalance in the lengths of the elements in S-which usually correlates with the detection difficulty of a plagiarized section-the explanatory power of the computed measures is limited.
It is more natural to treat the contiguous sequences of plagiarized characters as basic retrieval units. In this sense each s i ∈ S defines a query q i for which a plagiarism detection algorithm returns a result set R i ⊆ R. This view may be called macro-averaged or user-oriented. The recall of a plagiarism detection algorithm, r ec PDA , is then defined as the mean of the returned fractions of the plagiarized sections, averaged over all sections in S:
where computes the positionally overlapping characters. Problem 1. The precision of a plagiarism detection algorithm is not defined under the macro-averaged view, which is rooted in the fact that a detection algorithm does not return a unique result set for each plagiarized section s ∈ S. This deficit can be resolved by switching the reference basis. Instead of the plagiarized sections, S, the algorithmically determined sections, R, become the targets: the precision with which the queries in S are answered is identified with the recall of R under S.2 By computing the mean average over the r ∈ R one obtains a definite computation rule that captures the concept of retrieval precision for S:
where computes the positionally overlapping characters. The domain of prec PDA is [0, 1]; in particular it can be shown that this definition quantifies the necessary properties of a precision statistic. Problem 2. Both the micro-averaged view and the macro-averaged view are insensitive to the number of times an s ∈ S is detected in a detection result R, i.e., the granularity of R. We define the granularity of R for a set of plagiarized sections S by the average size of the existing covers: a detection r ∈ R belongs to the cover C s of an s ∈ S iff s and r overlap. Let S R ⊆ S denote the set of cases so that for each s ∈ S : |C s | > 0. The granularity of R given S is defined as follows:
where
where 1 marks the desireable one-to-one correspondence between R and S, and where |R| marks the worst case, when a single s ∈ S is detected over an over again.
The measures ( 1), (2), and ( 3) are combined to an overall score:
,
where F denotes the F-Measure, i.e., the harmonic mean of the precision prec PDA and the recall r ec PDA . To smooth the influence of the granularity on the overall score we take its logarithm.
For the competition, 13 participants developed plagiarism detection systems to tackle one or both of the tasks external plagiarism detection and intrinsic plagiarism detection. The questions that naturally arise: how do they work and how well? To give an answer, we survey the approaches in a unified way and report on their detection quality in the competition.
Most of the participants competed in the external plagiarism detection task of the competition; detection results were submitted for 10 systems. As it turns out, all systems are based on common approaches-although they perform very differently. As explained at the outset, external plagiarism detection divides into three steps (cf. Figure 1): the heuristic retrieval step, the detailed analysis step, and the post-processing step. Table 1 summarizes the participants' detection approaches in terms of these steps. However, the post-processing step was omitted here since neither of the participants applied noteworthy post-processing. Each row of the table summarizes one system; we restrict the survey to the top 6 systems since the overall performance of the remaining systems is negligible. Nevertheless, these systems also implement the generic three-step process. The focus of this survey is on describing algorithmic and retrieval aspects rather than implementation details. The latter are diverse in terms of applied languages, software, and their runtime efficiency; descriptions can be found in the respective references.
The heuristic retrieval step (column 1 of Table 1) involves the comparison of the corpus' suspicious documents D q with the source documents D. For this, each participant em- ploys a specific retrieval model, a comparison strategy, and a heuristic to select the candidate documents D x from the D. Most of the participants use a variation of the well-known vector space model (VSM) as retrieval model, whereas, the tokens are often character-or word-n-grams instead of single words. As comparison strategy, the top 3 approaches perform an exhaustive comparison of D q and D, i.e., each d q ∈ D q is compared with each
, while the remaining approaches employ data partitioning and space partitioning technologies to achieve lower runtime complexities. To select the candidate documents D x for a d q either its k nearest neighbors are selected or the documents which exceed a certain similarity threshold.
The detailed analysis step (column 2 of Table 1) involves the comparison of each d q ∈ D q with its respective candidate documents D x in order to extract pairs of sections (s q , s x ), where s q ∈ d q and s x ∈ d x , d x ∈ D x , from them which are highly similar, if any. For this, each participant first extracts all exact matches between d q and d x and then merges the matches heuristically to form suspicious sections (s q , s x ). While each participant uses the same type of token to extract exact matches as his respective retrieval model of the heuristic retrieval step, the match merging heuristics differ largely from one another. However, it can be said that in most approaches a kind of distance between exact matches is measured first, and then a custom algorithm is employed which clusters them to sections.
Table 2 lists the detection performance results of all approaches, computed with the quality measures introduced in Section 3. Observe that the approach with top precision is the one on rank 6 which is based on fingerprinting, the approach with top recall is the one on rank 2, and the approach with top granularity is the one on rank 1. The latter is also the winner of this task since it provides the best trade off between the three quality measures.
The intrinsic plagiarism detection task has gathered less attention than external plagiarism detection; detection results were submitted for 4 systems. Table 3 lists their detection performance results. Unlike in external plagiarism detection, in this task the baseline performance is not 0. The reason for this is that intrinsic plagiarism detection is a one-
We thank Yahoo! Research and the University of the Basque Country for their sponsorship. This work was also partially funded by the Text-Enterprise 2.0 TIN2009-13391-C04-03 project and the CONACYT-MEXICO 192021 grant. Our special thanks go to the participants of the competition for their devoted work.
class classification problem in which it has to be decided for each section of a document whether it is plagiarized, or not. The baseline performance in such problems is commonly computed as the naive assumption that everything belongs to the target class, which is also what Hagbi and Koppel (2009) did who classified almost everything as plagiarized. Interestingly, the baseline approach is on rank 2 while two approaches perform worse than the baseline. Only the approach of Stamatatos (2009) performs better than the baseline.
To determine the overall winner of the competition, we have computed the combined detection performance of each participant on the competition corpora of both tasks. Table 4 shows the results. Note that the competition corpus of the external plagiarism detection task is a lot bigger than the one for the intrinsic plagiarism detection task, which is why the top ranked approaches are those who performed best in the former task. Overall winner of the competition is the approach of Grozea, Gehl, and Popescu (2009).
The 1st International Competition on Plagiarism Detection fostered research and brought a number of new insights into the problems of automatic plagiarism detection and its evaluation. An important by-product of the competition is a controlled large-scale evaluation framework which consists of a corpus of artificial plagiarism cases and new detection qual-ity measures. The corpus contains more than 40 000 documents and about 94 000 cases of plagiarism. Furthermore, in this paper we give a comprehensive overview about the competition and in particular about the plagiarism detection approaches of the competition's 13 participants. It turns out that all of the detection approaches follow a generic retrieval process scheme which consists of the three steps heuristic retrieval, detailed analysis, and knowledge-based post-processing. To ascertain this fact we have compiled a unified summary of the top approaches in Table 1.
The competition divided into the two tasks external plagiarism detection and intrinsic plagiarism detection. The winning approach for the former task achieves 0.74 precision at 0.65 recall at 1.00 granularity. The winning approach for the latter task improves 26% above the baseline approach and achieves 0.23 precision at 0.46 recall at 1.38 granularity.