1 \section{Candidate document retrieval}~\label{simon}
2 The basic concept of candidate document retrieval is to use a web search
3 engine to find suitable documents. In PAN 12 competition we used ChatNoir search
4 engine~\cite{chatnoir} which indexes the entire English part of the ClueWeb09 corpus.
5 We can now reduce the problem to constructing appropriate queries for ChatNoir search engine.
6 The goal is to retrieve similar documents, which contains the same passages as the source document
7 or similar documents dealing with the same theme.
8 The strongest emphasis has been places on minimizing the number of executed queries
9 since they may be charged or time limited or number limited in the real world.
11 In the PAN 12 test corpus, there were 32 text documents all contained at least one plagiarism case.
12 The documents were approximately 30 KB of size, the smallest were 18 KB and the largest were 44 KB.
13 We have used methods which are applicable in general to any type of text input with no apriori information about the input document.
15 %All queries from a given document were firstly preconstructed and they were afterwards sequentially executed
16 %according to their priority. After each executed query the intermediate results of plagiarism
17 %were calculated using the multi feature document comparison techniques described in section~\ref{yenya}.
18 %This process leads to continuing lowering the number of executed queries, for more details see the following passages.
21 We can divide constructed queries into three main groups according to their origin:
22 i) document keywords based, ii) intrinsic plagiarism based, and iii) headers based.
23 %Please note two major attributes of the extracted keywords. Firstly we say
25 \subsection{Keywords based queries}
26 The document keywords based queries are constructed from automatically extracted keywords from the given document.
27 As for keyword extraction we used methodology based on word repetition similar to method described by Scott~\cite{text_patterns}.
28 The basic principle claims that the more frequent a single word in a given document is, the more likely it is to be key in it.
29 However the most frequent words usually do not carry any meaning.
30 For example articles (the), conjunctions (as) or prepositions (at).
31 These types of words are usually refered as the stop words.
32 Thus we firstly filter out stop words according to general English stop words list.
33 Secondly we used reference corpus word list as an additional filter.
34 We used words in their simple verbatim occurrence allied to a
35 statistical estimate of likelihood. As a result of this, a word to become a key
36 must not exists in the stop list and must occur in the suspicious document relatively much more frequently
37 than in the reference corpus. We used a corpus created from common English web sources, which contains
38 more then 4 billion tokens~\cite{ententen}.
39 The statistical measure TF-IDF~\cite{Introduction_to_information_retrieval}
40 was applied in order to decide whether the processed word shall become a keyword.
41 The TF-IDF combines term frequency (TF) and inverse document frequency (IDF) to produce composite weight of a given term.
42 Taking into account the average length of the suspicious document and minimizing the number of used queries we set TF-IDF weight threshold to 0.02,
43 which resulted in about 10 to 20 terms identified as keywords per document.
45 Before executing web search tasks we must combine extracted keywords into befitting queries.
46 All queries were constructed from 5 keywords according to their TF-IDF weight consecutively.
47 In other words 5 top ranked keywords combine into the first query the other 5 top ranked keywords combine into the second query.
48 By using this method we usually obtained from 2 to 3 initial queries per document.
50 \subsubsection{Collocations}
51 In addition to this we enhanced subsequent queries by the most frequent collocations of top 4 keywords.
52 For those 4 keywords we extracted the most frequent two-word and three-word collocation occurring within the single suspicious document.
53 A scope for collocates was a single sentence. We counted collocates as the most frequent neighbouring words within the scope also omitting stop words.
54 To take advantage of extracted collocations we combined them among selfs also into 5 word queries.
55 After omitting queries containing duplicated words we added, on average, two new queries to each suspicious document.
56 Despite of being composed from collocations we count those queries also as the keywords based. Together with
57 the queries created only from bare keywords, those queries were unconditionally executed as the initial queries. \\
59 Queries containing around 5 words should be optimal in order to retrieve highest mean average precision of results.
60 It means we would like to extract from results of those queries as many documents as possible but still dealing
61 with the similar theme as the source document. Expecting the order of words within a single query has small
62 impact on results, no other heuristics of combining keywords into queries were applied also
63 in order to keep the query amount minimal. In 32 from 33 input test documents were more than a hundred resulting documents found using
64 those initial queries, which gave a decent document base covering the source document theme for document comparison.
68 %using less kw in q would result into more general or underspecifi
70 All those previously mentioned queries characterize the document as a whole.
71 They should cover the theme of the document expecting the single document is actually dealing with a one theme.
73 \subsection{Intrinsic plagiarism based queries}
74 Intrinsic plagiarism queries were constructed from a representative sentence residing in
75 the selected part of the document. Representative sentence is any sentence from the selected part of the document
76 which is greater then eight words in length.
77 Such a sentence should produce the least searching false-positives~\cite{knight}.
79 The main task concerning representative sentences is to locate the suitable text part.
80 This part should be located by a method leading to discover potential plagiarism inside the document of its own,
81 which is called intrinsic plagiarism detection. Such a method is based on for example text statistics or syntactic features.
82 We chose statistical vocabulary richness method called average word frequency class described in~\cite{awfc}.
83 Using this method we can compute average word frequency class values (AWFC) for arbitrary parts of the text. The change
84 of this value between two adjacent text windows indicates change of writing style, which can be caused by a plagiarism.
85 We computed AWFC value for every text window of size 45 words, which was shifted through the text by 40 words span.
86 The values of window size and span of shifting was set empirically during training. Windows with
87 largest change of AWFC compared to AWFC of their neighbouring previous window were selected as candidate for query extraction.
90 The query from the representative sentence was composed by 6 words from the sentence beginning, also omitting stop words.
91 We chose 6 words to cover higher portion of selected sentence and not to exceed
92 the phrasal ChatNoir query limit.
93 This type of query is actually looking for documents containing the very same or at least the very similar sentence,
94 therefore we choose more than 5 word queries in order to narrow the search to more specific
95 results. Unfortunately in the time of PAN 12 competition the ChatNoir search engine did not
96 support phrasal search. Since querying a single sentence is phrasal search, one might have
97 expected even better results from those queries.
98 %Due to the fact, that ChatNoir does not currently support phrasal search,
100 The intrinsic plagiarism based queries are document positionable, meaning that we can store
101 their position within the document. It is due to the fact, that
102 those queries are created from more or less subsequent words. As a result, they are also executed conditionally, for more
103 information see section~\ref{process}.
104 The position within the document were set to the
105 start position of the representative sentence.
106 They characterize only a specific portion of the suspicious document on the contrary to keyword based queries.
108 \subsection{Headers based queries}
109 The last type of queries were constructed from local headers of the document.
110 A header usually characterize briefly and accurately the following section, thus it
111 can be used as a search query. In real scenarios the headers should
112 be located using some document metadata, in that way we can distinguish for example more header levels.
113 In the case of PAN 12 competition we have detected headers according to several
114 basic rules. Those basic rules applied on most headers from given test corpus text files.
115 As a header is considered any line which has an empty line above and bellow the actual line
116 and is from 2 to 6 words in length also omitting stop words.
118 Note that length of header based queries are variable, thus they can be both specific
119 and general according to their length. They are also document positionable.
120 We calculated their position as start position of the following text.
122 \subsection{Combining and executing queries}~\label{process}
125 After each executed query the intermediate results of plagiarism
126 were calculated using the multi feature document comparison techniques described in section~\ref{yenya}.
127 This process leads to continuing lowering the number of executed queries, for more details see the following passages.
129 All queries from a given document were firstly preconstructed and they were afterwards sequentially executed
130 according to their priority.
131 The first all keyword based queries, the second
132 intrinsic plagiarism based and the last headers based, whilst we could omit some of the positionable queries during the process,
133 which is described further in this section.
134 The queries processing is outlined as Algorithm~\ref{alg:queries}, where for simplicity the snippet calculation and a web source download is omitted.
135 After executing a query the intermediate results were always
136 calculated as follows: For every query result in result page based
137 on a snippet to input suspicious document similarities, we decided whether to actually
138 download the resulting URL or not. Since the snippet contains portions of Web document to each
139 given keyword, we calculated pre-similarity as apportionment of every word match between the snipped and the suspicious document.
140 If there were at least 80\% match, we downloaded the web source for thorough investigation.
141 For each downloaded web document we calculated similarities with the input suspicious document
142 in the same way as described in section~\ref{yenya}. All similarities has been stored in form of intervals from within
143 the input suspicious document. In other words for every similar part between the downloaded
144 document and the suspicious document we stored the beginning position and the ending position of that part in
145 the suspicious document.
147 As a result of that, we can during processing further queries, which haven't been executed yet, omit those
148 of which document position intersects with any of already found similarities intervals. This procedure
149 leads us to lowering the total number of executed queries.
150 All downloaded documents, which have at least one similarity interval, are declared
151 as possible source of the plagiarism.
154 \renewcommand{\algorithmicrequire}{\textbf{Input:}}
155 \renewcommand{\algorithmicensure}{\textbf{Output:}}
158 \algsetup{indent=2em}
159 \begin{algorithm}[h!]
160 \caption{Queries execution}\label{alg:queries}
161 \begin{algorithmic}[1]
162 \REQUIRE suspicious document $d$, queries $Q_{KW}, Q_{Intrinsic}, Q_{Headers}$
163 %keyword, intrinsic and headers based queries $Q_{KW}, Q_{Intrinsic}, Q_{Headers}$,
165 \ENSURE plagiarism source candidate web documents $W_{plag}$
168 \STATE $I \leftarrow \emptyset; I \in \mathbb{N}^2$
169 \STATE $W \leftarrow \emptyset$
171 \FORALL{$q \in (Q_{KW} \cup Q_{Intrinsic} \cup Q_{Headers}) $}
172 \IF{$position(q)$ do not intersects with any interval $ \vec{i} \in I$}
173 \STATE $W \leftarrow execute(q)$
175 \STATE $I_{sub} \leftarrow get\_similarities(w, d)$ %\COMMENT{output is set of intervals similarities $[d_{start},d_{end}]$}
176 \STATE $I \leftarrow I \cup I_{sub}$
177 \IF{$I_{sub} \neq \emptyset$}
178 \STATE $W_{plag} \leftarrow W_{plag} \cup \{w\}$
188 \subsection{Queries comparison}
189 During the test phase there were extracted 133 keywords based queries, 165 intrinsic plagiarism
190 based queries and 331 headers based queries in total. Table~\ref{querycount} shows the arithmetic mean
191 of the query count per document. We can see that nearly half of the prepared queries were
192 omitted due to the fact, that there had been found a similarity including their document position.
197 \caption{\footnotesize The arithmetic mean of the query count and the omitted query count per document}
199 \begin{tabular}{|c|c|c|}
202 {\bf Query type} & {\bf Extracted}& {\bf Omitted} \\ \hline \hline
203 KW & 4.16 & N/A \\ \hline
204 Intrinsic & 5.16 & 2.35 \\ \hline
205 Headers & 10.34 & 4.75 \\ \hline
215 \caption{\footnotesize The total portion of similarities found, taking into account number of similarities regardless of interval sizes.}
217 \begin{tabular}{|c|c|}
220 {\bf Query type} & {\bf Similarities portion } \\ \hline \hline
221 KW & 72.5 \% \\ \hline
222 Intrinsic & 24.3 \% \\ \hline
223 Headers & 10.34 \% \\ \hline