]> www.fi.muni.cz Git - pan12-paper.git/commitdiff
Prvni draft
authorSimon Suchomel <xsuchom1@anxur.fi.muni.cz>
Wed, 15 Aug 2012 19:34:39 +0000 (21:34 +0200)
committerSimon Suchomel <xsuchom1@anxur.fi.muni.cz>
Wed, 15 Aug 2012 19:34:39 +0000 (21:34 +0200)
paper.tex
simon-searchengine.tex

index 9a907578daf0f480748324a59f8fa2bea28f2dd8..dd3c3b7eb3bca282660dc46085e1476516aead19 100755 (executable)
--- a/paper.tex
+++ b/paper.tex
@@ -7,6 +7,7 @@
 \usepackage{algorithm}
 \usepackage{algorithmic}
 \usepackage{amssymb}
 \usepackage{algorithm}
 \usepackage{algorithmic}
 \usepackage{amssymb}
+\usepackage{multirow}
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{document}
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{document}
@@ -33,17 +34,22 @@ Briefly describe the main ideas of your approach.
 
 Due to the increasing ease of plagiarism the plagiarism detection has nowadays become a need for many institutions.
 Especially for universities where modern learning methods include e-learning and a vast document sources are online available.
 
 Due to the increasing ease of plagiarism the plagiarism detection has nowadays become a need for many institutions.
 Especially for universities where modern learning methods include e-learning and a vast document sources are online available.
-In the Information System of Masaryk University there is also an antiplagiarism tool which is based upon the same principles as are shown in this paper.
+%In the Information System of Masaryk University~\cite{ismu} there is also an antiplagiarism tool which is based upon the same principles as are shown in this paper.
 The core methods for automatic plagiarism detection, which also work in practice on extensive collections of documents,
 are based on computation document similarities. In order to compute a similarity
 we need to possess the original and the plagiarized document.
 The core methods for automatic plagiarism detection, which also work in practice on extensive collections of documents,
 are based on computation document similarities. In order to compute a similarity
 we need to possess the original and the plagiarized document.
-The most straightforward method is to use an online search engine in order to enrich
-document base with potential plagiarized documents and evaluate the amount of plagiarism by detailed document comparison. 
-In this paper we introduce a method which has been used in PAN 2012 competition\footnote{\url{http://pan.webis.de/}}
-in plagiarism detection.
-In the first section we described our aproach to retrieve candidate documents for detailed document comparison from online sources.
+%The most straightforward method is to use an online search engine in order to enrich
+%document base with potential plagiarized documents and evaluate the amount of plagiarism by detailed document comparison. 
+%In this paper we introduce a method which has been used in PAN 2012 competition\footnote{\url{http://pan.webis.de/}}
+%in plagiarism detection.
+In the first section we will introduce methods for candidate document retrieval from online sources, which took part in
+PAN 2012  competition\footnote{\url{http://pan.webis.de/}} in plagiarism detection. 
+The task was to retrieve a set of candidate source documents that may had served as an original to plagiarize from.
+In the PAN 2012 candidate document retrieval test corpus, there were 32 text documents all contained at least one plagiarism case.
+The documents were approximately 30 KB of size, the smallest were 18 KB and the largest were 44 KB.
+
+In the second section we describe our approach of detailed document comparison.
  
  
-The next section describes used methods of computation document similarities.
 We also discuss the performance ...
 
 
 We also discuss the performance ...
 
 
@@ -53,14 +59,16 @@ We also discuss the performance ...
 
 \section{Conclusions}
 
 
 \section{Conclusions}
 
-We have presented methods for candidate document retrieval which has led to
-discovery the decent amount of plagiarism with minimizing the number of used queries.   
+We present methods for candidate document retrieval which lead to
+discovery the decent amount of plagiarism with minimizing the number of used queries. 
+The proposed methods are applicable in general to any type of text input with no apriori information about the input document.
+In PAN 2012 competition the proposed methods succeeded with similar amount of plagiarism detected with
+only a small fraction of used queries compared to the others.  
+
+   
 
 
-We have created three main types of queries: keywords based, intrinsic plagiarism based and headers based.
-....
-%We distinguish two properties of queries: positionable, conditionally executable  
 
 
-....
 \bibliographystyle{splncs03}
 \begin{raggedright}
 \bibliography{paper}
 \bibliographystyle{splncs03}
 \begin{raggedright}
 \bibliography{paper}
index 22f0bffae4892793366573d149950358c1c1a87d..817f171d2764dac9a31bfb5f50913288f4b25825 100755 (executable)
@@ -1,6 +1,6 @@
 \section{Candidate document retrieval}~\label{simon}
 The basic concept of candidate document retrieval is to use a web search
 \section{Candidate document retrieval}~\label{simon}
 The basic concept of candidate document retrieval is to use a web search
-engine to find suitable documents. In PAN 12 competition we used ChatNoir search
+engine to find suitable documents. In PAN 2012 competition we used ChatNoir search
 engine~\cite{chatnoir} which indexes the entire English part of the ClueWeb09 corpus.
 We can now reduce the problem to constructing appropriate queries for ChatNoir search engine.
 The goal is to retrieve similar documents, which contains the same passages as the source document
 engine~\cite{chatnoir} which indexes the entire English part of the ClueWeb09 corpus.
 We can now reduce the problem to constructing appropriate queries for ChatNoir search engine.
 The goal is to retrieve similar documents, which contains the same passages as the source document
@@ -8,10 +8,6 @@ or similar documents dealing with the same theme.
 The strongest emphasis has been places on minimizing the number of executed queries
 since they may be charged or time limited or number limited in the real world. 
 
 The strongest emphasis has been places on minimizing the number of executed queries
 since they may be charged or time limited or number limited in the real world. 
 
-In the PAN 12 test corpus, there were 32 text documents all contained at least one plagiarism case.
-The documents were approximately 30 KB of size, the smallest were 18 KB and the largest were 44 KB.
-We have used methods which are applicable in general to any type of text input with no apriori information about the input document.
-
 %All queries from a given document were firstly preconstructed and they were afterwards sequentially executed
 %according to their priority. After each executed query the intermediate results of plagiarism 
 %were calculated using the multi feature document comparison techniques described in section~\ref{yenya}.
 %All queries from a given document were firstly preconstructed and they were afterwards sequentially executed
 %according to their priority. After each executed query the intermediate results of plagiarism 
 %were calculated using the multi feature document comparison techniques described in section~\ref{yenya}.
@@ -92,7 +88,7 @@ We chose 6 words to cover higher portion of selected sentence and not to exceed
 the phrasal ChatNoir query limit.
 This type of query is actually looking for documents containing the very same or at least the very similar sentence,
 therefore we choose more than 5 word queries in order to narrow the search to more specific 
 the phrasal ChatNoir query limit.
 This type of query is actually looking for documents containing the very same or at least the very similar sentence,
 therefore we choose more than 5 word queries in order to narrow the search to more specific 
-results. Unfortunately in the time of PAN 12 competition the ChatNoir search engine did not
+results. Unfortunately in the time of PAN 2012 competition the ChatNoir search engine did not
 support phrasal search. Since querying a single sentence is phrasal search, one might have
 expected even better results from those queries.
  %Due to the fact, that ChatNoir does not currently support phrasal search,
 support phrasal search. Since querying a single sentence is phrasal search, one might have
 expected even better results from those queries.
  %Due to the fact, that ChatNoir does not currently support phrasal search,
@@ -110,10 +106,10 @@ The last type of queries were constructed from local headers of the document.
 A header usually characterize briefly and accurately the following section, thus it
 can be used as a search query. In real scenarios the headers should
 be located using some document metadata, in that way we can distinguish for example more header levels.
 A header usually characterize briefly and accurately the following section, thus it
 can be used as a search query. In real scenarios the headers should
 be located using some document metadata, in that way we can distinguish for example more header levels.
-In the case of PAN 12 competition we have detected headers according to several 
-basic rules. Those basic rules applied on most headers from given test corpus text files.
-As a header is considered any line which has an empty line above and bellow the actual line
+In the case of PAN 2012 competition we have detected headers according to several 
+basic rules: As a headers based query we considered any line which has an empty line above and bellow the actual line
 and is from 2 to 6 words in length also omitting stop words.
 and is from 2 to 6 words in length also omitting stop words.
+Those basic rules applied on most headers from given format of test corpus text files.
 
 Note that length of header based queries are variable, thus they can be both specific 
 and general according to their length. They are also document positionable. 
 
 Note that length of header based queries are variable, thus they can be both specific 
 and general according to their length. They are also document positionable. 
@@ -121,32 +117,37 @@ We calculated their position as start position of the following text.
 
 \subsection{Combining and executing queries}~\label{process}
 
 
 \subsection{Combining and executing queries}~\label{process}
 
-
-After each executed query the intermediate results of plagiarism 
-were calculated using the multi feature document comparison techniques described in section~\ref{yenya}.
-This process leads to continuing lowering the number of executed queries, for more details see the following passages.
-
 All queries from a given document were firstly preconstructed and they were afterwards sequentially executed
 according to their priority.
 The first all keyword based queries, the second
 All queries from a given document were firstly preconstructed and they were afterwards sequentially executed
 according to their priority.
 The first all keyword based queries, the second
-intrinsic plagiarism based and the last headers based, whilst we could omit some of the positionable queries during the process, 
-which is described further in this section. 
+intrinsic plagiarism based and the last headers based.
+During the process we could omit some of the positionable queries, purposing to 
+lower total number of executed queries.
+The condition for their omitting is described further in this section.
+
+After each executed query the intermediate results of plagiarism 
+were calculated using the multi feature document comparison techniques described in section~\ref{yenya}.
 The queries processing is outlined as Algorithm~\ref{alg:queries}, where for simplicity the snippet calculation and a web source download is omitted.
 After executing a query the intermediate results were always  
 The queries processing is outlined as Algorithm~\ref{alg:queries}, where for simplicity the snippet calculation and a web source download is omitted.
 After executing a query the intermediate results were always  
-calculated as follows: For every query result in result page based
+calculated as follows: 
+
+For every query result in result page based
 on a snippet to input suspicious document similarities, we decided whether to actually
 download the resulting URL or not. Since the snippet contains portions of Web document to each
 given keyword, we calculated pre-similarity as apportionment of every word match between the snipped and the suspicious document.
 If there were at least 80\% match, we downloaded the web source for thorough investigation.
 on a snippet to input suspicious document similarities, we decided whether to actually
 download the resulting URL or not. Since the snippet contains portions of Web document to each
 given keyword, we calculated pre-similarity as apportionment of every word match between the snipped and the suspicious document.
 If there were at least 80\% match, we downloaded the web source for thorough investigation.
+
 For each downloaded web document we calculated similarities with the input suspicious document
 For each downloaded web document we calculated similarities with the input suspicious document
-in the same way as described in section~\ref{yenya}. All similarities has been stored in form of intervals from within
+as a document pair described in section~\ref{yenya}.
+All similarities were stored in form of intervals from within
 the input suspicious document. In other words for every similar part between the downloaded 
 document and the suspicious document we stored the beginning position and the ending position of that part in
 the suspicious document.
 
 As a result of that, we can during processing further queries, which haven't been executed yet, omit those
 the input suspicious document. In other words for every similar part between the downloaded 
 document and the suspicious document we stored the beginning position and the ending position of that part in
 the suspicious document.
 
 As a result of that, we can during processing further queries, which haven't been executed yet, omit those
-of which document position intersects with any of already found similarities intervals. This procedure
-leads us to lowering the total number of executed queries.
+of which document position intersects with any of already found similarities intervals. 
+%This procedure leads us to lowering the total number of executed queries.
 All downloaded documents, which have at least one similarity interval, are declared
 as possible source of the plagiarism.  
 
 All downloaded documents, which have at least one similarity interval, are declared
 as possible source of the plagiarism.  
 
@@ -185,43 +186,85 @@ as possible source of the plagiarism.
 \end{algorithmic}
 \end{algorithm}
 
 \end{algorithmic}
 \end{algorithm}
 
-\subsection{Queries comparison}
+\subsection{Queries comparison}~\label{comparison}
 During the test phase there were extracted 133 keywords based queries, 165 intrinsic plagiarism
 During the test phase there were extracted 133 keywords based queries, 165 intrinsic plagiarism
-based queries and 331 headers based queries in total. Table~\ref{querycount} shows the arithmetic mean 
-of the query count per document. We can see that nearly half of the prepared queries were
-omitted due to the fact, that there had been found a similarity including their document position. 
-
+based queries and 331 headers based queries in total. Table~\ref{querycount} compares
+results according to query types.  
 \begin{center}
 \begin{table}[h]
 \begin{center}
 \begin{center}
 \begin{table}[h]
 \begin{center}
-\caption{\footnotesize The arithmetic mean of the query count and the omitted query count per document}
-\vspace{0.3 cm}
-\begin{tabular}{|c|c|c|}
+\begin{tabular}{|c|c|c|c|}
 \hline
 \hline
-\label{querycount}
-{\bf Query type} & {\bf Extracted}& {\bf Omitted} \\ \hline \hline
-KW        & 4.16  & N/A  \\ \hline 
-Intrinsic & 5.16  & 2.35  \\ \hline 
-Headers   & 10.34 & 4.75  \\ \hline 
+{\bf Query type} & {\bf Extracted}& {\bf Omitted}  & {\bf Similarities portion }\\ \hline \hline
+KW        & 4.16  & N/A  &  72.5 \% \\ \hline 
+Intrinsic & 5.16  & 2.35  & 24.3 \% \\ \hline 
+Headers   & 10.34 & 4.75  & 3.2 \% \\ \hline 
 \end{tabular}\\
 \end{center}
 \end{tabular}\\
 \end{center}
+\vspace{0.3 cm}
+\caption{\footnotesize Queries type comparison.}
+\label{querycount}
 \end{table}
 \end{center}
 \end{table}
 \end{center}
-
-
-\begin{center}
+The second and the third column
+represents the mean of the query count and the omitted query count per document. The fourth
+column shows total portion of similarities found, taking into account the number of similarities regardless of interval sizes.
+ We can see that nearly half of the prepared queries were
+omitted due to the fact, that there had been found a similarity covering their document position. 
+We can also see that there were detected about 5 cases 
+of potential plagiarism on average, by means of used AWFC intrinsic plagiarism detection method.
+Table~\ref{querycount} also shows keyword based queries as the most successful and
+headers based queries as the least successful. Despite the fact, that they were greatest 
+in number they ended with only more than a 3\% of total similarities found. Nevertheless, please
+note that the headers based queries were executed as the last, thus they were used only for
+finding undiscovered potential similarities. In order to really compere the query type performance, we
+would need to execute and evaluate them separately.
+To conclude this section we can say, that all types of queries were more or less successful. The headers based
+were executed last and in the process they were the least successful. The interesting
+ finding is the fact, that we can even greatly lower the number of executed queries.
+By omitting all of headers based queries we could lover the total number of executed queries by 45 \% with only
+3.2 \% of recall lost.
+%\begin{center}
 \begin{table}[h]
 \begin{center}
 \begin{table}[h]
 \begin{center}
-\caption{\footnotesize The total portion of similarities found, taking into account number of similarities regardless of interval sizes.}
-\vspace{0.3 cm}
-\begin{tabular}{|c|c|}
+{ \scriptsize
+\begin{tabular}{c c c c c c c c c c c c }
 \hline
 \hline
-\label{querySuccess}
-{\bf Query type} & {\bf Similarities portion } \\ \hline \hline
-KW        & 72.5 \%    \\ \hline 
-Intrinsic & 24.3 \%    \\ \hline 
-Headers   & 10.34 \%  \\ \hline 
-\end{tabular}\\
+& \multicolumn{2}{c}{\bf Total workload} & \multicolumn{2}{c}{\bf Time to 1st Result}&\multirow{2}{*}{\parbox{0.6cm}{\bf No \\ result}} & 
+\multicolumn{2}{c}{\bf Reported Srcs.} & \multicolumn{2}{c}{\bf Downloaded Srcs.} &
+ \multicolumn{2}{c}{\bf Retrieved Srcs.} \\ 
+{\bf Team}&{\bf Queries}&{\bf  Downloads}&{\bf Queries}&{\bf Downloads}
+& & {\bf Prec.}&{\bf Recall}&{\bf Prec.}&{\bf Recall}&{\bf Prec.}&{\bf Recall}\\ \hline \hline
+
+\parbox{2,3cm}{Gillam et al. \\ University of Surrey, UK} & 63.44 & 527.41 & 4.47 &
+ 25.88 & {\bf 1} & 0.6266 & 0.2493 & 0.0182 & {\bf 0.5567} & 0.0182 & {\bf 0.5567} \\ \hline
+\parbox{2,3cm}{ Jayapal \\ University of Sheffield, UK }&      67.06 & 173.47  & 8.78  & 13.50 &
+ 1 & {\bf 0.6582} & {\bf 0.2775} & 0.0709 & 0.4342 & {\bf 0.0698} & 0.4342 \\ \hline
+ \parbox{2,3cm}{Kong Leilei \\ Heilongjiang Institute of Technology,\\ China} & 551.06 & 
+ 326.66        & 80.59 & 27.47 & 2 & 0.5720 & 0.2351 & 0.0178 & 0.3742 & 0.0141 & 0.3788 \\ \hline
+\parbox{2,3cm}{Palkovskii et al. \\ Zhytomyr State University, Ukraine} & 63.13 &
+1026.72        & 27.28 & 318.94 & 6 & 0.4349 & 0.1203 & 0.0025 & 0.2133 & 0.0024 & 0.2133 \\ \hline
+
+\parbox{2,3cm}{\bf our approach}& {\bf 12.56} & {\bf 95.41} & {\bf 1.53} & {\bf 6.28} & 2 & 0.5177 & 0.2087 & {\bf 0.0813} &
+0.3513 & 0.0094 & 0.4519 \\ \hline 
+\end{tabular}\\}
 \end{center}
 \end{center}
+\vspace{0.3 cm}
+\caption{\footnotesize PAN 2012 candidate document retrieval results.}
+\label{candidateDocsResults}
 \end{table}
 \end{table}
-\end{center}
+%\end{center}
+
+Table~\ref{candidateDocsResults} shows results of PAN 2012 candidate document retrieval
+task as averages over the all 32 documents from the test corpus. Our approach led
+to obtain decent retrieval performance with very little total workload and time to 1st result.
+Also the 80 \% word match treshold in Web snippet appear to be suitable, since we
+also achieved the highest precision among downloaded sources.
+
+
+  
+