Andreas Holzinger
email: a.holzinger@hci4all.at

Manuel Bruschi
email: m.bruschi@hci4all.at

Wolfgang Eder
email: wolfgang.eder@eder.ch

On Interactive Data Visualization of Physiological Low-Cost-Sensor Data with Focus on Mental Stress

Keywords: Data visualization, Knowledge Discovery, EDA, BVP, HRV, Stress, low-cost sensor

Emotions are important mental and physiological states influencing perception and cognition and have been a topic of interest in Human-Computer Interaction (HCI) for some time. Popular examples include stress detection or affective computing. The use of emotional effects for various applications in decision support systems is of increasing interest. Emotional and affective states represent very personal data and could be used for burn-out prevention. In this paper we report on first results and experiences of our EMOMES project, where the goal was to design and develop an end-user centered mobile software for interactive visualization of physiological data. Our solution was a star-plot visualization, which has been tested with data from N=50 managers (aged 25-55) taken during a burn-out prevention seminar. The results demonstrate that the leading psychologist could obtain insight into the data appropriately, thereby providing support in the prevention of stress and burnout syndromes.

Introduction

The value of emotion to the quality and range of everyday human experience is underestimated. It has a huge influence on the domains of cognition, in particular attention, memory, and reasoning [START_REF] Dolan | Emotion, cognition, and behavior[END_REF]. An increasing problem in our western industrialized world is the Burnout Syndrome (BOS), which is a psychological state resulting from prolonged exposure to job stressors [START_REF] Gall | Burn out syndrome among critical care workers[END_REF][START_REF] Weber | Burnout syndrome: a disease of modern societies?[END_REF]. In the past, many methods have been developed for measuring emotions, for a rapid overview refer e.g. to [START_REF] Wickens | An introduction to human factors engineering[END_REF][START_REF] Rubin | Handbook of Usability Testing: Howto Plan, Design, and Conduct Effective Tests[END_REF][START_REF] Cairns | Research methods for human-computer interaction[END_REF][START_REF] Lazar | Research methods in human-computer interaction[END_REF] and for a very short overview see [START_REF] Holzinger | Process Guide for Students for Interdisciplinary Work in Computer Science/Informatics: Instructions Manual-Handbuch für Studierende[END_REF], here a very brief summary: Electrodermal activity (EDA), aka Galvanic skin response (GSR), electro-dermal response (EDR), or skin conductance response (SCR) is basically the measuring of the electrical resistance of the skin and can be used as a sensitive index of the activity of the sympathetic nervous system. Another popular method to assess the psychophysiological activity is Heart-Rate Variability (HRV) (see details in Section 2), which can be derived from Electrocardiographic (ECG) or Blood Volume Pulse Data (BVP). Viewing these Biosignals on mobile devices is a current and increasing trend [START_REF] Breitwieser | iscope-viewing biosignals on mobile devices[END_REF].

Research on stress recognition and classification with physiological signals has reached a good point (for an overview look at [START_REF] Sharma | Objective measures, sensors and computational techniques for stress recognition and classification: A survey[END_REF]. Nonetheless, because people are sensitive to this topic due the popularity about burnout, we must be careful with our affirmations. Today, algorithms are able to reach a high accuracy for modeling stress but we still can not fully trust them, there is always the danger of modeling artifacts. However, stress remains an important aspect of human health that we must learn to deal with. Until recognition and classification patterns become fully reliable, we will continue to retrieve any data available and provide information to the individual expert end users, enabling them to gain knowledge by interactive visualizations -intelligence remains the forte of the human brain [START_REF] Holzinger | On knowledge discovery and interactive intelligent visualization of biomedical data-challenges in human-computer interaction & biomedical informatics[END_REF]. Moreover, while people are often unable to clearly identify their own emotions; it can be iteratively learned.

We recognized that the participants involvement/acceptance of the evaluation process necessitated an clear and easy to understand visualization of the physiological data processing results, in order for them to learn something about their emotions or discuss them with an expert.

Therefore our central goal was to design and develop an interactive information visualization for our signal processing model, which 1) displays most of the important feature evaluations regarding stress, 2) displays the data in a way that it is easy to compare features between relaxing and activating situations; 3) displays the data in a way that can be helpful for a non-expert end user and 4) at least may be provided with average computer resources within a tolerable time.

In short, the visualization must provide a variety of information about individual physiological activities with the focus on stress, so that both the nonexpert and the expert can analyze and discuss the data and, most of all, to obtain insight and new knowledge from it. All the data collection, evaluation and visualization should be done by one user interface. To ensure that the solution will be affordable for many people, we have used a low-cost-sensor, which is described in Section 3.

Background -Psychophysiological Assessment

Physiological events are involuntary activities for which our Autonomic Nervous System (ANS) is responsible. Two main nervous systems are relevant for stress, the Sympathetic and Parasympathetic Nervous Systems (SNS and PNS respectively). Stressful situations cause dynamic changes in the ANS whereby the activity of the SNS increases and of the PNS decreases. In short, the SNS dominates during restless activities and the PNS during resting ones. These two systems are important for our research, because they regulate the different physiological signals, such as heart rate variability (HRV), galvanic skin response (GSR), brain activity (EEG), blood pressure (BP) etc. Note that these systems are influenced by many different factors; two of them are eustress and distress. Eustress characterizes positive states and distress negative states, therefore, not all monitored stress should be perceived as bad stress. [START_REF] Boucsein | Electrodermal activity[END_REF] As Sharma and Gedeon showed in [START_REF] Sharma | Objective measures, sensors and computational techniques for stress recognition and classification: A survey[END_REF]-(Table 5) HRV and GSR are two good parameters for detecting stress. In our work we used GSR and BVP records from a low-cost sensor. The signal of the BVP can be used to compute the HRV and some other features explained in Section 1.

Electrodermal activity (EDA)

Electrodermal phenomena and the cardiac response are the most frequently assessed indices for the highly complex autonomic nervous system (ANS) activation in psychophysiology [START_REF] Boucsein | Electrodermal Activity[END_REF][START_REF] Dawson | The electrodermal system[END_REF]. The ease of obtaining a distinct electrodermal response (EDR) with inexpensive methods, the non-intrusiveness, and lenient field conditions are the major reasons for its popularity. Electrodermal recordings can use either external current (AC or DC) or the body's own electric current, the first are called exosomatic and second endosomatic. When an external current is applied to biological tissues such as skin, they act similar to electrical networks built of resistors and capacitors [START_REF] Boucsein | Electrodermal Activity[END_REF].

The term electrodermal activity (EDA) stands for all electrical phenomena of the skin, and was first introduced by Johnson and Lubin [START_REF] Johnson | Spontaneous electrodermal activity during waking and sleeping[END_REF]. But there are also other frequently used terms, such as like Galvanic Skin Response (GSR). This electrical phenomena also includes all active and passive electrical properties which correlate to the skin and its extremities. The EDA has a central importance in biosignal acquisition and this concerns its psychological significance. Since the first research activities this response system has been closely linked with the psychological concepts of emotion, arousal and attention [START_REF] Dawson | The electrodermal system[END_REF]. Basically it measures the hydration in the epidermis and dermis of the skin, which increases or decreases with the activation or inhibition of the sweat glands that are controlled by the sympathetic chain of the ANS.

Typically, this is recorded using two sensors placed at the surface of the hand or feet, since these are the areas of the body with higher seat gland density. In most cases the ring and middle finger are chosen and the most common unit used is µS.

The signal is a good indicator for stress, so that it helps to differentiate between conflict and non-conflict situations, but it is also a good indicator for dynamic activity. Usually a rapid rise of skin conductivity reflects a simple stress stimulus.

Cardiac activity

The main purpose of our cardiac activity is to maintain our organs activity by providing them with blood, , which is pumped around the body by the heart.

When we are under stress, the heart rate is increased by the SNS and after the stress has passed the PNS decreases it. . It is therefore obvious that we can evaluate stress by measuring the rate of cardiac activity. [START_REF] Camm | Heart rate variability: standards of measurement, physiological interpretation and clinical use. task force of the european society of cardiology and the north american society of pacing and electrophysiology[END_REF] Regarding stress, as in [START_REF] Devereux | Left ventricular wall stresses and wall stress-mass-heart rate products in hypertensive patients with electrocardiographic left ventricular hypertrophy: The life study[END_REF], acute stress causes the heart to contract with high force and increased frequency. It is also known that with more chronic stress, the mass of the heart is increased. However, the baseline cardiac activity depends on the fitness of an individual and his activity.

There are several methods of measuring the cardiac activity, one used in our work is blood volume pulse (BVP). Photoplethysmography (PPG) is a noninvasive monitoring technique that can be used to track changes in the cardiac system. A reflective finger PPG sensor converts the fluctuation in the blood volume within a region of the index finger into a continuous waveform known as the Blood Volume Pulse (BVP). Traditionally, the BVP period was used to determine the heart rate. Current research however, shows that the BVP is capable of reflecting more than just the heart rate. [START_REF] Barreto | Adaptive lms delay measurement in dual blood volume pulse signals for non-invasive monitoring [photoplethysmography[END_REF] With the BVP signal, we are able to compute the RR-Intervals (the time between two following heart beats) [START_REF] Silva | Study and evaluation of palmar blood volume pulse for heart rate monitoring in a multimodal framework[END_REF] and therefore the Heart Rate Variability (HRV). More information is provided in Section 4.

Experimental setup

Fifty healthy managers between the ages of 25 -55 were recruited during a seminar and participated in our tests. Due to the pressure of time caused by testing this many participants during a seminar we had to design an experimental setup with a maximum time window of ten minutes. Therefore, the setup and introduction had to be fast and easy but without putting the participants under stress. Since we measured EDA and BVP, other requirements to our design arose. In order to have truthful signals, we had to ensure that there were no distracting or exciting elements in the room and also the temperature had to be kept at a pleasant level. In the past we experienced, some participants becoming nervous only because of a little blinking led on the notebook or the integrated webcam and sometimes the room temperature distorted our measurements.

As showed in [START_REF] Sun | Activityaware mental stress detection using physiological sensors[END_REF] electrodermal and cardiac activity are both influenced by the physical activity of the participant. Both are strongly affected by anxiety and exercise [START_REF] Wilhelm | Distinguishing emotional from physical activation in ambulatory psychophysiological monitoring[END_REF] and in order to differentiate mental stress from other elicitations the activity also has to be considered. There are several solutions for this problem: firstly to add an accelerometer to the design, secondly to differentiate stress through feature extraction and preferably by reducing the physical activity as much as possible.

Another challenge we had set ourselves was to use low-cost sensors. Since the main purpose of our measurement is not to make a clinical analysis of the participants, but to visualize important information about their inner processes for discussion and learning, it is possible to keep the costs low.

Keeping all this in mind, we designed a hardware/software methodology that satisfies all these requirements. At the time we designed the system according to the requirements, we chose the IOM Device from Wild Divine [22] for the acquisition of physiological signals.

The device has been connected to a notebook on which we run our software. This shows a video file, logs the raw data from the sensor and write it to a file. With a video consisting of three parts, we were able to reduce the physical activity to a minimum because the participants were only asked only to observe and move as little as possible. The first part showed a slowly moving picture of a sky so that the subject could relax, after a while a calm voice announced the second part and mentioned that it will be stressful, the second part showed some random stressful pictures and colors with noisy sounds, after 15 seconds the voice soothed the participants and the third part with a slowly moving grass video, followed. During all three parts, relaxing music played in the background.

The chronological order of the test session was as following: During the first part (Introduction and Setup -2 min.), the participants were made familiar with the system and the tasks. We also gave them some information about the three parts shown in the video. Then we asked them to sit comfortably, keep their hands still and watch the video. To avoid measurement falsification we left the room and reentered after the end of the video. This second part (Videotest) lasted 5 min. and the third and last part was the feedback part (3 min.).

Feature extraction

In accordance with to many research reports about this topic [START_REF] Sun | Activityaware mental stress detection using physiological sensors[END_REF][START_REF] Zhai | Stress detection in computer users based on digital signal processing of noninvasive physiological variables[END_REF][START_REF] Canento | Applicability of multi-modal electrophysiological data acquisition and processing to emotion recognition[END_REF], we chose to extract from our signals the features shown in figure 1. With a BVP signal, it is possible to calculate the RR-Intervals and from that we can compute the other features such as:

-Mean RR-Interval and mean HR: Each of them varies under stress and therefore reflects sympathetic or parasympathetic activities. Mean RR is significantly lower during a mental task than in the control condition. [START_REF] Taelman | Influence of mental stress on heart rate and heart rate variability[END_REF] A higher RR-Interval means a lower HR and vice versa. A significant change in the RR-Interval during stressful situations reflects a high HRV and therefore how well individuals are able to adapt to changes.

[26] -Power Spectrum Analysis: As in [START_REF] Lauer | Autonomic function and prognosis[END_REF], the high frequency (HF) is thought to reflect parasympathetic tone, whereas the very-low-frequency (VLF) and low-frequency (LF) are thought to reflect a mixture of parasympathetic and sympathetic tone. Because VLF has been found to distort stress detection [START_REF] Camm | Heart rate variability: standards of measurement, physiological interpretation and clinical use. task force of the european society of cardiology and the north american society of pacing and electrophysiology[END_REF], we left this out. With LF and HF we can also compute the energy ratio (total LF over total HF), which increases if stress levels increase.

[28] -pNN50 and RMSSD: Both are time-domain related features that reflect parasympathetic activity [START_REF] Buchheit | Noninvasive assessment of cardiac parasympathetic function: postexercise heart rate recovery or heart rate variability?[END_REF][START_REF] Zulfiqar | Relation of high heart rate variability to healthy longevity[END_REF]. Since pNN50 is significantly lower with a mental task than in a control condition, it reflects mental stress. [START_REF] Taelman | Influence of mental stress on heart rate and heart rate variability[END_REF] GSR is directly influenced by the ANS and therefore it is overall a good indicator for stress. Already, minimal calculations, such as mean and sum are strong features. The detection of the skin responses (SCR), in order to compute the other three features shown in figure 1-(under SCR), is more complex but provides us with further indicators of stress. [START_REF] Boucsein | Electrodermal activity[END_REF][START_REF] Healey | Detecting stress during real-world driving tasks using physiological sensors[END_REF] In total, we extracted twelve features and with this paper we suggest an easy to understand information visualization with the advantage of having a clear but deep insight into the data, in order to gain new knowledge.

Data Visualization

Related work

We have had experience with using Star Plot diagrams, which are suitable for mobile and touch computers [START_REF] Holzinger | Typical problems with developing mobile applications for health care[END_REF]. Star Plots aka radar charts [START_REF] Ebert | Smart radar chart[END_REF], also called spider web diagram, polygon plot, polar chart, or Kiviat diagrams [START_REF] Morris | Kiviat graphs: conventions and figures of merit[END_REF], are graphical methods of displaying multivariate data in the form of a 2D chart of three or more quantitative variables represented on axes starting from the same point. Each multivariate observation can be seen as a data point in an n-dimensional vector space:

-Arrange N axes on a circle in R 2 -3 ≤ N ≤ N max -Map coordinate vectors P ∈ R 2 from R N → R 2 -P = {p 1 , p 2 , ..., p N } ∈ R N
where each p i represents a different attribute with a different physical unit -Each axis represents one attribute of data Fig. 2. A typical starplot diagram [START_REF] Saary | Radar plots: a useful way for presenting multivariate health care data[END_REF] -Each data record, or data point P is visualized by a line along the data points -A line is perceived better than just points on the axes

Our solution

During the measurements, the participants passed through three phases: First a relaxing, second a stressful and finally a relaxing/recovering phase. Consequently, our idea was to use this data and visualize the results corresponding to these three parts using three different colors. The idea becomes clear in figure 3. Unfortunately, it can be seen only in grey scales.

The upper half of figure 3 refers to the cardiac signal and the lower half to the electrodermal activity. Whereas the three smaller Star Plot diagrams show the feature values of the corresponding phase, the bigger spider diagrams with the darker areas on the right show the overall feature values. The values of each feature are only displayed if a user hovers a feature caption. As an example, here in the figure it is the mean HR. If a user hovers one caption, the corresponding value is shown in all four diagrams. If a user makes a right-click on a caption, they receive a short textual introduction to the meaning of this feature regarding stress.

Both the feature values of the four Star Plots of the cardiac signal and the electrodermal activity part are scaled the same way. The upper limit corresponds to the max overall value and the lower limit to the minimal overall value. This allows us to better compare the Star Plots.

Results and Discussion

In the EMOMES project, we have tested 50 participants so far and provided feedback to them after the test, only by showing them two diagrams: one for the heart-rate and one for the galvanic skin response. We noticed that most of them were very interested in such insights and, as far as they could understand the theoretical concepts behind it within the short time frame given, some have provided supporting information for the signal interpretation and confirmed our hypothesis of the need of individual preliminary knowledge for the interpretation of the measured data. Just an interesting example: on one occasion, we noticed a high skin conductance response, which at first sight seemed similar to a measurement error, however, the participant told us that at that moment the music sounded like a mosquito and because he had a fight with one during the previous night, he got very nervous and flicked his finger.

In support of our hypothesis we extracted 12 features from the signals collected from these 50 participants. The signals were processed twice: once for the overall test and once for the three different parts. Therefore we divided the signals into three data entries each. With this data we provided the information needed by our visualization. The validity of the feature extraction is not given at this time as the low signal quality makes further examination necessary before all results can be confirmed, and only examples are offered. Nonetheless, because our focus is actually the visualization after the feature extraction, we had the necessary data structure for the visualization given in figure 3. Results from our signal processing model are shown in table 1 and are from all three video parts together. Actually, it is not possible to measure in this short time frame if someone has a BOS and therefore we can not claim that this visualization tells whether someone is afflicted by BOS or not. However, providing this clear overview to experts gives them a good objective insight about individual stress reactions and has been confirmed as a good starting point to discuss the autonomous stress behaviours and preventing stress and burnout syndromes in order to decide whether further investigations are necessary or not.

As mentioned in section 4 we can tell something about stress activity by looking at these features. As an example, if you look at the table 1 the sum of GSR tells us whether or not the participant was able to recover from the stress within this time frame. If this value is positive, it means that he had more SNS activity than PNS and vice versa. The same is for the LF/HF -Ratio. If it is high, it means the participant had a low HF activity and therefore less parasympathetic activity. By splitting up the feature extraction in three parts in correlation to the three video parts, we are able to compare them in more detail and have a deeper insight into the physiological activity. This provides us with the possibility to give more detailed feedback to the participants and a more profound basis for discussions and analysis.

Conclusion and Future Research

In this work, we described our lessons learned from testing 50 participants and we present a visualisation for providing insight into physiological behaviours regarding stress.

These goals were achieved to our satisfaction. The visualization displays most of the important feature evaluations regarding stress and displays them in a way that it is easy to compare features between the three parts and the overall features. It gives us a very clean insight into the data and offers good possibilities for knowledge discovery. With a minimum of support, a layman is able to understand the science behind it and can support us with useful information. Nonetheless there are some things that can be improved and expanded.

The low-cost sensor provided workable signals, but for more accurate studies the signal quality is too low. However there are still low-cost sensors that are promising, such the BITalino [START_REF] Alves | BITalino: A Biosignal Acquisition System based on the Arduino[END_REF] and for better results for the visualization others will also be tried. After the completion of the processing, the evaluation of this visualization with a larger test group will provide further insight into our suppositions.

For a better insight for stress prevention, it would be helpful to include in our software a questionnaire like the Hamburger Burnout Inventory (HBI) that reflects the subjective sensation of the participants, especially looking at BOS. If the participants do this in advance of the test, at the end they have an objective and subjective insight.

Fig. 1 .

 1 Fig. 1. Overview of extracted signal features

Fig. 3 .

 3 Fig. 3. Example of the information visualization screen

Table 1 .

 1 Results from our Signal Processing Model

	Feature	Min Mean Max
	MeanRR (ms) 669	867	1114
	MeanHR (bpm) 54	73	93
	pNN50 (%)	24.80 49.44 76.90
	RMSSD (ms)	46	111	265
	LF (%)	23.90 40.69 56.70
	HF (%)	16.50 39.13 68.30
	LF/HF	0.364 1.2480 3.056
	Sum GSR (µS) -3.88 0.4640 3.09

Acknowledgments. We thank the anonymous reviewers for their helpful comments. Many thanks also to Hugo Silva from the Technical University of Lisbon for constantly supporting our research. Thanks to Carl Bck from the Technical University of Graz for some helpful comments. This work was partially funded by Austrian Science Fund (FFG), Innovationsscheck Plus No. 840131.


Jianwei Zhang
email: zhangjw@a.tsukuba-tech.ac.jpi1258131

Katsutoshi Minami

Yukiko Kawai
email: kawai@cc.kyoto-su.ac.jp

Yuhki Shiraishi
email: yuhkis@a.tsukuba-tech.ac.jpkumamoto@net.it-chiba.ac.jp

Tadahiko Kumamoto

Personalized Web Search Using Emotional Features

Re-ranking and re-retrieval of search results are useful techniques for satisfying users' search intentions, since current search engines cannot always return user-desired pages at the top ranks. In this paper, we propose a system for personalized Web search considering users' emotional aspects. Given a query topic, the system presents the major emotion tendency on this topic that search results returned from search engines are reflecting. The system also enables users to specify the polarities and strengths of their emotions (e.g., happy or sad, glad or angry, peaceful or strained) on this topic and offers a re-ranking list of initial search results based on the similarity of emotions. Particularly, the system can automatically obtain Web pages with minor emotion tendency on the query topic by extracting sub-queries with opposite emotions and conducting a re-retrieval. Experimental evaluations show the re-ranking and the re-retrieval achieve encouraging search results in comparison with initial search results.

Introduction

Search engines such as Google and Yahoo! have become main tools to obtain information from the Web. They typically provide a list of search results for a user query, ranked by relevancy and popularity. Generally, users only look through Web pages in the top-ranked search results and may often find the information satisfying their search needs. However, current search engines sometimes fail to return user-desired pages at top ranks due to the diversity of users' search intentions. Previous works have been devoted to improving search results in two main directions: (1) re-ranking pages in the initially retrieved list and (2) suggesting query expansion or reformulation for re-retrieving new pages.

Many aspects are utilized to achieve effective re-ranking of initial search results, such as query logs [START_REF] Zhuang | Re-ranking search results using query logs[END_REF], authorship [START_REF] Bogers | Authoritative re-ranking of search results[END_REF], passage centrality [START_REF] Bendersky | Re-ranking search results using document-passage graphs[END_REF], social tags [START_REF] Yan | Search result re-ranking based on gap between search queries and social tags[END_REF], re-finding [START_REF] Tyler | Utilizing re-finding for personalized information retrieval[END_REF], multiple pairwise relationships between pages [START_REF] Kang | Learning to re-rank Web search results with multiple pairwise features[END_REF], temporal features [START_REF] Chang | Learning-based time-sensitive re-ranking for Web search[END_REF], and demographical contexts (gender, age and income) [START_REF] Kharitonov | Demographic context in Web search re-ranking[END_REF]. Re-retrieval of new pages based on query expansion or reformulation is another effective strategy for improving retrieval accuracy, when initial search results in response to a query contain no pages relevant to users' search intentions. Query expansion or reformulation involves expanding or revising the search query to match additional or new pages by utilizing some technologies and information such as global analysis [START_REF] Xu | Query expansion using local and global document analysis[END_REF], pseudo-relevance feedback [START_REF] Tao | Regularized estimation of mixture models for robust pseudorelevance feedback[END_REF], users' personal information repository [START_REF] Chirita | Personalized query expansion for the Web[END_REF], term classification [START_REF] Cao | Selecting good expansion terms for pseudo-relevance feedback[END_REF], hints obtained from external Web search engines [START_REF] Yin | Query expansion using external evidence[END_REF], social annotation [START_REF] Lin | Social annotation in query expansion: a machine learning approach[END_REF], wikipedia articles [START_REF] Oliveira | Automatic query expansion based on tag recommendation[END_REF], and automatic diagnosis of term mismatch [START_REF] Zhao | Automatic term mismatch diagnosis for selective query expansion[END_REF].

On the other hand, sentiment analysis and opinion mining [START_REF] Pang | Opinion Mining and Sentiment Analysis[END_REF][START_REF] Liu | Sentiment Analysis and Opinion Mining[END_REF] have attracted a lot of research interests, which study emotion and its related concepts such as sentiments, opinions and attitudes. The role of emotions in information retrieval is investigated in some researches [START_REF] Arapakis | Affective feedback: an investigation into the role of emotions in the information seeking process[END_REF][START_REF] Arapakis | A comparison of general vs personalised affective models for the prediction of topical relevance[END_REF][START_REF] Moshfeghi | Role of emotional features in collaborative recommendation[END_REF]. Specially, researches on sentiment retrieval or opinion retrieval [START_REF] Eguchi | Sentiment retrieval using generative models[END_REF][START_REF] Zhang | A generation model to unify topic relevance and lexicon-based sentiment for opinion retrieval[END_REF][START_REF] Huang | A unified relevance model for opinion retrieval[END_REF][START_REF] Li | A unified graph model for sentence-Based opinion retrieval[END_REF] aim to provide a general opinion search service, similar to traditional Web search in the way that both of them find pages relevant to the query, but different from the latter in the way that sentiment retrieval need further determine whether the pages express opinions on the query topic and whether their polarities are positive or negative.

In this paper, we focus on emotional aspects of users and pages and apply such features to effectively modify search results. Not restricted to positivenegative emotions, we adopt more diverse emotions to the re-ranking and the re-retrieval of search results. Users can not only select three types of emotions ("Happy⇔Sad," "Glad⇔Angry," and "Peaceful⇔Strained."), but also set the strengths of emotions for the re-ranking. These features is also utilized to perform a re-retrieval to obtain pages with opposite emotions. Specially, we propose a system that enables the following:

construction of emotion dictionary that represents words and their emotion values on three types of emotions. extraction of emotion with respect to the query topic, i.e., the major emotion tendency that search results returned from search engines are reflecting. interactive re-ranking of initial search results based on the user-specified emotions. automatic re-retrieval of new search results reflecting the opposite emotions. Figure 1 is an example of initial search results for a query topic "Child benefit." Except for Web pages, the system also provides the emotions with respect to the query topic. Users can set their emotions and conduct a re-ranking so as to obtain a list sorted by the similarity between each initial search result's emotions and the user-specified emotions (Figure 2). Moreover, we observe that users tends to set the emotions opposite to the major emotion tendency for obtaining information in multiple perspective. Therefore, we also propose an opposite re-retrieval without user's input for automatically finding pages with minor emotion tendency (Figure 3). The query topic "Child benefit" in this example is a law introduced in Japan about distributing social security payment to the parents of children. The emotions on this topic that initial search results reflect are a little sad, a little angry and a little strained (Figure 1), because most of pages in the initial search list introduce that many people decline this offer, or parents may abuse this grant. When a user sets the opposite emotions and conducts a re-ranking (Figure 2) or conducts an opposite re-retrieval without manually specifying any emotion (Figure 3), the pages with positive emotions can be obtained. For example, some pages at the top ranks of the re-ranking and the re-retrieval lists argue that child benefit is effective in stimulating economic growth and thus express happy, glad and peaceful emotions.

The rest of this paper is structured as follows. Section 2 provides an overview of the system. Section 3 describes the emotion calculation for search results. Section 4 describes how to modify search results using the emotional features. Section 5 evaluates the effectiveness of our system. Section 6 reviews related work. Finally we conclude the paper and discuss future work in Section 7.

System overview

Figure 4 shows the overview of the proposed system. Given a query topic from a user, the system performs the following process:

1. Initial search results are returned by using Yahoo! Web Search API [START_REF]Yahoo! Web Search API[END_REF].

Specially, titles and snippets of pages are obtained for emotion analysis. 2. Emotions with respect to the query topic are calculated. The emotion values for each page ('s title and snippet) are calculated using an emotion dictionary that we have developed, and the averages of emotion values of initial search results are used as the emotions with respect to the query topic, that actually reflect the major emotion tendency of initial search results. The details of emotion calculation are described in Section 3. 3. Both the initial search results and the emotion with respect to the query topic are presented to the user (Figure 1). The emotions have three dimensions and are presented as a graph. 4a. The user can set the emotions by adjusting the strength of emotion on each dimension, and request a re-ranking of initial search results based on emotional features (Figure 2). For example, the initial search results in response to the query topic "Child benefit" reflect that the major emotion tendency is "a little sad," while the user can set stronger emotion "very sad" or opposite emotion "very happy." Re-ranking is expected to sort the pages with emotions close to the user-specified one to the top ranks. 4b. In the case that the user wants to find pages with minor emotion tendency, re-ranking of the initial search results may not satisfy the user's needs if there are not the pages with opposite emotions in the initial search list. Therefore, the system enables the user to alternatively request an opposite re-retrieval (Figure 3). The re-retrieval is expected to find new pages with opposite emotions, not restricted to the initial search results. The user need not manually set the emotions for the opposite re-retrieval. 5a. For the re-ranking, the similarity between each page's emotions and the userspecified emotions is calculated. The re-ranked list of initial search results is sorted in the descending order of emotion similarity. The details of re-ranking are described in Section 4.1. 5b. For the re-retrieval, the page with opposite emotion is first extracted from the initial search results. Then opposite sub-query extracted from this page expands the initial query to match new pages with opposite emotion. The details of re-retrieval are described in Section 4.2. 6. Finally, the re-ranking results or the re-retrieval results are presented to the user.

Calculation of emotions with respect to the query topic

Construction of the emotion dictionary

We construct an emotion dictionary, in which each entry indicates the correspondence of a word and its emotion values on three dimensions. The three-dimension emotions are "Happy⇔Sad," "Glad⇔Angry," and "Peaceful⇔Strained," that are formed based on a statistical analysis and a clustering analysis in our previous work [START_REF] Zhang | Diverse sentiment comparison of news websites over time[END_REF]. A sample of the emotion dictionary is shown in Table 1. A emotion value s(w) of a word w on each dimension is a value between 0 and 1. The values close to 1 mean the emotions of the words are close to "Happy," "Glad," or "Peaceful," while the values close to 0 mean the words' emotions are close to "Sad," "Angry," or "Strained." For example, the emotion value of the word "prize" on "Happy⇔Sad" is 0.862, which means the word "prize" conveys a "Happy" emotion. The emotion value of the word "deception" on "Glad⇔Angry" is 0.075, which means "deception" conveys an "Angry" emotion.

For each of the three dimensions, we set two opposite sets (OW L and OW R ) of original emotion words (Table 2). The basic idea of emotion dictionary construction is that a word expressing a left emotion on a dimension often occurs with the dimension's OW L , but rarely occurs with its OW R . For example, the word "prize" expressing the emotion "Happy" often occurs with the words "Happy," "Enjoy," "Enjoyment," "Joy," but rarely occurs with the words "Sad," "Grieve," "Sadness," "Sorrow." We compare the co-occurrence of each target word with the two sets of original emotion words for each dimension by analyzing the news articles published by a Japanese newspaper YOMIURI ONLINE during 2002 -2006.

First, for each dimension, we extract the set S of news articles including one or more original emotion words in OW L or OW R . Then, for each news article, we count the numbers of the words that are included in OW L and in OW R . The news articles, in which there are more words included in OW L than in OW R , constitute the set S L . Inversely, the news articles, in which there are more words included in OW R than in OW L , constitute the set S R . N L and N R represent the numbers of the news articles in S L and S R , respectively. For each word w occurring in the set S, we count the number of news articles including w in S L and mark it as N L (w). Similarly, we count and mark the number of news articles including w in S R as N R (w). The conditional probabilities are

P L (w) = N L (w) N L P R (w) = N R (w) N R
A emotion value s(w) of a word w is calculated as follows:

s(w) = P L (w) * weight L P L (w) * weight L + P R (w) * weight R
where weight L = log 10 N L and weight R = log 10 N R .

Emotion calculation for individual pages and emotion summary of search results

The emotion values of an individual page are calculated by looking up the emotion values of the words in the page from the emotion dictionary and averaging them 4 . In this way, a page has an emotion value ranging from 0 to 1, since the emotion values of the words in the emotion dictionary range from 0 to 1.

Considering the comprehensibility and the symmetry, the emotion value (x) of a page is further converted to a value (y) ranging from -3 to 3 by the formula: (y = 6 * x -3). When x is 1, 0.5, and 0, the corresponding y becomes 3, 0, and -3.

The emotion values 3, 2, 1, 0, -1, -2, -3 on a dimension, e.g., "Happy⇔Sad," correspond to "Happy," "Relatively happy," "A little happy," "Neutral," "A little sad," "Relatively sad" and "Sad" respectively.

Emotion values on each dimension of search results in response to a query are averaged as the emotion (polarity and strength) on that dimension with respect to the query. As shown in Figure 1, Figure 2, and Figure 3, the graph has opposite emotion polarities for the three dimensions, thus represents the emotion strengths as their absolute values, although the values of negative emotions in the inner system are negative numbers.

Modification of search results based on emotional features

Re-ranking of initial search results based on user-specified emotions

After receiving the three emotion values specified by the user, the system generates an emotion query vector V q = (v q1 , v q2 , v q3 ) using the emotion value on each dimension as its element. For each page in the initial search results list, an emotion page vector V p = (v p1 , v p2 , v p3 ) (p = 1,...,N, where N is the number of initial search results) is determined, the elements of which are the emotion values on three dimensions of each page. The similarity between V q and V p is calculated using the measure of cosine similarity:

sim(V q , V p ) = v q1 v p1 + v q2 v p2 + v q3 v p3 v q1 2 + v q2 2 + v q3 2 × v p1 2 + v p2 2 + v p3 2 (1)
The initial search results are re-ranked in a descending order of the emotion similarity and presented to the user. The pages with emotions similar to the user-specified ones tend to be ranked to the top place.

Re-retrieval of new search results reflecting opposite emotions

The essential of the re-retrieval is to extract the sub-query to expand the initial query. For obtaining pages reflecting opposite emotions, we extract the opposite sub-query as follows:

1. The emotions on the three dimensions with respect to the initial query (emotion summary of initial search results) are represented as an emotion query vector V q = (v q1 , v q2 , v q3 ). Each page in the initial search results list is also represented as an emotion page vector V p = (v p1 , v p2 , v p3 ). The system compares the emotion polarity on each dimension between V q and V p , and determines the candidate opposite pages if emotion polarities on all of the three dimensions of a page are contrary to the emotion query.

The system then calculates the Euclidean distance

3 i=1 (v qi -v pi ) 2
between V q and V p of each candidate opposite page. The page with the largest distance is determined as the opposite page. 3. Keywords are extracted from the opposite page by using Yahoo! Term Extraction API [START_REF]Yahoo! Term Extraction[END_REF]. The keywords scores are larger than 40 are determined as the candidate sub-queries. 4. The system looks up the emotion value of each candidate sub-query from the emotion dictionary, converts the emotion values to the scale ranging from -3 to 3, and forms an emotion sub-query vector V s = (v s1 , v s2 , v s3 ). Then the system compares the Euclidean distance between V q and each V s . The keyword with the largest distance is determined as the opposite sub-query, and is utilized to expand the initial query for the re-retrieval.

Experimental evaluation

Re-ranking effect

We select two query topics for initial retrieval, modify the emotions of initial search results, and then conduct a re-ranking as described in Section 4.1. Table 3 shows the emotions of initial search results, the user-specified emotions, and the emotions after re-ranking. The emotion value on each dimension of initial search results is the average of emotion values of initial search results. The emotion value on each dimension after re-ranking is determined by averaging five students' evaluations on the top ten re-ranked pages. Each student read each top-ranked page and gave a level from -3 to 3 about the emotion polarity and strength that the page reflected.

From Table 3, we observe that if users set emotions different from the major emotion tendency of initial search results, the emotions after re-ranking are consistent with the user-specified emotions. This indicates that the re-ranking based on emotional features can bring the pages with emotions similar to the user-specified emotions to the top ranks.

In the experiments, we observe that users tend to set opposite emotions so as to browse different opinions. However, if there are no pages with opposite emotions in the initial search results list, it is impossible to find them by reranking. In that case expanding the initial query and conducting a re-retrieval are necessary for obtaining such pages. In the next section, we describe the re-retrieval effect. Old age Strength [START_REF] Tao | Regularized estimation of mixture models for robust pseudorelevance feedback[END_REF] Job hunting Media [START_REF] Chirita | Personalized query expansion for the Web[END_REF] Bubble economy Work [START_REF] Cao | Selecting good expansion terms for pseudo-relevance feedback[END_REF] Security camera Particular

Re-retrieval effect

We select twelve query topics for verifying the effect of the opposite re-retrieval described in Section 4.2. We compare the emotions with respect to the initial search results with the emotions with respect to the re-retrieved search results.

The twelve query topics are categorized into three types based on their emotions with respect to the initial search results. If the emotions on all of the three dimensions of the initial search results are positive (Happy, Glad, and Peaceful), the query topic is categorized into Positive Query. If the emotions on all of the three dimensions of the initial search results are negative (Sad, Angry, and Strained), the query topic is categorized into Negative Query. If both positive and negative dimension exist (e.g., Happy, Glad, and Strained, etc.), the query topic is categorized into Mixed Query. Table 4 shows the query topics and their extracted opposite sub-queries. Figure 5, Figure 6 and Figure 7 show the comparison results corresponding to each emotion dimension, respectively for positive queries, negative queries and mixed queries. The abscissa in each graph is query topics and the ordinate is emotion values. The left white bars represent the emotions with respect to the initial search results, and the right black bars represent the emotions with respect to the opposite re-retrieval search results.

From Figure 5, we can observe that for all the positive query topics, the emotion values become smaller or even change to opposite polarities. The overall average of emotion values for all the four positive query topics and all the three dimensions inclines to the negative side in a scale of 0.64. For the negative query topics in Figure 6, all except Query 7 (Citizen judge) on the dimension "Peaceful⇔Strained" obtain the emotions inclining to the positive side. The overall incline scale from the negative side to the positive side is 0.54. Opposite re-retrieval is also effective for the mixed query topics in Figure 7. Except Query 11 (Bubble economy) on the dimensions "Happy⇔Sad" and "Glad⇔Angry," opposite re-retrieval succeeds to obtain search results with emotions inclining to the reverse side for all other mixed query topics. The overall incline scale (from negative to positive, or from positive to negative) for the mixed query topics is 0.14.

There are some comprehensible pages for comparing the contents of the initial and re-retrieved search results. For example, for Query 4 (April fool), the initial search results contain the pages that introduce tricks for April fool and express happy emotions, while the pages in the top re-retrieved search results are the sad pages about refraining from tricks. Another comprehensible example is Query 8 (Tokyo Electric Power Company). The pages in the initial search list in response to this query are the negative pages expressing considerable criticism to the way that TEPCO handled the crisis of nuclear accidents, while opposite reretrieval brings the positive pages that introduce TEPCO's efforts to develop future energy.

Related work

There have been a number of studies on re-ranking search results considering various aspects. Zhuang et al. [START_REF] Zhuang | Re-ranking search results using query logs[END_REF] proposed a Q-Rank method to refine the ranking of search results by constructing the query context from query logs. Bogers et al. [START_REF] Bogers | Authoritative re-ranking of search results[END_REF] utilized the authorship information to extract expert rankings. Bendersky et al. [START_REF] Bendersky | Re-ranking search results using document-passage graphs[END_REF] presented a passage-based approach to leverage information about the centrality of the document passages with respect to the initial search results list. Yan et al. [START_REF] Yan | Search result re-ranking based on gap between search queries and social tags[END_REF] proposed a Query-Tag-Gap algorithm to re-rank search results based on the gap between search queries and social tags. Tyler et al. [START_REF] Tyler | Utilizing re-finding for personalized information retrieval[END_REF] utilized the prediction of re-finding (finding the pages that users have previously visited) to re-rank pages. Kang et al. [START_REF] Kang | Learning to re-rank Web search results with multiple pairwise features[END_REF] proposed to combine multiple pairwise relationships between documents to re-rank search results. Chang et al. [START_REF] Chang | Learning-based time-sensitive re-ranking for Web search[END_REF] exploited temporal features for re-ranking time-sensitive search results. Kharitonov et al. [START_REF] Kharitonov | Demographic context in Web search re-ranking[END_REF] improved search results by using demographical contexts such as gender, age, and income.

Another research direction for improving retrieval accuracy is to re-retrieve new search results based on query expansion or reformulation. Xu et al. [START_REF] Xu | Query expansion using local and global document analysis[END_REF] showed that using global analysis such as word context and phrase structure on local documents (the documents retrieved by the initial query) produced more effective search results. Tao et al. [START_REF] Tao | Regularized estimation of mixture models for robust pseudorelevance feedback[END_REF] proposed to integrate the initial query with pseudo-relevance feedback documents in a probabilistic mixture model without parameter tuning. Chirita et al. [START_REF] Chirita | Personalized query expansion for the Web[END_REF] expanded short queries by analyzing user data at different levels ranging from term and compound level analysis up to global co-occurrence statistics. Cao et al. [START_REF] Cao | Selecting good expansion terms for pseudo-relevance feedback[END_REF] argued against the assumption of pseudo-relevance feedback that the most frequent terms in the pseudo-feedback documents are useful for the retrieval, and proposed to integrate a term classification process to predict the usefulness of expansion terms. Yin et al. [START_REF] Yin | Query expansion using external evidence[END_REF] utilized the hints such as query logs, snippets and search result documents from external search engines to expand the initial query. Lin et al. [START_REF] Lin | Social annotation in query expansion: a machine learning approach[END_REF] extracted candidate expansion terms by a term-dependency method and ranked them based on social annotation resource. Oliveira et al. [START_REF] Oliveira | Automatic query expansion based on tag recommendation[END_REF] proposed to expand entityrelated queries using wikipedia articles and tag recommendation methods. Zhao et al. [START_REF] Zhao | Automatic term mismatch diagnosis for selective query expansion[END_REF] proposed an automatic diagnosis of term mismatch to guide interactive query expansion or create conjunctive queries.

Similar to these researches we also aim to obtain a user-desired re-ranking and re-retrieval search results. Different from them we improve a personalized Web search using the emotional features. The pages with emotions similar to users' can be re-ranked to the top rank and the pages with opposite emotions can be re-retrieved based on the extraction of opposite sub-queries.

On the other hand, sentiment analysis and opinion mining [START_REF] Pang | Opinion Mining and Sentiment Analysis[END_REF][START_REF] Liu | Sentiment Analysis and Opinion Mining[END_REF] are one of the hottest research areas that extract sentiments (or emotion, opinions, attitudes) from text such as movie reviews, book reviews, and product evaluations. Some researches have applied emotion knowledge to information retrieval and its relevant research areas. Arapakis et al. [START_REF] Arapakis | Affective feedback: an investigation into the role of emotions in the information seeking process[END_REF] found that emotions in the information seeking process interwove with physiological, psychological and cognitive processes and formed characterized patterns according to specific task and specific user. In [START_REF] Arapakis | A comparison of general vs personalised affective models for the prediction of topical relevance[END_REF], Arapakis et al. personalized affective models using facial expression data and compared their performance to a general model for predicting topical relevance. Moshfeghi et al. [START_REF] Moshfeghi | Role of emotional features in collaborative recommendation[END_REF] investigated the role of emotional features in collaborative recommendation and their experimental results showed the emotional features extracted from movie reviews were capable of enhancing recommendation effectiveness.

Specially, sentiment retrieval or opinion retrieval is a newly developed research subject, which requires documents to be retrieved and ranked according the opinions about a query topic. Eguchi et al. [START_REF] Eguchi | Sentiment retrieval using generative models[END_REF] proposed several sentiment retrieval models based on probabilistic language models, assuming that users both input query topics and specify sentiment polarity. Similar methods proposed in [START_REF] Zhang | A generation model to unify topic relevance and lexicon-based sentiment for opinion retrieval[END_REF] and [START_REF] Huang | A unified relevance model for opinion retrieval[END_REF] unified topic relevance and opinion relevance respectively based on a quadratic combination and a linear combination. A different method proposed by Li et al. [START_REF] Li | A unified graph model for sentence-Based opinion retrieval[END_REF] combined topic-sentiment word pairs in a bipartite graph to effectively rank the documents. Opinion retrieval from UGC (User Generated Content) such as blogs [START_REF] Zhang | Opinion retrieval from blogs[END_REF] and Twitter [START_REF] Luo | Opinion retrieval in Twitter[END_REF] also yields comparable retrieval performance.

Different the above researches mainly focusing on review documents and positive-negative emotions, we consider any Web pages and more diverse emotions. As we showed in the experiments, there are Web pages that express both positive emotion and negative emotion in different dimensions.

Conclusions and future work

In this paper, we studied the problem of personalized Web search considering emotional aspects: re-ranking initial search results based on user-specified emotions, and re-retrieving new search results with opposite emotions based on the extraction of opposite sub-query. Given a query topic, the system shows the major emotion tendency that search results reflect. After users specify their emotions, the search results similar to users' emotions can be re-ranked to the top place. Even without users' interaction, the system also automatically extracts opposite sub-query so as to re-retrieve the pages with minor emotion tendency with respect to the initial query. We have showed that our system is effective in re-ranking the initial search list and re-retrieving opposite pages.

In the future, we plan to repeat the re-retrieval process and verify whether Web pages with stronger opposite emotions can be extracted. In that case, the problems about the reversion of emotion polarity (from positive to negative, then back to positive) and the topic drift must be taken into consideration.

Fig. 1 .Fig. 2 .Fig. 3 .

 123 Fig. 1. Emotions with respect to the query topic

Fig. 4 .

 4 Fig. 4. Overview of the re-ranking and re-retrieval system

Fig. 5 .Fig. 6 .Fig. 7 .

 567 Fig. 5. Positive query

Table 1 .

 1 A sample of the emotion dictionary

	Word w s(w) on Happy⇔Sad s(w) on Glad⇔Angry s(w) on Peaceful⇔Strained
	prize	0.862	1.000	0.808
	cooking	1.000	0.653	0.881
	deception	0.245	0.075	0.297
	death	0.013	0.028	0.000

Table 2 .

 2 Original emotion words for the three dimensions

	Dimension Original emotion words
	Happy	Happy, Enjoy, Enjoyment, Joy (OWL)
	⇔Sad	Sad, Grieve, Sadness, Sorrow (OWR)
	Glad	Glad, Delightful, Delight (OWL)
	⇔Angry Angry, Infuriate, Rage (OWR)
	Peaceful Peaceful, Mild, Primitive, Secure (OWL)
	⇔Strained Tense, Eerie, Worry, Fear (OWR)

Table 3 .

 3 Re-ranking effect

	Query topics Emotion dimension	Emotion value	User-specified Emotion value
			of initial search results emotion value after re-ranking
	Child benefit	Happy⇔Sad	-0.33	0	0
		Glad⇔Angry	-1.06	3	3
		Peaceful⇔Strained	-0.77	3	3
	Citizen judge	Happy⇔Sad	-0.61	3	3
		Glad⇔Angry	-0.81	3	3
		Peaceful⇔Strained	-0.63	3	3

Table 4 .

 4 Query topics and opposite sub-queries (translated from Japanese)

	Query ID	Positive Query	Opposite sub-query
	(1)	Melting pot	Mixed breed
	(2)	The University of Tokyo	Consumption
	(3)	Internet cafe	Dispatch
	(4)	April fool	Self-restraint
	Query ID	Negative Query	Opposite sub-query
	(5)	Press conference	Campaign
	(6)	Hashimoto Toru	Schedule
	(7)	Citizen judge	Plan
	(8)	Tokyo Electric Power Company	Energy
	Query ID	Mixed Query	Opposite sub-query
	(9)

Since the title and snippet of a page summarize the content of the page and their text is shorter than full page, the system actually calculate the emotion values using the text of the title and snippet for each page so as to shorten the response time.

Acknowledgments

This work was supported by JSPS KAKENHI Grant Number 24800007, 23500140, 24500134, 24780248.


Alexandra Pomares-Quimbaya

Miguel Eduardo Torres-Moreno

Fabián Roldán

MetaExtractor: A System for Metadata Extraction from Structured Data Sources

Keywords: Large Scale Data Mediation, Metadata Extraction, Source Selection, Multi-Agent System, Mediation Systems

The extraction of metadata used during the planning phase in mediation systems assumes the existence of a metadata repository that in most cases must be created with high human involvement. This dependency rises complexity of maintenance of the system and therefore the reliability of the metadata itself. This article presents MetaExtractor, a system which extracts structure, quality, capability and content metadata of structured data sources available on a mediation system. MetaExtractor is designed as a Multi-Agent System(MAS) where each agent specializes in the extraction of a particular type of metadata. The MAS cooperation capability allows the creation and maintenance of the metadata repository. MetaExtractor is useful to reduce the number of data sources selected during query planning in large scale mediation systems due to its ability to prioritize data sources that better contribute to answer a query. The work reported in this paper presents the general architecture of MetaExtractor and emphasizes on the extraction logic of content metadata and the strategy used to prioritize data sources accordingly to a given query.

Introduction

The processing of queries in mediation systems involves processes of logic and physical planning taking into account the characteristics of the data sources available in the system. This information is typically stored in metadata repositories that are accessed whenever a query is evaluated. Unfortunately, mediation systems assume the existence of previously constructed metadata repositories [START_REF] Doan | Efficiently ordering query plans for data integration[END_REF] or focuses only on the structure of data sources, and basic statistics such as the number of records, the number of null data, etc. [START_REF] Akbarinia | Data management in the appa system[END_REF] Although advanced mediation strategies contemplate the existence of more comprehensive metadata such as the number of objects contained in a source [START_REF] Bleiholder | Query planning in the presence of overlapping sources[END_REF], the way in which this metadata is obtained has not been well defined. Parallel to mediation systems of structured sources, several proposals have been made to summarize the contents of available sources in the Web: using trees [START_REF] Hayek | Summary management in p2p systems[END_REF] to describe the dependency relationships between sources [START_REF] Sarma | Data integration with dependent sources[END_REF]. These alternatives are useful for increasing the richness of metadata. However, their generation requires high human interaction or includes only general aspects that do not allow a real differentiation among sources, especially when the sources are dependent and data fragmentation is not disjoint. Faced with these limitations of mediation systems this article proposes MetaExtractor a system designed for the automatic extraction of metadata from structured distributed data sources that are registered in a mediation system. MetaExtractor's goal is to increase the quality of metadata repositories through methods that do not require intensive human involvement. MetaExtractor design is based on multi-agent systems that uses data sources as resources to meet its goal of extracting a particular type of metadata. MetaExtractor considers the extraction of structure, capability, quality and content metadata. The structure of this article presents in Section 2 the analysis of related works on the area of mediation systems that allow to put into context the contribution of MetaExtractor. Subsequently, Section 3 presents an overview of MetaExtractor that is detailed in Section 4. Section 5 reports evaluation results on priorization of data sources using the extracted metadata. Finally, Section 6 presents the conclusions and future work.

Related Work

Different approaches to support data queries in the context of heterogeneous and distributed sources have been studied for over 15 years. Most of them are based on mediation systems [START_REF] Wiederhold | Mediators in the architecture of future information systems[END_REF] that aims to provide an integrated view of heterogeneous and distributed data sources respecting their own autonomy [START_REF] Roth | A wrapper architecture for legacy data sources[END_REF]. The architecture of mediation systems [START_REF] Roth | A wrapper architecture for legacy data sources[END_REF][START_REF] Tomasic | Scaling access to heterogeneous data sources with DISCO[END_REF][START_REF] Garcia-Molina | The tsimmis approach to mediation: Data models and languages[END_REF][START_REF] Kossmann | The state of the art in distributed query processing[END_REF] consists of four levels of abstraction: i) the data sources level, ii) the adaptation (wrappers) level, iii) the mediation level and iv) the application level. Query processing in this type of systems is coordinated at the mediation level and takes place in two stages: planning and execution. In the planning stage, sources that can fully or partially answer the query are selected and then the query is rewritten into subqueries, using the external model of each source. To select appropriate sources, the mediator uses a metadata catalogue that includes the external model and other information sources, whose level of detail and accuracy varies according to the type of mediator. In the execution stage, the mediator sends the subqueries to each source and is responsible for coordinating the execution of the queries, and receiving and processing responses in order to integrate them.

One factor that affects the accuracy and efficiency of a mediation system is its planning strategy, which is directly related to the quantity and quality of available metadata. In the first generation of mediation systems, such as: Information Manifold [START_REF] Levy | Querying heterogeneous information sources using source descriptions[END_REF], TSIMMIS [START_REF] Garcia-Molina | The tsimmis approach to mediation: Data models and languages[END_REF], DISCO [START_REF] Tomasic | Scaling access to heterogeneous data sources with DISCO[END_REF] and Minicon [START_REF] Pottinger | Minicon: A scalable algorithm for answering queries using views[END_REF], the planning process uses as metadata information the processing capabilities of sources (e.g. the number of required conditions, or the attributes that could be defined in the predicate). Another group of strategies such as: iDrips and Streamer [START_REF] Doan | Efficiently ordering query plans for data integration[END_REF], navigation paths [START_REF] Bleiholder | Query planning in the presence of overlapping sources[END_REF] perform the planning process by means of metadata that describes the content of the sources. Other proposals such as QPIAD [START_REF] Khatri | Qpiad: Query processing over incomplete autonomous databases[END_REF] and the quality-oriented presented in [START_REF] Naumann | Completeness of integrated information sources[END_REF] use detailed statistics on the quality of the data contained in the sources to reduce the number of plans. Meanwhile, proposals for large-scale mediation: PIER [START_REF] Huebsch | Querying the internet with pier[END_REF], PinS [START_REF] Villamil | Pins: Peer-to-peer interrogation and indexing system[END_REF], Piazza [START_REF] Tatarinov | The piazza peer data management project[END_REF], PeerDB [START_REF] Ooi | Peerdb: peering into personal databases[END_REF], and SomeWhere [START_REF] Rousset | Somewhere: A scalable peer-to-peer infrastructure for querying distributed ontologies[END_REF] use location of metadata, content summary and description of reputation sources, among others.

The metadata used in these systems are an essential input for the performance of the mediation process. However, obtaining such metadata from structured data sources is limited to the manual (human) description of the structure of the sources and some quality statistics obtained during the operation of the system. Even if the owners or managers of each source of information can define some metadata manually, to ensure maintainability, efficiency, consistency and cost of the mediation system, it is necessary to generate strategies for automatically obtain metadata from the mediation repositories.

The existing methods for generating metadata can be classified into three groups: i) extraction, ii) collection and iii) hybrid generation [START_REF] Greenberg | Metadata extraction and harvesting: A comparison of two automatic metadata generation applications[END_REF]. In the first case the aim is to obtain the metadata based on the execution of techniques for analyzing, mining, evaluating, etc. In the case of metadata collection the goal is to gather pre-built metadata. Finally, hybrid generation obtains existing metadata, and from its analysis generates new metadata [START_REF] Margaritopoulos | Automatic metadata generation by utilising pre-existing metadata of related resources[END_REF]. The aim of the MetaExtractor project is focused on metadata extraction from structured data sources that may contain narrative text in some of their attributes.

Literature reviews show that most research efforts suggests strategies to extract metadata from unstructured information available on the web, the vast majority of available methods use processing algorithms that analyze natural language texts in order to generate structured descriptions [START_REF] Hripcsak | Using discordance to improve classification in narrative clinical databases: An application to communityacquired pneumonia[END_REF]. These algorithms are part of strategies for information retrieval that assess text in a semantic and syntactic way to get a list of descriptors for the content of the sources [START_REF] Kowalski | Information Retrieval Systems: Theory and Implementation[END_REF]. Although there are methods of metadata generation from structured sources its extraction and / or collection is focused on basic attributes such as size or scheme that cannot act as a true differentiator of data sources.

This article presents MetaExtractor a system that modifies and extends these existing methods and techniques to enhance the extraction of metadata from structured sources. MetaExtractor obtains metadata using different techniques according to the type of metadata that must be extracted. In addition, given a query, MetaExtractor prioritizes data sources that better contribute to answer it. The proposed MetaExtractor architecture includes the use of data mining techniques to identify the type of content from a source. The intention is to explore a sample of each data source to establish whether there is a tendency to have some type of instances of a business object (e.g. client, patient).

MetaExtractor Overview

As Section 2 illustrates, current mediation system strategies for source selection assume the existence of the required metadata for query planning, extracts only basic metadata, or require an important manual effort to feed metadata repos- itories. In order to fulfill this gap this paper proposes MetaExtractor a system that allows to extract structure, quality, capability and content metadata from structured data sources. MetaExtractor architecture is based on the interaction of software agents in charge of extracting different types of metadata from distributed and heterogeneous structured data sources. The main idea behind the agent architecture is for MetaExtractor to have agents located in the same location as the data source and watching over the sources' logs to identify any important or relevant changes on the structure or data contained in each source. This section presents an overview of MetaExtractor functionality and architecture. The following section emphasizes on key aspects of the agents in charge of metadata extraction.

MetaExtractor Preliminaries

The goal of MetaExtractor is to provide the metadata required for query planning in a mediation system. Figure 1 illustrates the relationship between MetaExtractor and a mediation system, the goal is to act as the knowledge base during the planning phase of a query.

MetaExtractor extracts and stores metadata based on the assumption that data sources contain pieces of information of the relevant objects in a specific domain (e.g. patient, client, campaign) from now on called VDO (see Definition 1). The VDO illustrated in Figure 2 represents a Patient composed by four concepts (Person, Medical Act, Medical History, Affiliation). This VDO pertains to the medical domain, which is going to be used from now on to describe MetaExtractor's functionality.

Definition 1 Virtual Data Object (VDO).

A VDO is a logical set of related concepts relevant to a group of users. Figure 2 illustrates a VDO joining four concepts. Each concept has data type properties whose values are data literals. Concepts are related through object type properties whose values are instances. VDOs are virtual because their instances are partitioned and distributed on several data sources. MetaExtractor considers queries with selection conditions on the properties of the concepts composing the VDO. For example, the query hereafter uses the VDO Patient and selects the id of patients with a "Buphtalmos" diagnosis.

Query 1 Q(V DO P atient , properties(id), conditions(diagnosis = Buphtalmos))
In the following sections we will work with queries which include several conditions, such as follows:

Q(V DO name , properties(id), conditions(condition 1 , condition 2 , ..., condition n ))
When a mediator receives a query it can issue a request to MetaExtractor asking about the facts related to the VDO involved in the query; these facts may be given directly to the mediator or they can be used by MetaExtractor to prioritize the data sources that better contribute to answer the query.

MetaExtractor Processes

Figure 3 illustrates the agents and processes involved in the execution of MetaExtractor. The GUI process, the Server process and the Source process include a set of sub-processes (agents), which corresponds to activities of an agent with a defined behaviour. The GUI agents represent the interactions of the users, the Server agents manage persistence of metadata and users, and include the logic to prioritize data sources given a particular query. To accomplish their tasks they use the metadata extracted by the Source agents that are in charge of the actual extraction of metadata and are the ones watching over the source itself.

The metadata extraction starts with a communicative act between the Metadata Manager Agent, who proactively and periodically activates the metadata extraction. The activation event triggers the activation of the Source Manager Agent and this, in turn, sends an event to the related Data Source Agents. Finally, each Data Source Agent communicates with the Extraction Coordination Agent that is in charge of coordinating the extraction of each type of metadata. Currently, MetaExtractor provides four agents in charge of extracting diferent metadata types: structure, quality, content and capability metadata. The following subsection describes each one of metadata types and Section 4 the internal logic of each metadata extractor agent. It is important to notice that according to the requirements of the mediation system, different kinds of metadata extractor agents can be added later on to the system. . These conditions include a restriction of value over an attribute. The content metadata allows to identify the data sources that better could answer a query according to the role it can play as a contributor of instances of a VDO in the domain where the restriction is true. Roles reflect the ability of data sources to resolve query predicates. Section 4 describes the roles and the strategy used by MetaExtractor to describe the content of a data source. 4. Capability Metadata Extraction: This type of metadata is extracted to identify data sources that have restrictions over the type of queries that they can answer. This metadata is specially important in data sources that can only be accessed through a set of services or an interface that limits the attributes that may be acquired. It is also relevant when data sources demand a specific number of query conditions to answer a query. In the medical domain for instance, a data source may restrict the access of the patient's name or may demand the inclusion of at least one condition in the query.

Extraction functions

MetaExtractor provides three functions for querying the metadata required for planning purposes. These functions are:

-Query data source metadata: Allows to query the values of metadata of a specific data source. -Prioritize data sources: According to the properties and conditions related to a VDO query it delivers the list of prioritized data sources to answer it. In order to prioritize MetaExtractor uses the logic proposed in [START_REF] Pomares-Quimbaya | Improving source selection in large scale mediation systems through combinatorial optimization techniques[END_REF]. This strategy is based on combinatorial optimization techniques. -Metadata subscription: Allows to obtain changes on the metadata of a data source or a set of data sources automatically.

Extractor Agents

This section presents the logic within content, quality and capability metadata extractor agents.

Content Metadata Extractor Agent

The goal of this agent is to identify the role that a data source may play during the execution of a query taking into account its content. This task is not straightforward in structured data sources, because they may contain different records, each one of them containing different content. As a consequence, the Content Metadata Extractor Agent must identify the better way to describe a data source given the content of its records. Lets look an example. Consider three hospital databases DS1, DS2 and DS3. According to the kind of hospital these databases may be specialized on a specific type of patients. For example DS1 is specialized on information about patients with cancer. DS2 is specialized on pediatrics and, as a consequence, it contains only child patients. And DS3 contains both, patients with cancer, child patients, as well as other type of patients because is the database of a general hospital. In this domain the agent must describe the role according to the attribute "diagnosis" and "age" differentiating the specialization of DS1 (i.e. diagnosis = Cancer) and DS2 (age < 18), and indicating that even if DS3 is not a specialist it may contain records with this content. Roles reflect the ability of sources to solve conditions. Given the analysis of the roles played by a database in a mediation system, we propose the following roles: specialist and container. The definition of each source role is described in Definition 2 and 3. In these definitions all the instances of VDOj stored in data source DSi are noted ext(DSi, V DOj) 1 . U designates all the data sources participating in the system. All the instances of VDOj available in the system are denoted ext(U, V DOj). The subset of ext(DSk, V DOj) corresponding to the instance that verifies a condition p is denoted ext(DSk, V DOj) p and card() is the cardinality function.

Domain Training

The content of a data source must be described in terms of its domain. For instance, a data source containing electronic health records (EHR) must be described in terms of diagnosis, treatments, medicines, or in terms of the properties of patients like age and gender. Typically, a data source of EHR contains attributes that store all this information; however, some of them, and frequently the most important, are narrative text attributes that contain these terms hidden in lots of text.

The goal of this phase is to record and train the system to recognize what kind of VDOs are contained in a data source. In order to do that MetaExtractor must be trained to identify when the content of a data source is related to a VDO with a specific value in one or more properties. For instance, when a data source contains patients with a specific diagnosis. This identification is straightforward when data sources contain mostly well coded attributes; however, as mentioned, in some domains (e.g. medical) this information may be within texts.

This phase works as follows, for each one of the VDO properties that are usually used as query conditions (e.g. diagnosis) and their possible values according to well known thesaurus or terminology dictionaries (e.g. SNOMED CT [?]), MetaExtractor searches on the internet (using an API created for this purpose) in order to identify what are the common words used when talking about the condition with a specific term (e.g. diagnosis and diabetes). The search involves the property and its possible terms (e.g. disease, diabetes). According to the domain of the mediation system, the properties, as well as their possible terms, must be parametrized in the system. At the end of this training phase each one of the terms related to selected properties has associated a dictionary of related words used in conjunction with the term. The outputs are called training dictionaries, and are used later to identify the terms that better describe a data source.

Content Description This phase identifies the role played by a data source within the system. The algorithm proposed to identify the role is illustrated in Algorithm 1. The principle of this algorithm is to use narrative text attributes and a subset of structured attributes from the data source to identify its main content. For example, the narrative text attributes of an EHR that contain the evolution and the treatment of the patient are very important to describe the type of patients the data source has. Additionally, some of the structured attributes (i.e. attribute that contains a limited number of possible values) may provide hints on the content of the data source.

In case the size of a data source exceeds a threshold, the first part of the algorithm reduces its size applying a stratified sample technique [I]. This technique uses a structured attribute to identify the strata.

Then, for each one of the records in the data source sample [II], and using text mining techniques, it annotates the narrative texts taking into account the training dictionaries created in the Domain Training phase [III]. As an example we can obtain for a record the annotation (diagnosis = heart failure, sign = pulmonary edema).

Next, analyzing the structured attributes it identifies its value and adds it to the annotations [IV]; After this step the annotation may include (diagnosis = heart failure, sign = pulmonary edema, gender = F).

Once MetaExtractor analyzes all the records it applies a neighborhood based clustering algorithm [START_REF] Everitt | Cluster Analysis[END_REF] to identify if there is a specific group of similar records [V] in the data source. The annotations that better describe each cluster are used to specify the role of the data source. In case a cluster contains more than 50% of the records of the data source, the data source will be stored as a specialist with respect to the property with the value that better describes the cluster (e.g. diagnosis:heart failure) [VI]; otherwise, it will be stored as a container.

Quality Metadata Extractor Agent

This agent evaluates the quality state of a data source based on the analysis of nullity of its attributes. To obtain this state MetaExtractor evaluates the frequency of null values in each one of the attributes and the general density of nullity of the data source. The density is very important because some attributes may have high frequency of nullity not because of the quality, but because of the domain. For instance, an attribute middle name may have a lot of nulls because is an optional value in the domain, its null frequency does not reveal a quality problem, but a business rule. In order to assure the performance of MetaExtractor when data sources contain high number of records, it provides the possibility of obtaining quality metadata over a sample from the original data source. This sample follows a systematic approach using as sample size a parameter that can be configured in the system.

Capability Metadata Extractor Agent

Capability metadata extractor goal is to identify the restrictions of data sources according to the following characteristics:

1. Attributes that can be specified in the query 2. Attributes that can be included in the predicate of the query 3. Attributes that cannot be specified in the query 4. Attributes that cannot be included in the query predicate. 5. Minimum number of attributes that must be in the query predicate 6. Maximum number of attributes that must be in the query predicate

The strategy to obtain this information is based on the execution of provequeries. These queries are light queries that belong to a defined set of queries each one of them intended to validate one or more of the restrictions. An example of a prove-query ask for a specific attribute without any predicate, this query contributes to the validation of restriction characteristics 1,3 and 5. For evaluating restriction number 2, MetaExtractor tries to execute a query with one condition in the predicate including the attribute compared to a valid value according to the type of the attribute (e.g. numeric, string). If the query does not return an error, the attribute is included in the set of safe attributes in the predicate. The last restriction is evaluated through the incremental of the number of conditions in the predicate. The attributes used in this case are only the ones that passed the restriction 2. Once a data source is registered the defined set of prove-queries is executed over it.

Prototype and Functionality Evaluation

In order to evaluate the behavior of MetaExtractor a prototype has been constructed and used to evaluate its extractors and query capabilities. This section presents the main results obtained during this evaluation. Section 5.1 presents the characteristics of the prototype. Section 5.2 details the experimental results.

Prototype

In order to evaluate the behavior of MetaExtractor we developed the components presented in Figure 4. Components were written in Java. the Global schema and metadata repository are stored in Virtuoso [START_REF] Software | Openlink software virtuoso open-source (vos) versión 1[END_REF]. The communication and interaction of agents uses the multiagent framework BESA [START_REF] González | Besa: Arquitectura para construcción de sistemas multiagentes[END_REF]. Queries are accepted in SPARQL [START_REF] Prud | Sparql query language for rdf[END_REF]. The content metadata extractor agent uses the natural language processing API provided by LingPipe [START_REF] Carpenter | Text Analysis with Ling Pipe 4[END_REF] and the Weka environment.

Structural Metadata and Global Schema One of the main issues in mediation systems is how to control the heterogeneity of data sources that contribute to the system. Approaches that allow each data source to manage its own schema have demonstrated to scale well, but have important drawbacks in the expressiveness of domain concepts [START_REF] Ooi | Peerdb: Peering into personal databases[END_REF]. Because of this, MetaExtractor follows a global schema approach that allows to relate the structure of each one of the data sources to the schema of the domain that allows to create VDOs. This decision was made considering that mediation systems are used to create virtual environments of data sharing around a domain. The global schema defines this domain, the relationship between a data source and the VDOs global schema represents the contribution of this data source to the domain.

The Global Schema in MetaExtractor is created as an ontology in OWL [START_REF] Owl Working Group | OWL 2 Web Ontology Language: Document Overview[END_REF]. It can be created by importing it using a .owl extension or automatically based on a seminal data source. In the latter case, the tables of the data source are interpreted as Classes, its attributes as Data Type Properties and the foreign keys as Object Type Properties. Although the extraction from a structured data source does not allow to include all the elements of a OWL ontology, they can be added manually after its creation.

In order to create the relationship between data sources and global schema, MetaExtractor provides a method that identifies synonyms between the names of tables and attributes with the names of classes and properties of the global Metadata pieces are stored as triples (Subject, Predicate, Object), respecting the semantics and syntaxis of metadata ontology and global schema ontology. In these triples Subject is an individual of the classes defined in the ontology, Predicate is a property and Object is the value associated to the Subject-Predicate.

When a data source is registered in MetaExtractor the first performed action is to create a triple that specifies that the name of the data source is a Data Source. Then, MetaExtractor proceeds creating the triple that describes the data source. The following expression is an example on how to create a triple:

Triple triple = new Triple( Node.createURI(systemOntologyBaseName + ''\#'' + tableName), Node.createURI(systemOntologyBaseName + ''\#hasAttribute''), Node.createLiteral(systemOntologyBaseName + ''\#'' + attribute))

Experimental Results

Eventhough MetaExtractor was created for being used in any context, the motivational context was the integration of medical data sources containing electronic health records in a country. Tests with MetaExtractor were executed in this context. The environment involves 100 simulated data sources containing EHRs. Data sources were created in three different DBMS: PostgreSQL, MySQL and SQL Server 2012. The records contained in each data source were extracted from a database from a general hospital; however, for testing purposes, the database was divided into subsets in order to have different types of specializations (e.g. data sources specialized on obstetrics and gynecology) or general data sources. Categories were trained based on the SNOMED terms.

Tests involve the extraction of structure, content, quality and capability metadata as well as the prioritization using the extracted metadata. Due to space limitations we are going to focus in content metadata extraction tests. Figure 6 shows the results comparing the precision of metadata when the extraction of content and quality metadata used samples instead of the complete databases. Although the extraction of samples reduces the precision of the extracted metadata, the tests allows us to conclude that the precision of metadata is stable and can be used to extrapolate the quality and content of the complete data source.

Figure 7 illustrates the differences on True Positives (TP) and False Positives (FP) taking into account the Container and Specialist roles. The main conclusion of these tests is that the rate of TP and FP confirms the reliability of the system.

Conclusions and Future Work

This paper presents MetaExtractor a system that extracts, stores and maintains metadata. MetaExtractor is able to extract content, quality, capability and structure metadata from structured data sources that contain high volume of narrative texts. To the best of our knowledge, this is the first attempt to support formally the extraction of this type of metadata in mediation systems.

MetaExtractor architecture is based on the interaction of software agents in charge of extracting different types of metadata from distributed data sources. It stores metadata in a repository that follows the semantics and syntax of an ontology that allows to obtain precise metadata given a user query. MetaExtractor was designed to be used in architectures where the proportion of distribution with respect to the structure of an object (VDO) is higher than the distribution of its instances, making the metadata useful to reduce the number of sources required for a query. It improves the evaluation of queries that involve predicates with high selectivity and guarantees the dynamic adaptability of the system.

MetaExtractor is being implemented as part of a large scale mediation system. The current prototype is a proof-of-concept. Performance evaluation will be tested in the next stage of development. Short term work involves the analysis of redundancy between data sources to avoid the use of data sources that may provide the same set of instances.

Fig. 1 .

 1 Fig. 1. MetaExtractor in a Mediation System

Fig. 2 .

 2 Fig. 2. VDO Patient.

Fig. 3 .

 3 Fig. 3. MetaExtractor Agents Interaction

Definition 2

 2 Specialist Role. A data source DSi plays a specialist role w.r.t. a condition p in a query on VDOj iff most instances of VDOj stored in DSi match p. IsSpecialist(DSi, V DOj, p) =⇒ card(ext(DSi, V DOj) p ) ≥ card(ext(DSi, V DOj) ¬p ) Definition 3 Container Role. A data source DSi plays a container role w.r.t. a condition p in a query on VDOj iff DSi contains at least one instance of VDOj that matches p. IsContainer(DSi, V DOj, p) =⇒ ext(U, V DOj) p ∩ ext(DSi, V DOj) p = ∅ The process of content metadata extraction is divided into two phases, the Domain Training phase and the Content Description. The following subsections describe both of them.

Algorithm 1

 1 Role Identification Input: DS //DataSource Cat(cat1{v1,...,vn},...,catm{v1,...,vn}) sizeThreshold Output: QRoles(role(catj),...,role(catk)) Begin QRoles={}, annotations={}, clusters={} [I] If (size(DS) > sizeThreshold) s = getSample(DS) Else s = DS [II] ForAll (reg in s) ForAll (att in reg) If (narrativeAtt(att)) [III] annotations[reg] = annotations[reg] + annotate(att) Else [IV] annotations[reg] = annotations[reg] + idValue(att) [V] clusters = Cluster(annotations) ForAll (c in clusters) [VI] If (size(c) > size(s)/2) QRoles = QRoles(specialist(c.cat)) Else QRoles = QRoles(container(c.cat)) Return(QRoles) End

Fig. 4 .

 4 Fig. 4. MetaExtractor Prototype Components.

Fig. 5 .

 5 Fig. 5. Metadata Ontology

Fig. 6 .

 6 Fig. 6. Precision Quality and Content Metadata with Samples.

Fig. 7 .

 7 Fig. 7. True Positives and True Negatives Specialists and Containers.

  Once a data source is registered MetaExtractor is able to extract and/or obtain from them the following metadata (by means of the Source Agent):1. Structure Metadata: This type of metadata describes the relationship between the objects of a data source with the domain VDOs. For instance, a data source in the medical domain may have a table called Attention that contains all the attentions of a patient in a medical institution, this table may be the equivalent of Medical Act in the description of the VDO patient.In this case the metadata structure contains the equivalent relationship between the table Attention and the concept Medical Act. Structure metadata includes the name of the tables, attributes and relationships, and their relationship with the domain VDOs by using the operators Equivalence and Inclusion. 2. Quality Metadata: MetaExtractor provides information about the quality state of a data source. This type of metadata is very important to distinguish which data source is more promising to answer a query when two or more data sources have similar structural and content characteristics. The quality state is described using the following attributes:-Null percentage: It serves to identify the level of deterioration of an attribute according to the frequency of nulls related to the size of a sample. An attribute with a value 65% in Null Percentage can mean that the quality is too low. -Null density: It calculates the density of null values in a table, its goal is to differentiate tables that have few attributes with high frequency of null values and tables that have a larger number of attributes with low frequency of null values. -Maximum null frequency: Identify the attribute with the highest frequency of nulls. 3. Content Metadata Extraction: Most of the queries over mediation systems involve a condition over a set of attributes of the VDO; for instance in the medical domain, a query over the patient VDO may have a condition over the diagnosis (e.g. diagnosis = cancer)

This extension contains the VDO identifiers.

Acknowledgements

This work was supported by the project "Extracción semi-automática de metadatos de fuentes de datos estructuradas: Una aproximación basada en agentes y minería de datos" funded by Banco Santander S.A. and Pontificia Universidad Javeriana.