Dr Dimitrios Charalambidis
email: dimitrios.charalambidis@stjoseph.gr

ICT in the Future Classrooms and Teaching: Preparing the Knowledge Workers of the 21st Century

Keywords: ICT in education, knowledge workers, 21st century skills, 1 to 1 computing, future classroom scenarios, innovation in teaching and learning, professional development

A knowledge worker is a person that adds value to an organization by processing existing information to create new information and knowledge that could be used to define and solve problems. The future classroom is the cradle (for students) and the action field (for teachers) of a knowledge worker. It incarnates the vision for learning and teaching with the use of Information, Communications and Technology tools (ICT) in order to provide to the students significant 21st century skills such as personal and social responsibility, critical thinking, digital competence, as well as collaboration and communication abilities. From the teacher's point of view it demands understanding and creative use of ICT tools, organizational and administrative competences, use of up-to-date teaching scenarios, intuitive assessment methods and most of all a "lead and teach by example" attitude. Building the future classroom is all about delivering competent and effective people to the society, people that will be the key stakeholders in a world that seeks innovation and creativity in order to keep going socially, scientifically, economically, etc. In this paper we will provide insights about the reasons why a future classroom teacher should afford 21st century skills to his students and continuous professional development to himself.

Introduction

Why is so important for a classroom teacher to afford 21st century skills to his students? To help us get a better feel for the changes coming to schooling and learning, let's take a few minutes and do a thought test, submitting four questions to ourselves.

First, imagine that we have a child whom we love and care about. Moreover, this child is about to start kindergarten this year. Question #1: What will the world be like twenty years from now when our child finishes school? We can easily answer to that question if we try to remember what life was like twenty years ago and all the changes we have seen taking place until today. Question #2: What skills will our child need to be successful in a world twenty years from now? Inexorably, this question generates most of the 21st century skills covered in this article, including hard and soft skills as well as knowledge, values and behaviors [START_REF] Trilling | 21st Century Skills: Learning for Life in Our Times[END_REF].

Secondly, let us change our point of view and imagine that we run a small business, an R&D department or a university research laboratory. Furthermore, this business, R&D department or university lab is about to compete other innovative companies, R&D departments or labs locally and abroad. Question #3: What skills would we require from our staff in order to achieve innovative goals? This question also generates most of the times 21st century skills required from competitive business or academic environments.

Finally, let us look over our answers to the first three questions and consider how most students currently spend their time each and every day in school. Question #4: What would teaching and learning be like if it were designed and implemented around our answers to the first three questions?

Schooling: A Time for High-performance Cultures

The final stage of the upper secondary Hellenic educational system called Lykeio is primarily focused on teaching and learning what will be tested in the big government exams (Panellinies). In this case the spirit of innovation is dead, considering that the main goal is to get good examination marks that will eventually lead to enrollment in a high educational institution. Ironically, students and their parents think that Lykeio is unable to fulfil this preparatory role in a satisfying way. As a result, they seek resource to private tutorial schools (frontistiria). Frontistiria, a purely Greek phenomenon, undergo intensive preparations for the country-wide exams (Panellinies) [START_REF] Vretakou | Vocational education in Greece[END_REF].

This innovation-hostile schooling culture deprives the students as well as the teaching staff of all the benefits that innovation can bring to an unchanging, and thus obsolescent and "human-eating", system. Why is this educational system obsolescent? Because, it delivers highly educated underskilled professionals. Therefore, it produces long-term unemployed or underpaid people. Besides, long-term unemployment leads to an erosion of skills and knowledge. Why is this educational system "humaneating"? Because, it produces greatly unhappy and desperate people.

An underdeveloped school is striving to succeed by standard methods and it is unable to make or sustain improvements. Additionally, a traditional school is effective by standard methods and seeks improvement within old-style pedagogical and managerial methods. On the other hand, an innovative school goes beyond standard methods and measures of success. It constantly evaluates how effectively it is preparing students with core academic and 21st century skills. Twenty-first century schools are first and foremost effective organizations by design. They are schools where innovation and continuous improvement are core values. They have strong leaders who create learning environments, which motivate and attract the best educators. They also use metrics and analytics, because they know what gets measured gets done efficiently. Overall, innovative schools build high-performance cultures. However, as mentioned before, what mostly characterizes these schools is a determination to prepare students for 21st century professions. The jobs of the future will be complex and will require innovative and creative thinking. Jobs that are not, will be done by computers.

21st Century Skills: The World within and beyond the Classroom

In order to thrive in a digital world, students will need digital age proficiencies. It is important for every educational system to fulfill its mission in society, namely the preparation of students for the world beyond the classroom. Therefore, schools must comprehend and embrace 21st century skills within the context of rigorous academic standards. The concept of 21st century skills does not have a precise definition, but it is intended to convey the idea that changes in technology and culture are leading to changing demands in the workplace, and so the skills that are required in current and future workplace are different from those required in the past [START_REF] Kyllonen | Measurement of 21st Century Skills within the Common Core State Standards[END_REF].

Digital Literacy

In the early 1900s, a person who had acquired simple reading, writing, and calculating skills was considered literate. Today, all students need to learn to read critically, write persuasively, think and reason logically, and solve complex problems in mathematics and science. Digital cameras, graphics packages and streaming video are the means to communicate ideas in a visual and effective way. Students need good visualization skills to be able to decipher, interpret, detect patterns, and communicate using imagery. Digital literacy includes accessing information efficiently and effectively, evaluating information critically and competently, using information accurately and creatively [START_REF]The North Central Regional Educational Laboratory[END_REF].

Inventive Thinking

The interconnectedness of today's world brings with it unprecedented complexity. Interaction in such an environment requires individuals to be able to identify and react to changing conditions independently. Students should become self-directed learners who are able to analyze new conditions as they arise. Professionals should identify new skills that will be required to deal with these conditions and independently chart a course that responds to these changes. They should be able to take into account contingencies, anticipating changes, and understanding interdependencies within systems [START_REF]The North Central Regional Educational Laboratory[END_REF].

Global Awareness

Global awareness and international collaboration during schooling period results in more rounded individuals, encouraging students to see things from different perspectives and helping them to make informed decisions, acquiring transferable skills that will be useful to them and will remain with them for life. According to the UKs Association of Graduate Recruiters [5] companies cannot find enough applicants with the requisite skills to operate in an international market place, indicating that greater efforts by schools in fostering global awareness and international collaboration are needed to best prepare students for life and work in the 21st century [START_REF]Why students need a global awareness and understanding of other cultures[END_REF].

Creativity and Risk-taking

Innovation is impossible to achieve without taking a necessary amount of risk. Inevitably, every success sees failures along the way. A teacher should act and teach as an effective innovation leader, encouraging creativity and risk taking, while also practicing a tolerance for failure. Obsolete schooling systems punish failure with low grades. Instead, innovative schooling methods consider the fear of failure as an "innovation killer". Accordingly, failure and risk-talking is being seen and recognized as a learning experience [START_REF]Innovation is Creativity x Risk Taking[END_REF]. Creativity and risk-taking leads to a sense of initiative and entrepreneurship. The student acquires the ability to turn ideas into action as well as the ability to plan and manage projects in order to achieve objectives [START_REF]Key Competences for Lifelong Learning. A European Reference Framework[END_REF].

Teamwork

Information technology plays a key role in the ease with which individuals and groups collaborate. Email, faxes, voice mail, audio and video conferencing, chat rooms, shared documents, and virtual workspaces can provide timely, iterative collaborations. In today's wired, networked society it is imperative that students understand how to communicate using technology. This includes asynchronous and synchronous communication such as person-to-person email interactions, group interactions in virtual learning spaces (such as Learning Management Systems or LMS), chat rooms, interactive videoconferencing, etc. Such interactions require knowledge of etiquette often unique to that particular environment. Other dimensions introduced through global communication include scheduling over time zones, cultural diversity and language issues [START_REF]The North Central Regional Educational Laboratory[END_REF].

Learning to Learn

Learning to learn is the ability to pursue and persist in learning, to organise one's own learning, including through effective management of time and information, both individually and in groups. This competence includes awareness of one's learning process and needs, identifying available opportunities, and the ability to overcome obstacles in order to learn successfully. This competence means gaining, processing and assimilating new knowledge and skills as well as seeking and making use of guidance [START_REF]Key Competences for Lifelong Learning. A European Reference Framework[END_REF].

Preparing the Knowledge Workers of the Knowledge Age

The adoption of the 21st century skills in schooling will eventually create a new work force known as knowledge workers. Peter Drucker, the management guru, is credited with popularizing the term knowledge worker as long ago as 1968 [START_REF] Drucker | The age of discontinuity: Guidelines to our changing society[END_REF]. Back then he argued, "Today the center is the knowledge worker, the man or woman who applies to productive work ideas, concepts, and information rather than manual skill or brawn…Where the farmer was the backbone of any economy a century or two ago…knowledge is now the main cost, the main investment, and the main product of the advanced economy and the livelihood of the largest group in the population".

The knowledge workers of an organization produce knowledge capital, meaning experience, information, knowledge, learning, and skills. Of all the factors of production, knowledge capital creates the longest lasting competitive advantage of an innovative organization. A knowledge worker, as a producer and bearer of the knowledge capital and also as part of an unseparated whole, becomes the most value asset of his team, his company, his society, his country and therefore of the globalized world. One could argue that a knowledge worker simply signifies a more modern conception of a good job where workers are viewed as more than what they produce, but ultimately it is more than that [START_REF] Brinkley | Knowledge Workers and Knowledge Work. A Knowledge Economy Programme Report[END_REF].

Our digital world is currently formed in the Digital Age but moves quickly towards change and gradually is being transformed into the Knowledge Age. Knowledge Age alters the form of entrepreneurship. In Knowledge Age, knowledge and ideas will become the main source of economic growth (more important than land, labor, money, or other tangible resources). As well as this (and this is very important for education), knowledge's meaning is changing. Knowledge is no longer being thought of as 'stuff' that is developed (and stored) in the minds of experts, represented in books, and classified into disciplines. Instead, it is now thought of as being like a form of energy, as a system of networks and flows, something that does things, or makes things happen. In Knowledge Age, knowledge is defined and valued not for what it is, but for what it can do. It is produced, not by individual experts, but by a collective intelligence, meaning groups of people with complementary expertise who collaborate for specific purposes. These changes will eventually alter and define education systems and inexorably will prepare students to become the knowledge workers of tomorrow [START_REF]The Knowledge Age[END_REF].

Building the future classroom of the Knowledge Age

Technologically speaking, the school classrooms will become the cradle of the knowledge workers, thus the student and his teachers. From the teachers' point of view it demands understanding and creative use of ICT tools, organizational and administrative competences, use of up-to-date teaching scenarios, intuitive assessment methods, project, change and conflict management skills and most of all a "lead and teach by example" attitude. Building the future classroom is all about delivering competent and effective people to the society, people that will be the key stakeholders in a world that seeks innovation and creativity in order to keep going socially, scientifically, economically, etc. From the students' point of view all that is needed is courage, willingness and perseverance. Finally, from the parents' point of view an open-minded and proactive outlook that will permit them to spot and choose the proper schooling environment for their children.

In order to provide to the students significant 21st century skills, a pleiade of ICT tools is needed such as an efficient infrastructure (internet access, multi-touch LCD interactive boards, tablets, email accounts, collaboration and e-learning platforms, video recording and editing equipment, live video-to-video supporting interactive infrastructures like those proposed and implemented by LiveCity EU program, etc.) as well as the proper educational content. The book-based paradigm, which has dominated the organization of schooling for two centuries, can't really become much more efficient [START_REF] Lloyd | Schooling at the Speed of Thought: A blueprint for making schooling more effective[END_REF] and therefore new approaches such as internet research, interactive e-books and teacher-student content co-creation are needed.

Conclusion

How well we educate our children, whether or not they learn the skills now needed to participate and thrive in global economy, will determine the future health, wealth, and welfare of everyone. This is the good scenario, answering the question #2 of the introduction: What skills will our child need to be successful in a world twenty years from now? The bad scenario would be to live in conditions of an endless economic depression where unemployment changes from a microeconomic problem into a structural one. In this case the unemployed workers lack the skills needed for the jobs, or they are not living in the part of the country or the world where the jobs are available. This is how our country would simply become in the long run; a no man's / no worker's land. Also, the recent global recession has given us a painful glimpse of what life could be like if we don't succeed in providing our children a 21st century education. Though the causes of the global recession are not directly related to education, the results provide us with an important lesson.


Zafeiria-Marina Ioannou
email: ioannouz@ceid.upatras.gr

Nikolaos Nodarakis
email: nodarakis@ceid.upatras.gr

Spyros Sioutas
email: sioutas@ionio.gr

Athanasios Tsakalidis

Giannis Tzimas
email: tzimas@cti.gr

Mining Biological Data on the Cloud -A MapReduce Approach

Keywords: Bioinformatics, Data mining, Text mining, Clustering, MapReduce, Hadoop

During last decades, bioinformatics has proven to be an emerging field of research leading to the development of a wide variety of applications. The primary goal of bioinformatics is to detect useful knowledge hidden under large volumes biological and biomedical data, gain a greater insight into their relationships and, therefore, enhance the discovery and the comprehension of biological processes. To achieve this, a great number of text mining techniques have been developed that efficiently manage and disclose meaningful patterns and correlations from biological and biomedical data repositories. However, as the volume of data grows rapidly these techniques cannot cope with the computational burden that is produced since they apply only in centralized environments. Consequently, a turn into distributed and parallel solutions is indispensable. In the context of this work, we propose an efficient and scalable solution, in the MapReduce framework, for mining and analyzing biological and biomedical data.

Introduction

The term data mining [START_REF] Han | Data Mining: Concepts and Techniques[END_REF] refers to the process of data analysis to identify interesting and useful information and knowledge from huge collections of data. From a more general and more intuitive aspect, data mining is a research field in computer science that employs a wide diversity of well-established statistical and machine learning techniques, such as neural networks, to derive hidden correlations, patterns and trends from large datasets. Bioinformatics, is a prominent domain, among several others, where the existing data mining algorithms are applicable and enhance the process of knowledge discovery. Especially, as the volume of biological and biomedical data accumulated in large repositories continues to expand at exponential rates, data mining techniques are of critical importance in extracting knowledge efficiently from such datasets. Adding the need to manage heterogeneous data, that in the vast majority are unstructured biomedical text documents (Biomedical Text Mining [START_REF] Ananiadou | Text Mining for Biology and Biomedicine[END_REF]), and automate the exploration procedure of them, it is easy to understand why data mining plays a fundamental role in bionformatics domain [START_REF] Wang | Data Mining in Bioinformatics[END_REF].

Despite how efficient a data mining technique might be, as the volume of data collections continues to expand at some point it will be impractical to use due to limits in resources posed by the centralized environment where the algorithm is executed. Typical Biomedical Text Mining tasks include automatic extraction of protein-protein interactions, named entity recognition, text classification and terminology extract. Consider PubMed4 , which is the most widely used biomedical bibliographic text base with millions of records and grows by a rate of 40,000 publications per month. To perform such tasks in an enormous corpus like PubMed is unthinkable. Most existing methods in literature [START_REF] Cohen | A Survey of Current Work in Biomedical Text Mining[END_REF][START_REF] Dai | A Survey of State of the Art Biomedical Text Mining Techniques for Semantic Analysis[END_REF][START_REF] Ioannou | A Text Mining Approach for Biomedical Documents[END_REF][START_REF] Ioannou | Genome-based Population Clustering: Nuggets of Truth Buried in a Pile of Numbers?[END_REF][START_REF] Lu | Pubmed and Beyond: A Survey of Web Tools for Searching Biomedical Literature[END_REF][START_REF] Manconi | Literature Retrieval and Mining in Bioinformatics: State of the Art and Challenges[END_REF] apply to a few hundreds or thousands of records. As a result, high scalable implementations are required. Cloud computing technologies provide tools and infrastructure to create such solutions and manage the input data in a distributed way among multiple servers. The most popular and notably efficient tool is the MapReduce [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF] programming model, developed by Google, for processing large scale data.

The method proposed in the context of this work, is under development and is an extension of the work in [START_REF] Ioannou | A Set of Novel Mining Tools for Efficient Biological Knowledge Discovery[END_REF] which proposes an automatic and efficient clustering approach that performs well on multiple types of biological and biomedical data. In [START_REF] Ioannou | A Set of Novel Mining Tools for Efficient Biological Knowledge Discovery[END_REF], two mining tools were developed, Bio Search Engine which is a text mining tool working with biomedical literature acquired from PubMed and Genome-Based Population Clustering tool which extracts knowledge from data acquired from FINDbase [START_REF] Georgitsi | Population-Specific Documentation of Pharmacogenomic Markers and their Allelic Frequencies in FINDbase[END_REF][START_REF] Van Baal | FINDbase: A Relational Database Recording Frequencies of Genetic Defects Leading to Inherited Disorders Worldwide[END_REF][START_REF] Viennas | Population-Ethnic Group Specific Genome Variation Allele Frequency Data: A Querying and Visualization Journey[END_REF]. FINDbase5 is an online resource documenting frequencies of pathogenic genetic variations leading to inherited disorders in various populations worldwide. In this paper, we take the data mining technique proposed in [START_REF] Ioannou | A Set of Novel Mining Tools for Efficient Biological Knowledge Discovery[END_REF] one step further and adapt it to the needs of big data analysis. We propose a novel and effective data mining technique for extracting valuable knowledge from biological and biomedical data in the cloud. We focus only on Biomedical Text Mining, since the size of PubMed is adequately big and fit the needs of MapReduce model in contrary to the size of existing genetic and mutation databases (like FINDbase). Our approach uses Hadoop [START_REF]The apache software foundation: Hadoop homepage[END_REF][START_REF] White | Hadoop: The Definitive Guide, 3rd Edition[END_REF], the open source MapReduce implementation, and Mahout [START_REF]The apache software foundation: Mahout homepage[END_REF] which is a scalable machine learning library built on top of Hadoop.

The remainder of the paper is organized as follows: Section 2 discusses related work, Section 3 provides a full analysis of the algorithm and proceeds into a detail examination of all of its steps and finally Section 4 concludes the paper and presents future steps.

Related Work

Biomedical Text Mining

Biomedical Text Mining or BioNLP is the field of research that deals with the automatic processing, retrieval and analysis of scientific texts and more generally literature from the biomedical domain by applying text mining techniques aimed at uncovering previously unknown knowledge. Currently, there has been significant research advances in the area of biomedical text mining, including named entity recognition, text classification, terminology extraction, relationship extraction and hypothesis generation [START_REF] Cohen | A Survey of Current Work in Biomedical Text Mining[END_REF].

Text Document clustering, unlike text document classification, is an unsupervised learning process that does not depend on prior knowledge or domain expertise. In particular, document clustering is the task where similar documents are grouped into clusters. Existing biomedical text mining systems that cluster results into topics [START_REF] Lu | Pubmed and Beyond: A Survey of Web Tools for Searching Biomedical Literature[END_REF] include GOPubMed6 , ClusterMed7 and XplorMed8 . GOPubMed uses both Medical Subject Headings (MeSH) terms and Gene Ontology (GO) in order to organize the search results and, thus, to enhance the user navigation and the search possibilities. It is also capable of sorting results into four categories: "what", "who", "where" and "when". Another prominent example is ClusterMed that also employs clustering in six different ways: i) Title, Abstract and MeSH terms, ii) Title and Abstract, iii) MeSH terms only, iv) Author names, v) Affiliations, vi) Date of publication. XplorMed organizes results by MeSH categories, extracts topic keywords and their co-occurrences and furthermore it provides an interactive navigation through abstracts. For a comprehensive survey of such biomedical text mining systems along with their various characteristics and features, one can consult [START_REF] Cohen | A Survey of Current Work in Biomedical Text Mining[END_REF][START_REF] Dai | A Survey of State of the Art Biomedical Text Mining Techniques for Semantic Analysis[END_REF][START_REF] Lu | Pubmed and Beyond: A Survey of Web Tools for Searching Biomedical Literature[END_REF][START_REF] Manconi | Literature Retrieval and Mining in Bioinformatics: State of the Art and Challenges[END_REF].

It should be noted that besides clustering, there are a handful of other fruitful techniques that have been applied to mine biological text data, that either deviate apart from the bag-of-words model and the tf-idf representation or employ other learning techniques different from clustering. From these approaches, worth to be mentioned are approaches based on the incorporation of semantic information and ontologies in order to correctly disambiguate the meaning of various terms. We could also refer to the employment of second order n-gram Markov models, probabilistic suffix analysis, and named entity recognition. Furthermore special mentioning deserves automatic term recognition techniques, that recognize domain concepts and using automatic term restructuring technique permit the text content organization into knowledge structures (terminologies). More details for these techniques can be found in [START_REF] Ananiadou | Text Mining for Biology and Biomedicine[END_REF].

Hadoop and MapReduce Framework

In the context of this work, we focus on the use of Hadoop which is an open source framework for managing large-scale data and running computationally heavy tasks in a parallel and distributed manner. Hadoop follows MapReduce principles and is designed to scale up from single servers to thousands of machines, each offering local computation and storage. Here we describe in more details how it works.

A task performing a specific computation in Hadoop is called MapReduce job. The input data for each job is split and distributed among the nodes consisting the cluster and then is processed by a number of tasks executed on these nodes. The categories in which these tasks belong are defined as Map and Reduce. Each Map task receives input data and processes them by calling a user-defined Map function which outputs a set of intermediate key-value pairs. After that, a Shuffle process groups all intermediate values associated with the same key I and each group is assigned to the corresponding Reduce task. Each Reduce task also calls a user-defined Reduce function which accepts an intermediate key I and a set of values for that key and outputs the final set of key-value pairs. The intermediate values are supplied to the Reduce function via an iterator in order for the system to handle lists of values that are too large to fit in memory. Using the MapReduce programming model, the user does not have to worry about how the program is executed over the cluster or designing fault tolerance protocols in case a node fails. The system handles these issues itself thus allowing the user to focus on his own problem exclusively.

Mahout is a scalable machine learning library that consists of a set of data mining algorithms (e.g. k-means clustering, naive Bayes classifier etc.) implemented in the Hadoop MapReduce framework.

The Proposed Mining Algorithm

In the following subsections, we present in detail the steps of the proposed data mining technique. The solution consists of a combination of MapReduce jobs that run either on the Hadoop or Mahout framework. The basic steps of the algorithm are: 1) Preprocessing of the data collection in order to represent them in a more processable structure, 2) Latent Semantic Indexing and 3) Coarse Clustering in an attempt to generate an initial partition of data, 4) Agglomerative Hierarchical Clustering [START_REF] Steinbach | A Comparison of Document Clustering Techniques[END_REF] in order to reduce the number of the initial clusters (in case that the number is relatively large) and 5) spherical k-means algorithm [START_REF] Dhillon | Iterative Clustering of High Dimensional Text Data Augmented by Local Search[END_REF][START_REF] Kogan | Introduction to Clustering Large and High-Dimensional Data[END_REF] in order to enhance the quality of the proposed clustering. Each of the aforementioned steps is a MapReduce job (or a series of MapReduce jobs) and the output of each MapReduce job feeds the input of the next job in the sequence. Note that we combine hierarchical and non-hierarchical clustering techniques to improve the efficiency and accuracy of clustering [START_REF] Chen | Novel Hybrid Hierarchical-K-means Clustering Method (H-K-means) for Microarray Analysis[END_REF][START_REF] Zhang | K-means Clustering Algorithm with Improved Initial Center, Knowledge Discovery and Data Mining[END_REF]. An overview of the algorithmic process is depicted in Figure 1.

Preprocessing the Data Collection

Data preprocessing is an essential step in the data mining process that includes feature selection and representation of data. The data elements have to be transformed into a representation suitable for computational use. For this purpose, we display a method for preprocessing the corpus of PubMed which constitutes the input dataset of our mining method.

The bag-of-words model is the most widely used document representation adopted in the text clustering algorithms. According to the principles of this model, each document is represented as a sequence of terms/words. Initially, we parse each document and distinguish the lexical units (tokens) that constitute it. After this, we proceed two kinds of feature reduction. At first, we remove the stopwords. A stopword is defined as a term which is not thought to convey any meaning as a dimension of vector space. Typically, a compilation of stopwords consists of very common words such as articles, preposition etc. By removing them, we achieve a reduction in the dimensionality of the index by 20-30%. The second step involves Part-Of-Speech Tagging (POS Tagging) and lemmatization. POS Tagging is the process of assigning a particular part of speech (e.g. noun, verb, adjective, etc.) to each term of a document while lemmatization is the process of reducing the words to their basic form (lemma). Consequently, we end up with the unique lemmas of noun words of all documents. To put through the POS Tagging process we use the GENIA Tagger9 which is specifically tuned for biomedical texts.

Subsequently, according to the vector space model [START_REF] Baeza-Yates | Modern Information Retrieval: The Concepts and Technology behind Search[END_REF], each document is represented as a vector of m dimensions, where m is the number of unique lemmas. For each document, we measure the significance of each lemma in its content using the TF-IDF (Term Frequency -Inverse Document Frequency) scheme. The term frequency is simply the number of times a lemma appears in a document, whereas the inverse document frequency is a measure obtained by dividing the total number of documents by the number of the documents containing the term. So, more formally, we define T F -IDF (t, d, D) = T F (t, d)• IDF (t, D), where IDF (t, D) = log |D| |{d∈D:t∈d}| . Consequently, lemmas that appear frequently in a document but have low document frequency in the whole data collection are given a high value in the TF-IDF scheme.

In order to preprocess the data in the way we described, we developed a MapReduce Job. The Map function takes as input the data collection of PubMed, proceeds to POS Tagging of the terms and extracts the lemmas of noun words. For each lemma, it outputs a key-value pair in the form <lemma, d, 1>, where lemma is the key and the value composes of number 1 and the name of document that contains the lemma. The Reduce function retrieves the unique lemmas and calculates the TF-IDF value for each document they belong. Next, it outputs key-value pairs in the format <lemma, tfidf, d>, where lemma is the key and the value composes of the TF-IDF weight and the name of the document that is binded with the lemma and the TF-IDF value. The overall outcome of this job is a term-document matrix A of dimension m × n, where m is the number of unique lemmas and n is the number of documents.

Latent Semantic Indexing

Latent Semantic Indexing (LSI) [START_REF] Baeza-Yates | Modern Information Retrieval: The Concepts and Technology behind Search[END_REF] is a prominent indexing and retrieval method for extracting hidden relationships between terms and concepts contained in large, unstructured collections of documents. The main idea of the method is the projection of document vectors in a new low-dimensional space through the Singular Value Decomposition (SVD) of the term-document matrix A. This can significantly reduce the number of computations needed in the next steps of our data mining algorithm.

The Singular Value Decomposition of an m×n matrix A of rank r expresses A as a product of three simpler matrices, A = U SV T where S = diag(σ 1 , ..., σ r ) is a diagonal matrix containing the set of singular values, U = (u 1 , ..., u r ) is an m × r matrix whose columns are orthonormal and V = (v 1 , ..., v r ) is an n × r matrix which is also column-orthonormal. LSI omits all but the k largest singular values in the above decomposition, for some appropriate k which will be the dimension of the low-dimensional space referred to in the description above. It should be small enough to enable fast retrieval and large enough to adequately capture the structure of the corpus. Consequently, after SVD and dimension reduction, a matrix

A k = U k S k V T k is created, where S k = diag(σ 1 , ..., σ k ), U k = (u 1 , ..., u k ) and V k = (v 1 , ..., v k ).
To this end, we utilize the Singular Value Decomposition algorithm implemented in Mahout. More specifically, Mahout implements a version of Lanczos algorithm10 as a series of MapReduce jobs. We provide as input to the algorithm the matrix A, the number of row and columns and the rank of the output matrix and it produces the V k and S k matrices, needed for the next step of our solution.

Coarse (initial) Clustering

Fuzzy Clustering [START_REF] Inoue | Fuzzy Clustering Based on Cooccurence Matrix and Its Application to Data Retrieval[END_REF] has been widely used in the area of information retrieval and data mining. In traditional Fuzzy Clustering Methods, data elements can belong to more than one clusters, and each data element is associated to every cluster based on a membership function, that differentiates on the specific cluster. In our approach, we interpret the results of the LSI transformation of the initial matrix A as a form of fuzzy clustering and then we transform the fuzzy clustering to a hard-crisp clustering by assigning each document to exactly one cluster, the cluster where the document has the highest degree of participation. In this way, we produce an initial rough clustering of documents. Later these initial clusters are going to be reduced (Agglomerative Hierarchical Clustering) and furthermore re-organized (spherical k-means algorithm) in order to enhance their quality.

In particular, we rely on the n × k matrix V k S k , produced by SVD in the previous step, and consider its k columns as a set of k clusters and the n rows as documents. Each value in position (i, j) of V k S k defines the document's i degree of participation to the cluster j. This fuzzy clustering is transformed to a crisp clustering by assigning each document to exactly one cluster, where the document has the highest degree of participation according to the values of the V k S k .

To perform the fuzzy clustering we run the respective algorithm implemented in the Mahout framework. The algorithm works as follows:

-Each document is assigned to the cluster where it has the highest degree of participation according to the membership values of V k S k . -Each initial cluster is represented by a central vector c [START_REF] Steinbach | A Comparison of Document Clustering Techniques[END_REF], called centroid, where c = 1

|S| x∈S x.
More specifically, the Map function reads the probability membership values of documents and assigns them to the corresponding cluster. The records produced by the Map function are key-value pairs where the key is a cluster identifier and the value is a vector that represents a row of the matrix A. The Reduce function receives all the key-value pairs from the map task and produces a centroid for each cluster. The key of the output record is a cluster identifier and the value is the centroid of the cluster.

Hierarchical clustering

Hierarchical Clustering [START_REF] Steinbach | A Comparison of Document Clustering Techniques[END_REF] is a widely used data analysis method for identifying relatively homogenous clusters of experimental data items based on selected measured characteristics. Commonly, hierarchical clustering techniques generate a set of nested clusters, with a single all-inclusive cluster at the top and single point clusters at the bottom. The result of a hierarchical clustering algorithm can be graphically displayed as tree, called a dendrogram.

Hierarchical clustering algorithms can be divided into two basic approaches: agglomerative (merging) and divisive (splitting). In the context of this work, we adopt the agglomerative approach in an attempt to reduce the number of initial clusters, and develop an iterative algorithm in the Hadoop framework. The agglomerative approach is a bottom-up clustering method that starts with all the data elements as individual clusters and at each step it merges the most similar or closest pair of clusters, based on a cluster similarity or distance measure. The steps are repeated until the desired number of clusters is obtained according to a user defined parameter.

The algorithm consists of an iterative step with two phases. Phase 1 computes similarity between the clusters and phase 2 merges the two most similar clusters. The process repeats until the above prerequisite is fulfilled. The agglomerative approach attempts to shrink the number of initial clusters produced by LSI and fuzzy clustering since the produced number of clusters is equal to the LSI dimension which is generally high. At each step, the algorithm merges the most similar pair of clusters based on the UPGMA (Unweighted Pair Group Method with Arithmetic Mean) scheme:

similarity(cluster1, cluster2) = x∈cluster1,y∈cluster2 cos(x, y) size(cluster1) • size(cluster2)

Spherical k-means Algorithm

The k-means algorithm is an efficient and well known method for clustering large portions of data. Typically, the k-means algorithm determines the distance (similarity) between a data element in a cluster and its cluster centroid by using the squared Euclidean distance measure. The spherical k-means algorithm [START_REF] Kogan | Introduction to Clustering Large and High-Dimensional Data[END_REF] is a variant of the original method that uses the cosine similarity as distance measure and achieves better results on high-dimensional data such as text documents. Note however that the above mentioned algorithm is significantly sensitive to the initialization procedure meaning that its clustering performance depends heavily on the initial selection of cluster centroids. As a consequence, this selection constitutes a task of crucial importance. In an attempt to overcome this issue and with the goal of enhancing the achieved performance, we initialize the spherical k-means algorithm with the cluster centroids obtained by the previous steps of the proposed technique. Furthermore, the motivation for applying the spherical k-means as the final step of our clustering approach, is to enhance the quality and the precision of the clustering produced by the previous steps of the proposed technique.

More specifically, we utilize a MapReduce version of a refinement algorithm [START_REF] Kogan | Introduction to Clustering Large and High-Dimensional Data[END_REF] that uses local search in order to refine the clusters generated by spherical k-means. The algorithm alternates between two steps (a) first variation and (b) spherical k-means. The first step moves a single data element from one cluster to another increasing in this way the value of the objective function of the clustering. A sequence of first variation moves allows an escape from a local maximum, so that fresh iterations of spherical k-means (in the second step) can further increase the objective function value. The k-means algorithm is implemented in the Mahout framework and we provide the cosine similarity as input parameter, in order for the method to behave similar to the spherical k-means approach.

In this paper, we present a novel data mining algorithm for clustering biological and biomedical data in the cloud. The method constitutes of a series of steps/algorithms and is currently under development. We utilize the Hadoop and Mahout frameworks to implement existing centralized data mining algorithms that fit the MapReduce programming model. In the near future, we intend to finish the implementation of our approach and run extensive experiments using the enormous data repository of PubMed. We want to compare the efficiency of our method with existing centralized methods and measure the gain we earn using parallel and distributed solutions instead of centralized ones. Moreover, we plan to explore more existing data mining techniques and create respective MapReduce versions of them to experiment with.

Fig. 1 .

 1 Fig. 1. Overview of MapReduce Clustering Algorithm

http://www.ncbi.nlm.nih.gov/pubmed/

http://www.findbase.org

http://www.gopubmed.org/web/gopubmed/

http://clustermed.info/

http://www.ogic.ca/projects/xplormed/

http://www.nactem.ac.uk/tsujii/GENIA/tagger/

http://en.wikipedia.org/wiki/Lanczos algorithm

Acknowledgements. This research has been co-financed by the European Union (European Social Fund ESF) and Greek national funds through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework (NSRF) -Research Funding Program: Thales. Investing in knowledge society through the European Social Fund.


Costas S Iliopoulos
email: c.iliopoulos@kcl.ac.uk

Manal Mohamed

On-line Minimum Closed Covers

Keywords: String, Cover, Closed String, Algorithm

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The computation of various kinds of "regularities" in a given string has been of interest for more than a century. Such interest has been initiated with the computation of periodicities [START_REF] Thue | Über Unendliche Zeichenreihen[END_REF] and later extended, in response to applications arising in data compression and molecular biology, to other concepts of regularities. Apostolico et al introduced the idea of cover (quasiperiod); that is, a substring u is called a cover of given string w if concatenations of u generates w. Clearly the notion of a cover is one way to grasp the repetitive structures of w [START_REF] Apostolico | Optimal Superprimitivity Testing for Strings[END_REF]. Several algorithms to compute the covers of a given string were published in the 1990s [START_REF] Breslauer | An On-Line String Superprimitivity Test[END_REF][START_REF] Moore | An Optimal Algorithm to Compute All the Covers of a String[END_REF][START_REF] Iliopoulos | An O(n log n) Algorithm for Computing All Maximal Quasiperiodicities in Strings[END_REF], culminating in an algorithm [START_REF] Li | Computing the Cover Array in Linear Time[END_REF] that in O(n) time computes a cover array specifying all the covers of every prefix of w.

The idea of covers was further extended to consider a set of substrings of w that covers w rather than a single substring. In particular, aiming for a set of minimum size, the k-covers problem calculates for a particular integer k, a set of substrings all of length k that covers w [START_REF] Iliopoulos | New Complexity Results for the k-Covers Problem[END_REF]. Also, the λ-covers problem finds a minimum set of λ substrings of equal length that covers w with the minimum error, under a variety of distance models [START_REF] Guo | Computing the λ-Covers of a String[END_REF]. More recently, the palindromic covers was proposed in which a minimum set of palindromic substrings that covers w is calculated [START_REF] Tomohiro | Computing Palindromic Factorizations and Palindromic Covers On-line[END_REF]. In this paper, we consider yet another set of substrings that cover w, namely the set of closed substrings. We chose to investigate the idea of a cover using set of closed substrings due to the well-studied relation between palindromic and closed strings [START_REF] Bucci | Rich and Periodic-Like Words[END_REF]4]. We aim to design an algorithm that calculates a minimum set of closed substrings of w that covers a given string w.

More precisely, a string w is called a closed string if it is empty or it has a factor (different from the string itself) occurring exactly twice in, as a prefix and as a suffix, that is, with no internal occurrences. Initially, the notion of closed string has been proposed and characterized by Fici [START_REF] Fici | A Classification of Trapezoidal Words[END_REF] as a way to classify trapezoidal strings. In a more recent work, Badkobeh,Fici and Lipták [4] showed that any string of length n contains at least n + 1 closed factors. They also investigated and provided a combinatorial characterization of the set of strings with the smallest number of closed factors which they called C-poor strings.

The paper is organized as follows: in Section 2, we state the preliminaries used throughout the paper. In Section 3, we define the longest closed cover problem and detail our algorithm.

Preliminaries

Throughout the paper w denotes a string of length n defined on a finite alphabet Σ. We use w[i], for i = 1, 2, . . . , n, to denote the i-th letter of w, and w[i..j] as a notation for the factor (substring)

w[i]w[i + 1] • • • w[j] of w.
The length of w, the non-negative integer n, is denoted by |w|. The empty string has length zero and is denoted by ϵ. A power is a string that is a concatenation of copies of another string.

A prefix (resp. a suffix) of a string w is any string u such that w = uz (resp. w = zu) for some string z. A factor of w is a prefix of a suffix (or equivalently, a suffix of a prefix) of w. A border of w is any string u ̸ = w that is a prefix and a suffix of w. From the definitions, we have that ϵ is a prefix, a suffix and a factor of any string. An occurrence of a factor u in a string w is a pair of positions (i, j) such that 1 ≤ i, j ≤ n and u = w[i..j].

We recall the definition of closed string given in [START_REF] Fici | A Classification of Trapezoidal Words[END_REF] Definition 1. We say that w is closed if and only if it is empty or has a factor v ̸ = w occurring exactly twice in w, as a prefix and as a suffix of w.

The string aba is closed, since its factor a appears only as a prefix and as a suffix. On the contrary, a string abaa is not closed. Note that for any letter a ∈ Σ and for any n > 0, the string a n is closed, as a n-1 is a factor that occurs only as a prefix and a suffix in it. More generally, any string that is a power is closed.

The concept of closed string is equivalent to that of periodic-like string [START_REF] Carpi | Periodic-Like Words, Periodicity and Boxes[END_REF]. A string w is periodic-like if its longest repeated prefix does not appear in w followed by different letters. The concept of closed string is also related to complete return to a factor u in w, as considered in [START_REF] Glen | Palindromic Richness[END_REF]. A complete return to u in w is any factor of w having exactly two occurrences of u, one as a prefix and one as a suffix. Therefore, w is a closed string if and only if w is a complete return to its longest repeated prefix.

A factor of w that is closed is called a closed factor of w. For any string w of length n, the number of closed factors of w is at least n + 1. In particular, a string w of length n is called C-poor if it has exactly n + 1 closed factors, i.e., if it contains the smallest number of closed factors a string of length n can contain. For example, the string abca of length 4 is a C-poor as it has 5 closed factors namely ϵ, a, b, c and abca, whereas the string ababa of length 5 is not C-poor as it has 8 closed factors: ϵ, a, b, aba, abab, bab, baba, and ababa. Note that there are C-poor strings that are not closed, e.g. ab, and closed strings that are not C-poor, e.g. abab.

A set of subintervals [1, n]. The size of the cover is the number

{[b 1 , e 1 ], • • • , [b h , e h ]} is called a cover of interval [1, n] if ∪ h i=1 [b i , e i ] =
h of subintervals in it. A cover {[b 1 , e 1 ], ..., [b h , e h ]} of [1, n] is said to be a closed cover of string w of length n, if w[b i ..e i ]
is a closed factor of w for all 1 ≤ i ≤ h. A minimum closed cover of w is a closed cover of w with the smallest possible size; note that a minimum closed cover is not unique.

Tools

Suffix Array: The Suffix Array of the string w is a data structure used for indexing its content. It is comprised of two arrays:

-The array SA which stores the list of positions of w associated with its suffixes in increasing lexicographic order. Thus SA is indexes by the ranks of suffixes in their sorted list. -The second array, LCP, which stores the longest common prefixes between consecutive suffixes in the sorted list. That is

LCP[r] = |lcp(SA[r -1], SA[r])|,
where lcp(i, j) is the longest common prefix of the two suffixes of w starting at positions i and j, i.e. w[i.

.n] and w[j.

.n].

The computation of the suffix array can be done in time O(n log n) in the comparison model [START_REF] Manber | Suffix Arrays: A New Method for On-Line Search[END_REF]. For an integer alphabet, the suffix array can be built in time O(n) [START_REF] Kärkkäinen | Simpler Linear Work Suffix Array Construction[END_REF][START_REF] Kim | Linear-Time Construction of Suffix Arrays[END_REF][START_REF] Ko | Space Efficient Linear Time Construction of Suffix Arrays[END_REF].

Longest Previous Factor:

The Longest Previous Factor array has been introduced in [START_REF] Crochemore | Computing Longest Previous Factor in Linear Time and Applications[END_REF] and gives for each position i in a given string w the length of the longest factor that occurs both at position i and to the left of i in w. The Longest Previous Factor is defined by LPF[1] = 0 and for 1

< i ≤ n, by LPF[i] = max {k | w[i..i + k -1] = w[j..j + k -1],
for some 1 ≤ j < i}. For example, for string abbaba, the Longest Previous factor corresponding to position 4 is 2 because ab is the longest factor at position 4 that appears before (at position 1). In the paper we make use of the following known result on LPF from [START_REF] Crochemore | Computing the Longest Previous Factor[END_REF]:

Lemma 1. The Longest Previous Factor array of a string of length n on an integer alphabet can be built from the read-write Suffix Array and Longest Common Prefix array in time O(n) (independently of the alphabet size) with a constant amount of extra memory space.

The Longest Previous Factor algorithm can compute for no extra cost an array FPOS that stores the positions of the longest previous factor if such factor exists, that is

FPOS[i] = 0 if LPF[i] = 0 and FPOS[i] = max {j | w[i..i+LPF[i] -1] = w[j..j+LPF[i] -1], for 1 ≤ j < i}.
Range Min in Weighted Tree: For any two nodes u and v in the same path of a weighted rooted tree, let min(u, v) be a query that returns a node in the path with minimum weight. The following lemma from [START_REF] Alstrup | Improved Algorithms for Finding Level Ancestors in Dynamic Trees[END_REF] states recent result used in this paper:

Lemma 2. Under a RAM model, a dynamic tree can be maintained in linear space so that a min query and an operation of adding a leaf to the tree are both supported in the worst-case O(1) time.

Minimum Closed Covers

In this section, we present an algorithm that computes Minimum Closed Covers of all prefixes for a given string w of length n. More precisely, we compute array C such that for each position 1

≤ i ≤ n, C[i] stores the size of a minimum closed cover of w[1..i]. If C[i] = h then, by definition, there is a closed cover {[b 1 ..e 1 ], • • • , [b h ..e h ]} that covers w[1..i] such that b 1 = 1, e h = i and h is minimum.
Obviously there might be several closed covers that are minimum but we are interested on being able to retrieve one of them. In order to achieve this goal, array C ℓ is maintained such that C ℓ [i] stores the length of the rightmost closed factor ending at position i which is associated with the rightmost subinterval of a minimum closed cover (of size C[i]) of w [1..i]. A minimum closed cover of w, and indeed of any prefix of w, can be easily computed in a greedy manner from right to left using C ℓ .

Before presenting our algorithm, we will introduce several known results concerning closed strings; for proof and more details please refer to [4]:

Corollary 1. A string w is C-poor if and only if every closed factor of w is a complete return of a single letter.

By definition empty strings and one-letter strings are closed. Corollary 1 suggests an additional class of closed strings namely complete return of a single letter; that is for any letter α, string w = αuα is closed if α has no occurrence in string u. Additionally, Lemma 3 suggests that if the size of a string increases by one (let say, by concatenating a single letter) then the total number of closed factors of the new strings should increase. In this paper, we are interested with the minimum number of closed factors that cover a given string. Our main observation suggests that if the size of string increases by one letter then the minimum size of closed cover cannot increase by more than one.

Observation 1 Let {[b 1 ..e 1 ], • • • , [b k ..e k ]} be a minimum closed cover w[1..i-1] and {[b ′ 1 ..e ′ 1 ], • • • , [b ′ h .. ′ e h ]} is a minimum closed covers of w[1..i1] then h ≤ k+1.
Considering position i, given C[j] for 1 ≤ j < i, while taking C[i -1] into consideration, there are three different possibilities:

1. The size of a minimum closed cover of w [1..i .i] and the length of its rightmost closed subinterval, respectively. That is, if

C ℓ [i] = ℓ then w[i -ℓ + 1..i] is the rightmost closed factor associated with interval [i -ℓ + 1..i]; the rightmost subinterval of a minimum closed cover of w[1..i].
For each position i we will store the length of the border of the rightmost closed factor such that B ℓ [i] = |border(w[i -ℓ + 1..i])|. In this way, array B ℓ will enable us to check in O(1) time whether the rightmost closed factor can be extended to the right by a single letter and stay closed. We will also maintain an array P that keeps for each position i, the nearest position j to the left of i containing letter w[i] such that w[j..i] is closed as it is a complete return of a single letter (Corollary 1). Now we are ready to present our Minimum Closed Covers algorithm. The algorithm initializes C [START_REF] Alstrup | Improved Algorithms for Finding Level Ancestors in Dynamic Trees[END_REF] = 1 and iterates from left to right calculating for each position i the value of C[i] as follows:

C[i] =          C[i -1]. If w[i -C ℓ [i -1] + B ℓ [i -1]] = w[i]. min      C[P [i] -1] + 1, C[i -1] + 1, C[k -1] + 1.

Otherwise.

At each iteration i, the algorithms first checks whether the rightmost closed factor can be extended to the right by letter w[i] and stays closed. This can be easily achieved by comparing positions w

[i -C ℓ [i -1] + B ℓ [i -1]] and w[i].
If the two positions are equal then the size of a minimum closed cover does not increase, as we are still able to cover w [1..i] with a minimum cover of size C[i-1], and since C[i-1] is minimum, then C[i] is also minimum. If the rightmost closed factor cannot be extended, then the algorithm checks all possible closed factors of w [1..i], ending at position i, and chooses the one that minimizes the size of a closed cover. Obviously, there are two closed factors of w [1..i] ending at position i that can be easily checked: factor w[i]; a a one-letter closed factor, and factor w[P [i]..i]; a complete return of a single letter. These two factors are not the only ones that need to be checked and now we will turn our attention to explain how all other closed factors can be identified and checked efficiently.

Recall that the Longest Previous Factor gives for each position i in w the length of the longest factor that occurs at i and to the left of i in w. We show that the position of the longest previous factor can be calculated at no extra cost. Here, we update the definition of LP F as follows: LP F [1] = (0, 0) and

LP F [i] = (ℓ, j) such that ℓ = max{k | w[i..i + k -1] = w[j..j + k -1], 1 ≤ j < i}.
Clearly, if LP F [i] = (ℓ, j), then w[j..i + ℓ -1] is a closed factor with a border (of length ℓ) starting at positions j and i. For the purpose of our algorithm, we want to calculate for each position the maximum closed factor ending at a certain position (not starting). By maximum, we mean non left-expendable. To do so, the longest previous factor array is computed for string

← ---- w[1..n] = w[n]w[n -1]..

w[1]; we will call the new array

← ---LP F . By doing so, we calculate for each position the length of the maximum closed factor ending at each position n -i + 1 and to the right of n -i + 1 in w. Thus, if ← ---LP F [i] = (ℓ, j), then there is a closed factor in w with a left border (of length ℓ), ending at position n -i + 1, and a right border ending at position n -j + 1. The relation between closed factors and array ← ---LP F has been highlighted in [START_REF] Badkobeh | Closed Factorization. To appear[END_REF]. For i = 11, ← ---LP F [START_REF] Glen | Palindromic Richness[END_REF] = [START_REF] Breslauer | An On-Line String Superprimitivity Test[END_REF][START_REF] Bucci | Rich and Periodic-Like Words[END_REF] implies that there is a closed factor baaaa baaaa in ←w , that corresponds to a closed factor (aaaab aaaab) in w, with a left border ending at position 9 = 19 -11 + 1, and a right border ending at position 14 = 19 -6 + 1. This is a maximum closed factor as it cannot be extended to the left.

Note that position 7 appears three times in ← ---LP F , which implies that there are three different closed factors with a right border ending at position 13 = 19-7+1 in w. These three closed factors are different and each is associated with distinct maximum closed factor with respect to the end positions of the left borders:

left border ending at position 12 = 19 -8 + 1 and of length = 3: aaaa, left border ending at position 8 = 19 -12 + 1 and of length = 4: aaaabaaaa, left border ending at position 7 = 19-13+1 and of length = 7: aabaaaaabaaaa.

From the above example, one should be able to recognize that the number of distinct maximum closed factors ending at a certain position i in w is not always equal to 1. However, the total number of distinct maximum closed factors over all positions i in w is at most n; the length of w. Now, we can go back and finalize the Minimum Closed Covers algorithm. Recall that in order to calculate C[i], the algorithm checks whether the rightmost factor can be extending with letter w[i] and remain closed. If this not possible, the algorithm finds the rightmost closed factor ending at position i that minimizes

C[i]. Lemma 4. A factor w[k..i] is a closed factor of w ending at position i if and only if k = i or k = P [i] or k ∈ ∪ [j i -ℓ ji + 1..j i -ℓ ji+1 ],
where {(j 1 , ℓ j1 ), (j 2 , ℓ j2 ), • • • , (j h , ℓ j h )} is the ordered set of all maximal closed factors of w ending at position i, and with left borders ending at positions j i and of length ℓ ji (j h+1 = 0).

Proof. If {(j 1 , ℓ j1 ), (j 2 , ℓ j2 ), • • • , (j h , ℓ j h )} is the set of closed factors ending at position i in ascending order, i.e. j 1 < j 2 < ... < j h . Then, it should be clear that

ℓ j1 > ℓ j2 > • • • > ℓ j h .
Consider for example positions j 1 < j 2 , both w[j 1 -ℓ j1 + 1..i] and w[j 2ℓ j2 + 1..i] are closed factors of w ending at position i with borders of length ℓ j1 and ℓ j2 , respectively. By definition, w[i -ℓ j1 + 1i] and w[i -ℓ j2 + 1i] are the longest suffixes associated with these closed factors. Each suffix appears in the associated factor twice as a suffix and a prefix. If

ℓ j1 < ℓ j2 , then w[i -ℓ j1 + 1i] is a suffix of w[i -ℓ j2 + 1i] and should have internal occurrence in w[j 1 -ℓ j1 + 1..i], a contradiction.
Each closed factor w[j l -ℓ j l + 1..i] is maximum i.e. it cannot be extended to the left by any letter. This is due to the method of construction from LP F . However, in order to calculate all possible positions in w that could start a closed factor ending at position i, non-maximal closed factors need to be considered. This can be done by considering all suffixes of w[j l -ℓ j l +1..i] starting at positions j l -ℓ j l + 1..j l -ℓ j l+1 . Note that any smaller suffix is not closed due to an internal occurrence.

⊓ ⊔

Each position k defined by Lemma 4 is a candidate for a start position of a closed factor ending at position i. The closed factor that minimizes C[i] is the one that starts at position k such that C[k -1] is smallest. Proof. Although for each position i, the number of candidate positions at which a rightmost closed factor (ending at position i) is not constant, the number of intervals that need to be checked is bounded by n. The sum of these intervals over all possible i is linear. According to Lemma 2, calculating for each interval, the position k, with the minimum C[k], can be done in O( 1

[i] 1 1 2 2 1 2 2 2 1 1 1 1 1 2 3 4 2 2 2 C ℓ [i]
1 2 1 3 5 1 2 3 9 10 11 12 13 9 1 1 4 5 6

Consider position i = 14, given that aabaaaaabaaaa is the rightmost closed factor of a minimum closed cover of w [1..13]. Firstly, the Minimum Closed Covers algorithm checks whether this closed factor is extendable to the right by comparing positions w [START_REF] Iliopoulos | An O(n log n) Algorithm for Computing All Maximal Quasiperiodicities in Strings[END_REF] and w [START_REF] Crochemore | Computing Longest Previous Factor in Linear Time and Applications[END_REF]. Since w[14] ̸ = w [START_REF] Crochemore | Computing Longest Previous Factor in Linear Time and Applications[END_REF], the closed factor cannot be extended to the right and the algorithm proceeds to compute the optimal value for C [START_REF] Iliopoulos | An O(n log n) Algorithm for Computing All Maximal Quasiperiodicities in Strings[END_REF] In Example1, we show that there is one maximum closed factor ending at position 14 that starts at position 5 and with a border of length 5. Although, all five suffixes (starting at positions ∈ [5..9]) of this maximum closed factor are also closed and need to be considered, computing position k ∈ [5..9] with the minimum C[i -1] can be done constant time using a single min query (k = 6). Therefore, C [START_REF] Iliopoulos | An O(n log n) Algorithm for Computing All Maximal Quasiperiodicities in Strings[END_REF] = 2 is the size of a minimum closed cover of w [1..14]; note that there are two minimum closed covers: {[1..13], [14..14]} and {[1..5], [6..14]}, both of size 2.

The size of a minimum closed cover of w calculated by our proposed algorithm is C [START_REF] Li | Computing the Cover Array in Linear Time[END_REF] = 2. It consists of two closed factors that can be retrieved using array C ℓ . In this case, { [1..13][14..19]} is a minimum closed cover with two closed factors: aabaaaaabaaaa and bcdbcd.

Conclusion

We have considered The Minimum Closed Covers problem and proposed an online algorithm to calculate such cover in linear time. Our work is an extension to various string cover related problems. Recently, an algorithm to compute the minimum palindromic covers was proposed. Although there are relatively strong relations between palindromic string and closed string, our algorithm is significantly different. Various types of covers are still to be investigated mainly for its theocratical interest. In particular, we are interested in the calculation of the minimum Abelian covers of a string.

Lemma 3 .

 3 For any strings u and v, one has |CC(u)|+|CC(v)| ≤ |CC(uv)|+1, where |CC(w)| is the size of a set of closed factors of w.

Example 1 .For i = 13 ,

 113 Let w = aabaaaaabaaaabcdbcd be a given string of length 19. a a a a a b a a a a b c d b c d LP F [i](ℓ, j) 0 LP F [13] = (2, 8) implies that there is a closed factor abaaaab, with a left border starting at position 8, and a right border starting at position 13 in w. The length of the border of this closed factor is 2. The inverse of string w, ←w = dcbdcbaaaabaaaaabaa. d c b a a a a b a a a a a b a a ← ---LP F [i](ℓ, j)

Theorem 2 .

 2 Given string w of length n, the Minimum Closed Covers algorithm computes C[i] for 1 ≤ i ≤ n in O(n)-time in an online manner.

Example 2 .

 2 ) time. ⊓ ⊔ For the same string w = aabaaaaabaaaabcdbcd. position i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 w[i] a a b a a a a a b a a a a b c d b c d C

  [START_REF] Iliopoulos | An O(n log n) Algorithm for Computing All Maximal Quasiperiodicities in Strings[END_REF] -1] + 1 = C[START_REF] Crochemore | Computing Longest Previous Factor in Linear Time and Applications[END_REF] + 1 = 2 + 1 = 3, C[13] + 1 = 1 + 1 = 2, min{C[k -1] + 1; for k ∈ [5..9]} = C[5] + 1 = 1 + 1 = 2.

  ] increases by one. In this case, the one-letter closed factor w[i] becomes the rightmost closed factor of a minimum closed cover. 2. The size of a minimum closed cover of w[1..i] stays the same. This may be achieved if the rightmost closed factor can be extended to the right by letter w[i] and stays closed. If w[b..i-1] is the rightmost closed factor of a minimum

closed cover of w[1..i -1] and w[b..i] is closed then w[b..i] is the rightmost closed factor of a minimum closed cover of w[1..i]. 3. The size of a minimum closed cover of w[1..i] decreases. This can only be achieved if there exists a position k such that w[k..i] is a closed factor of w[1..i] and C[k -1] < C[i -1]. Here C[i] = C[k -1] + 1 and w[k..i] will be the rightmost closed factor of a minimum closed cover of w[1..i]. Recall that C[i] and C ℓ [i] are the size of a minimum closed cover of w[1.


Xenophon Evangelopoulos
email: evangelopo@ceid.upatras.gr

Christos Makris
email: makri@ceid.upatras.gr

Yannis Plegas
email: plegas@ceid.upatras.gr

Reciprocal Rank using Web Page Popularity

Keywords: Information Retrieval, Evaluation, Metrics, User Behavior, User Model

In recent years, predicting user behavior has drawn much attention in the fields of information retrieval. To that extend, many models and even more evaluation metrics have been proposed, aiming at the accurate evaluation of the information retrieval process. Most of the proposed metrics, including the well-known nDCG and ERR, rely on the assumption that the probability (R) a user finds a document relevant, depends only on its relevance grade. In this paper, we employ the assumption that this probability is a function of a combination of two factors; its relevance grade and its popularity grade. Popularity, as we define it from daily page views, can be considered as users' vote for a document, and by combining this factor in the probability R we can capture user behavior more accurately. We present a new evaluation metric called Reciprocal Rank using Webpage Popularity (RRP) which takes into account not only the document's relevance judgment, but also its popularity, and as a result correlates better with click metrics than the other evaluation metrics do.

Introduction

Designing evaluation metrics consists an important direction of information retrieval, which has gained tremendous attention over the last few years due to the expeditious evolution of information retrieval systems. Some of the best known evaluation metrics that have been developed over the years are Mean Average Precision (MAP), Precision at k (P@k), normalized Discounted Cumulative Gain (nDCG) [START_REF] Järvelin | Cumulated gain-based evaluation of ir techniques[END_REF], Expected Reciprocal Rank (ERR) [START_REF] Chapelle | Expected reciprocal rank for graded relevance[END_REF] etc. A good evaluation metric should reflect the rate of relevance of the retrieved results. Furthermore, a proper user model which reflects users' interaction with the retrieval system is of utmost importance.

There are two different types of user behavior models; the position models and the cascade models. The first [START_REF] Craswell | An experimental comparison of click position-bias models[END_REF] assume that a click depends on both relevance and examination. Moreover, the probability of examination depends only on the position. As a result, position models consider each result in a page as independent from other results and thus fail to capture interaction among them in examination probability.

On the other side, cascade models rely on the assumption that users examine all the results sequentially from top to bottom and stop as soon as a relevant document is found and clicked. The examination probability in this case depends on the rank of the document and the relevance of all the previous documents. It is showed by Chapelle and Zhang [START_REF] Chapelle | A dynamic bayesian network click model for web search ranking[END_REF] that cascade models can predict click-through rates mode accurately than position models.

In this paper we induce a novel evaluation metric which incorporates a new concept called web page popularity. Our metric is a cascade-based evaluation metric, which means that we assume the user scans all results from top to bottom and stops when she/he finds a relevant document and clicks on it. The difference of our proposed metric lies on the definition of the probability R, that a user finds a document relevant. Unlike previous editorial metrics we assume that the probability a user clicks on a document depends on two factors; not only on its relevance grade, but also on its popularity grade. For each document D i , we have two values, a relevance grade as it is proposed by experts and popularity grade as it is given by web traffic statistics. We then incorporate these two values in the probability R and evaluate how well our proposed metric captures user behavior by comparing its performance with the performance of click-metrics.

The remainder of this paper is organized as follows. First Section 2 presents some recent related work on the field. Section 3 then describes the cascade model on which our new metric is based. Section 4 explains in detail the notion of web page popularity. Our metric is presented in Section 5 and Section 6 provides evidence of our metric's well-behavior. Finally we conclude the paper in Section 7.

Related Work

Evaluating the quality of information retrieval systems constitutes an important task in the research area of information retrieval. A great number of scientific papers have been published trying to best model, how well the search system satisfies users' search needs. As a result, a broad range of evaluation metrics which quantify system performance have been proposed, including Discounted Cumulative Gain (DCG or nDCG as it is mostly used) by Järverlin and Kekäläinen [START_REF] Järvelin | Cumulated gain-based evaluation of ir techniques[END_REF], Average Precision (AP) and Expected Reciprocal Rank (ERR) by Chapelle et al. [START_REF] Chapelle | Expected reciprocal rank for graded relevance[END_REF] just to name a few. The latter belongs to a group of IR metrics which have an underlying cascade user model, which is the user model our proposed evaluation metric also uses.

The basic concept an information retrieval measures, is the concept of relevance. Most evaluation metrics use a set of relevance judgments for a set of documents as firstly induced by TREC evaluations. Relevance judgments are collected by human experts who are obliged to asses for a document's relevance to a given query and thus capture the notion of user relevance [START_REF] Cleverdon | The significance of the cranfield tests on index languages[END_REF] [START_REF] Sanderson | Information retrieval system evaluation: Effort, sensitivity, and reliability[END_REF]. Instead, we argue that an expert's opinion about a document's relevance is not sufficient enough to account for all users' opinion. Thus, we introduce a second relevance indicator which accounts for a huge amount of real users' opinion. We call this concept web page popularity and is derived from the daily page views a web page gets.

A resultant issue which arises when evaluating information retrieval systems is the test collection incompleteness problem, where a significant amount of relevance judgments is missing from the test collection. Buckley and Voorhees [START_REF] Buckley | Retrieval evaluation with incomplete information[END_REF], Sakai [START_REF] Sakai | Alternatives to bpref[END_REF] and Chucklin et al [START_REF] Chuklin | Click model-based information retrieval metrics[END_REF] battle this problem either by introducing a new metrics or by alternative solutions. We will also contemplate this problem using the concept of web page popularity.

Cascade User Model

One of the first things one should take into consideration when developing an evaluation metric is how well it's user model reflects users' satisfaction [START_REF] Scott | How well does result relevance predict session satisfaction[END_REF]. There exist two main categories of user models: position models and cascade models. Position models [START_REF] Craswell | An experimental comparison of click position-bias models[END_REF] [13], as their name implies, are trying to express the examination probability as a function of the position. Some of the metrics relying on the position model include the DCG metric and the RBP [START_REF] Moffat | Rank-biased precision for measurement of retrieval effectiveness[END_REF] metric. However, as showed by Chapelle et al. [START_REF] Chapelle | Expected reciprocal rank for graded relevance[END_REF] position models appear to face some serious drawbacks due to the fact that they assume that the probability of examination depends only on position.

Our proposed metric is based on the cascade model [START_REF] Chapelle | A dynamic bayesian network click model for web search ranking[END_REF], assuming a linear traversal through the ranking, and that the rest of the results below a clicked document are not examined by the user. Let R i be the probability of examination of the i -th document. As soon as the user clicks on a result and is satisfied with it, she/he terminates the search and results below are not examined at all, no matter of what their position is.

As showed by Craswell et al. [START_REF] Craswell | An experimental comparison of click position-bias models[END_REF] R i represents the attractiveness of a result. More specifically it measures the probability of a click on a result which can be interpreted as the relevance of the snippet. We expand this by inducing a novel factor contributing in the measurement of examination probability. This factor is called web page popularity. A more detailed explanation and definition of web page popularity follows in section 4. In order to develop an evaluation metric which captures user behavior well, one should not only rely on experts' judgments, but also on other factors which capture user behavior. Popularity, as we define it from daily page views, can be considered as users' vote for a document and as result a value which expresses user's behavior. Here, we make the assumption that at each rank, the document's probability relies not only on its relevance, but also on its popularity. This means that when a user examines all documents from top to bottom, at each rank r she/he is expected to click on a result after examining its snippet S r , which finds relevant and its url link L r , which finds popular. As a result we suggest that probability of clicks is highly correlated both with the relevance of the document and its popularity.

R r = P (C r |S r , L r )
The R i values as we will show in the next section can be set as a function of two factors. The relevance grade of document i and the popularity of the url of document i. For a given set of R i , the probability of click on the i -th document can thus be expressed as:

P (C r = 1) = r-1 i=1 (1 -R i )R r .

Web Page Popularity

In the previous section we presented the cascade user model, where we presented a novel concept named as popularity of a web page. But how can one define the popularity of a link or better of a page? Cho et al. [START_REF] Cho | Page quality: In search of an unbiased web ranking[END_REF] in their study define popularity V(p,∆t) of a page p as the number of "visits" or "page views" the page gets within a specific time interval ∆t. Here, we also use this notation but abstract it generally as Web Page Popularity.

Definition 1 (Web Page Popularity) We define the popularity P(p,∆t) of a web page p as the number of page views (pv ) that page gets within a specific time interval ∆t.

Following from the above definition we construct a popularity grade in accordance with the relevance grade, so that the popularity of each link can be measured and compared properly. Particularly, given a number of page views pv for a link u, we define its popularity grade as follows:

p u = ln pv u 5 (1)
Equation ( 1) was developed based on traffic statistics about every web page. More specifically, pageview values pv ranged from 0 (that is no page views at all) to 500.000.000 (Google's page views) per day. In order to incorporate these large numbers in a metric we decided to get the natural logarithm from each pv value so that we don't lose the amount of information for each website. Moreover we mapped each natural logarithm to a 5-scale ranging from 0 to 4 in order to create a grade-scale similar to that of the relevance grades.

According to equation (1) each website received a 5-scaled grade (unknown, well-known, popular, very popular and famous) according to its daily traffic statistics. Table 1 shows the popularity grade of some websites according to their daily page views.

Proposed Metric

In this section we will introduce our new proposed evaluation metric. This novel metric is based on the cascade model described in section 3. As stated before our proposed metric is described by two factors of relevance. The relevance grade of the document and the popularity grade of the document. Let g i be the relevance grade and p i the popularity grade of the i -th document. Then the relevance probability can be equally defined by g i and p i .

R i = R(g i , p i ).
Here R i denotes a different value equally defined by two factors and R consists a mapping function from relevance and popularity grades to probability of relevance. There are many different ways to define R, but here we select it in accordance with the gain function of ERR used in [START_REF] Chapelle | Expected reciprocal rank for graded relevance[END_REF] R(r) = 2 r -1 2 rmax , where r = g + p 2 , r ∈ {0, ..., r max }.

This means that the probability of relevance can be defined equally by two factors; its relevance grade and its popularity grade. As we will prove in the next section this is a well-balanced way to define relevance due to the equal contribution of each factor. Thus, when a document is fairly-relevant (g = 1), but is very popular (p = 4), the probability that a user will click on that result is much higher than if the document was non-popular.

In order to make things more clear, consider the following scenario: a user examines all the results after posing a query in a search machine. She/he discovers two results (regardless of their position) which he considers as very relevant. If the first result is a far more popular web page than the other, then she/he will not examine the latter. The next step is to define a utility function for our metric. A utility function ϕ takes as argument the position of each document and should satisfy that at the first position it will take the maximum value 1 and as position increases ϕ converges to 0. In other words, ϕ(1) = 1 and ϕ(r) → 0 as r goes to +∞. In accordance with ERR metric, we select the special case ϕ(r) = 1/r. As a result, our metric can be defined as follows:

RRP := n r=1 1 r r-1 i=1 (1 -R i )R r .
Compared to other cascade-based metrics, RRP relies not only on the documents' relevance judgment but also on the popularity grade which consists a real-time "judgment" of users. Thus, our metric captures user behavior more successfully.

Evaluation

It is known that the evaluation of a new retrieval metric is not an easy task due to the fact that there is no ground truth to compare with. However, it has been shown [START_REF] Radlinski | How does clickthrough data reflect retrieval quality[END_REF] that the quality of a retrieval system can be well estimated by click-trough data. A common technique though is comparison with click metrics. That way one can see how well does a metric approximates user behavior and as a result captures user satisfaction. In this section, we try to evaluate our novel metric by computing correlations between click metrics and editorial metrics including our proposed metric.

Data Collection

In order to collect click through data we developed an information retrieval system based on Indri Search Engine (Lemur Project [START_REF]The lemur project[END_REF]) using TREC Web Track data. We then asked users from Information Retrieval Class of the Computer Engineering and Informatics Department of Patras to perform an informational search on a number of predefined queries by TREC Web Tracks. Particularly, we used 200 queries from TREC Web Tracks 2009 to 2012 and their document results at depth 20 as returned by Indri. Each user was asked to perform search on 200 predefined queries according to a special informational need. Click-through data from each interaction with the system were collected in log files.

We intersected these click through data with relevance judgments as they were defined by TREC Web Tracks on a five-grade scale (0 → 4). We also intersected click through data with popularity grades which were computed from daily page views as shown in section 4. Finally, each document was graded according to a five-grade scale from 0 to 4. The final dataset consisted of relevance and popularity grades for each resultdocument of each query. For some queries of TREC Web Tracks though, all of their results-documents were graded with zero relevance judgments or with zero popularity grades. We removed these queries in order to simulate a search process which reflects reality, ending with click-through data for 167 different queries.

Correlation with click metrics

Using the dataset described in previous subsection we computed the pearson correlation between a set of click metrics and editorial metrics. Particularly, the editorial metrics used were:

-nDCG: Normalized Discounted Cumulative Gain.

-AP: Average Precision, where grades perfect, excellent and good are mapped to relevant and the rest to non-relevant. -ERR: Expected Reciprocal Rank.

-RRP: Our proposed metric.

The click metrics used were:

-PLC Precision an Lowest Rank as defined by [START_REF] Chapelle | Expected reciprocal rank for graded relevance[END_REF].

-Max, Mean and Min RR Maximum, Mean and Minimum Reciprocal Ranks of the clicks. -UCTR Binary variable indicating whether there was a click or not in a session.

We did not include the Search Success (SS) metric induced by Chapelle et al. [START_REF] Chapelle | Expected reciprocal rank for graded relevance[END_REF], as it uses relevances not only clicks. We also confirmed the findings of [START_REF] Chapelle | Expected reciprocal rank for graded relevance[END_REF], that QCTR has negative or close to zero correlation with all the editorial metrics and skipped it as well. Table 2 shows correlations between all the above mentioned metrics.

From table 2 we conclude that our proposed metric shows higher scores in correlation with click metrics than other editorial metrics. Particularly, RRP outperforms position-based metrics such as nDCG and Average Precision; additionally RRP correlates better with click metrics even than the cascade-based metric ERR.

As click metrics are concerned, we observe that reciprocal ranks (max,min and mean) along with precision at lowest rank seem to correlate better with ERR and our proposed metric RRP. This holds due to the fact that they both use as utility function the reciprocal rank 1 k . Precision at lowest rank uses reciprocal rank of the lowest position and as a result shows higher correlation with ERR and RRP too. We can see though, that in most cases our proposed metric appears to score significantly better that other editorial metrics except for UCTR. This can be explained as UCTR does not account for clicks (rather than their absence) and therefore lacks the source of correlation with click metrics. Moreover, overall results of UCTR enhance our assertion as it seems to correlate with editorial metrics much lower (around zero) than other click metrics do.

Performance on incomplete collection

Search engines are using an enormous amount of data, which is constantly changing. Thus it is difficult to maintain complete relevance judgments even for a small proportion of the web corpus. As a result there exists a set of queries which partly or completely lacks relevance judgments.

There has been an effort to confront this problem in various ways over the years. Buckley and Voorhees [START_REF] Buckley | Retrieval evaluation with incomplete information[END_REF] in their work propose a robust preference-based measure called bpref which measures the effectiveness of a system on the basis of judged documents only. On the other side, Sakai [START_REF] Sakai | Alternatives to bpref[END_REF] proposes an alternative solution which does not need a new metric. Our proposed metric which accommodates two factors of relevance can battle the missing relevance judgment issue in a complete different way. In situations when there is a document with missing a relevance judgment, we employ the second factor, the popularity grade which accounts for user preference. In order to enhance our assertion we conducted experiments on how correlation between click metrics and our proposed metric was affected when some queries of our dataset lacked relevance grades. Particularly, from the initial set of 167 queries, we created 2 sets where in the first set 41 from 167 queries lacked relevance grades and in the second set 83 from 167 queries lacked relevance grades. We then computed the correlation between click and editorial metrics of each partly "unjudged" dataset. Figures 1, 2 and 3 show the correlation diagram for the initial dataset and the two partly "unjudged" datasets. In figure 2 where a small set of the dataset is "unjudged", our metric retains the highest scores in correlation with click metrics. As we increase the amount of "unjudged" queries (half of the dataset contains no relevance grades), we observe deterioration of our metric's performance. We can easily conclude that in cases when the amount of relevance judgments absence is not extensive, our proposed metric can still express user behavior better than the other editorial metrics.

Conclusions and Future Work

In this paper, we proposed a novel information retrieval metric called reciprocal rank with webpage popularity (RRP). This cascade model-based metric incorporates an additional relevance factor while computing the probability that a user finds a document relevant. The second relevance factor we incorporate is called popularity grade and is calculated by the number of daily page views a document gets. The number of daily page views of a web page, can be viewed as a users' vote for this web page and thus, by combining this factor with experts' relevance judgments, our evaluation metric captures user behavior better. In order to verify our thoughts, we conducted experiments on a TREC dataset with click data collected by students' search sessions. The results showed that our evaluation metric correlates better with click-metrics and as a result expresses user behavior better. Furthermore, we showed that in situations where a significant amount of relevance judgments is unavailable, our metric still correlates better with click-metrics using only popularity grades.

Our plans for the future include the development of a novel user model which will be able to implement the notion of popularity and model accurately its reflect on user behavior. Moreover, new experiments on a dataset with greater number of queries and sessions is another thought in order to enhance the user model's findings.

Fig. 1 :Fig. 2 :

 12 Fig. 1: Correlation between Editorial and Click metrics when no queries are "unjudged"

Table 1 :

 1 Popularity grade for four sample websites

	WebSite	Daily Page views	Popularity Grade
	http://google.com	584.640.000	4
	http://wikipedia.com	30.451.680	3
	http://ceid.upatras.gr	11.228	1
	http://sample-site.wordpress.com	11	0

Table 2 :

 2 Pearson Correlation between editorial and click metrics

		PLC MeanRR MinRR MaxRR UCTR
	nDCG 0.498 0.497	0.503 0.445 -0.024
	AP	0.402 0.417	0.395 0.396 -0.004
	ERR 0.528 0.512	0.517 0.459 0.064
	RRP 0.559 0.554	0.588 0.472 0.041

Acknowledgments

This research has been co-financed by the European Union (European Social Fund -ESF) and Greek national funds through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework (NSRF) -Research Funding Program: Thales. Investing in knowledge society through the European Social Fund.