Fabienne Kuhn
email: fabienne.kuhn@bfh.ch

Andreas Spichiger
email: andreas.spichiger@bfh.ch

Reinhard Riedl
email: reinhard.riedl@bfh.ch

Sensor Data Meets Social Networks Reflecting on Benefits in the Case of a Patient Room

Keywords: Social media, sensor media, requirements engineering, ubiquitous computing, information provider, information access, Web 2.0, E-health. 1

In a hospital, information exchange is essential to save lives and to prevent life-endangering mistakes. Information exchange is supported by a hospital information system (HIS). From a theoretical perspective, the deployment of an HIS is promising because it reduces errors and duplication of information. In practice, however, there are some major problems concerning the usage of such a system. One way to deal with these problems is introduced in this paper: the integration of sensor data into social media. The paper concentrates on the conceptual benefits and risks such an integration may generate. It focuses on the case of a patient room.

Introduction

The information management in a hospital is often supported by a hospital information system (HIS) which addresses the various needs in a hospital by integrating most applications used there [START_REF]EHR Scope: Hospital Information Systems (HIS)[END_REF]. HIS provides some essential benefits, but there can still be major problems when using it on a daily basis. Benefits of using an effective HIS include information integrity, prevention of medication errors, reduction of transcription errors, duplication of information entries and report turnaround time [START_REF]EHR Scope: Hospital Information Systems (HIS)[END_REF], [START_REF] Watson | Woman dies after replacement nurse gives her wrong drug during labout dispute[END_REF]. Problems arise in the following areas [START_REF] Marion | Hospital information systems: perspectives on problems and prospects, 1979 and 2002[END_REF], [START_REF] Bates | Using information technology to reduce rates of medication errors in hospitals[END_REF], [START_REF] Wojciechowski | Distributing and Replicating Data in Hospital Information Systems URL=[END_REF], among others: Data recording and storage  Immediate data access is required in a context where urgent cases are commonplace. Depending on the data storage solution, this requirement may not be met because data cannot always be recorded and stored in a timely manner. Sometimes not only the data storage but also the workflow does not allow instant recording of data. Concerns arise that information does not flow quickly enough during personnel changeovers, e.g. a change of shift.  When a patient moves from one ward to another there are no techniques to move his data along effectively. This is because one organization unit cannot copy just one patient's data from another organization unit. Furthermore it is not easy to find old data about a newly arrived patient, for example when this person comes from an external domain.  Classic information systems are constructed for people who work on computers and nursing staff work with humans. The time taken to record data sometimes is longer than is allowed for in a nurse's job description. This leads to poor recording habits like copy/paste from other reports or shortening notes so they become unspecific. Thus wrong medication 1 and wrong therapy can result.

Data view

 Doctors and nursing staff can lose the overview because there are many different screens where many details can be entered, which are not necessarily important but can be shown anyway.  When data is not filtered and not declared, doctors and nursing staff may focus on specifics and do not see what others have written.  Some approaches use alerts, reminders and warning messages to try to generate a specific view for each user. However, they can be sent regardless whether the information is relevant for the recipient or not. Thus the users tend to turn them off.

Culture

 Communication, which is very important in a hospital, is not simply about exchanging information. It is about generating effects; the sender wants the recipient to act. Furthermore, with direct communication the sender can find out how much the recipient understands, can correct a misunderstanding and can estimate and influence the recipient's actions. It is also about maintaining relationships.

We are interested in how user interfaces can be rebuilt as a smart system, focusing mainly on two problem areas. An important area concerning the problems mentioned earlier is the recording of data. It should be correct but not time consuming; it should support the staff but not interfere significantly with their workflow. A possible solution can be the deployment of sensors. Nevertheless it is risky to add more information into a system which already has several unresolved issues. The expectation is that it will not work. Let us follow this idea anyway: how should a system be rearranged to improve its usage? For a start there should be sensors which record the well-being of a patient and his whereabouts. Furthermore, medicines should be locatable to determine which medicine was given to whom. Another important problem area is the data view. The view should be composed user-and-situation-specific way without irrelevant data. Social media can provide those views. It also addresses another problem with HIS: data privacy. Social media offers the possibility to share selected data only with a selected group of people. Along with the previously mentioned requirements, which can be met either by sensor or social media, others can be met by the combination of both. For example the actors may comprehend the context and orient themselves better. This paper shows further possible conceptual benefits and risks concerning the idea of the combination of sensor and social media (SoSeMe) as a possible solution to the problems mentioned above. We have concentrated on the case of a patient room. This case was selected because a patient room provides a small and controlled environment and different stakeholders meet multifaceted challenges.

Fig. 1 gives an overview of the subjects raised thereby. Our research follows research guidelines according to Hevner [START_REF] Hevner | Design Science in Information Systems Research[END_REF]. In compiling the results we have mainly focused on the dimensions quality and economy. The paper is structured as follows: Theoretical basics and ideas are provided in chapter 2. Chapter 3 summarizes the case results and shows topics discussed for the patient-room case.

Fig. 1 Situation of the subject of this paper

Related Research Work

The idea of combining social and sensor media is not new. When users are requested to tag their posts with keywords, the benefits increase because it is easier to find posts related to specific topics [START_REF] Nagarajan | Citizen sensor data mining, social media analytics and development centric web applications[END_REF]. An example here is Twitter, there the user can tag keywords by typing a "#" at the beginning. This makes it easier for machines to find relevant related information for analysis. For example natural disasters are easier to detect and to monitor by mining the posts of social media users when they distinguish keywords like the name of the service which analyzes the data [START_REF] Aulov | Human Sensor Networks for Improved Modeling of Natural Disasters[END_REF]. Areas where social and sensor networks can be linked effectively are shown in [START_REF] Breslin | Integrating Social Networks and Sensor Networks[END_REF]. The article concludes that SoSeMe applications are more context aware. They are more deeply integrated into daily life and can act as an enabler for emerging services, e.g. mobile communication, internet, multimedia, etc. The framework in [START_REF] Stelle | Social Media, Mobile Devices and Sensors: Categorizing New Techniques for Health Communication[END_REF] describes communication in e-health primarily through social media. Those mentioned papers clearly indicate potential benefits. Even so, SoSeMe contrasts itself by researching in an area where data is mainly gathered through sensors, not people, and stored within the logic of social media. Furthermore the communication processes and rituals in a patient room are examined. With this approach, advantages in the limited setting and the intricacies of traditional communication are well understood.

Data Processing

Sensor and social media have different roles to play. In the following chapters their relevant roles are introduced for the case. This short theoretical background focuses on data processing: how data is acquired, stored and viewed. Furthermore it introduc-es topics inevitably connected with either social or sensor media in the context of a patient room.

E-Health

E-health focuses on the technical side of electronic media and adapts it to health care [START_REF] Mea | What is e-Health (2): The death of telemedicine?[END_REF]. Health 2.0 uses networks of stakeholders like patients, doctors and scientists to personalize health care and promote collaboration [START_REF] Bos | Patient 2.0 Empowerment[END_REF]. It allows the patients to actively participate in their own healthcare through information and communication technology. In Fig. 1 Health 2.0 is the interface between e-health and social media.

Health networks may have the same problem as large enterprises: they are extremely complex and different parts often operate in silos [START_REF] Becker | A wireless sensor network architecture and its application in an assistive environment[END_REF]. This makes it hard to communicate across organizational units. However, if the flow of information between them stagnates, significant risks would be created for the patients. In addition, the non-sharing of information increases the risk of reacting too late to the spreading of infectious diseases. One solution to the latter problem is found in the Global Pandemic Initiative from 2006, where IBM offers several pieces of its healthcare technology portfolio to work with major worldwide public institutions [START_REF] Loughran | IBM, Public Health Groups Form Global Pandemic Initiative, Goal is to Identify, Map Pandemic Outbreaks and Better Target Vaccines[END_REF]. Technologies offered include a framework to improve communication and collaboration, building a community of users which can tap into information as well as conducting research on influenza viruses. A solution for the former disadvantage may be found in patient centered electronic health records (EHR). EHR offers an overview of important medical data about a patient. The patient decides himself who gets access to his data.

Sensor Media

Sensors record their surroundings on demand, regularly or permanently within a time period. They can determine the position, movement and further attributes of an object at a specific time. They can also detect pressure to find out the weight of an item or detect the movements of a person during the day, categorizing them into different activities [START_REF] Denzler | Das Arzt-Patienten-Verhältnis im digitalen Zeitalter[END_REF]. Sensors can be put together into a network in which they communicate with each other [START_REF] Dargie | Fundamentals of wireless sensor networks: theory and practice[END_REF], [START_REF] Wilson | Human-Computer Interaction Handbook, Fundamentals, Evolving Technologies and Emerging Applications[END_REF]. The combination of networked sensors opens new possibilities and more attributes can be measured. Correlation allows a more precise acquisition of an object's state and it is possible to see the bigger context. In the patient room the combination of sensors in a network can, for example, detect that the patient fell in the wet room at 12:00 p.m. Sensor media record an event but with sensors alone there is no reaction. How does the nurse know a patient has had a fall?

Sensor Deployment in Healthcare

The deployment of sensors in healthcare has five main application areas [START_REF] Rost-Hein | RFID im Gesundheitswesen, Die Anwendungsbereiche[END_REF]: process controlling and documentation, localization, personalized patient medicine and identification, monitoring of measured data and protection against fake medicine.

In process controlling, the sensor technology can facilitate processes and organize them more efficiently based on data collected through sensors. This can optimize product logistics and cost control. Processes concerning documentation can also be simplified, which results in timesaving and reduction of mistakes. Through a better localization of personnel, materials and devices, search time can be reduced and information about the inventory can be provided. One of the most frequent mistakes is the dispensing of the wrong medicine. Insufficient information about the exact kind, amount and time the medicine was administered is one of the causes. A personalized RFID tag can prevent such mistakes, because with this, all information can be allocated to a specific patient. So it can be ensured that the right patient gets the right medicine. The measurement and monitoring of vital signs is relevant for product logistics. The collected data is transferred into an emergency system that raises an alarm when a specific range is exceeded. Protection against counterfeit medicine is an issue whose relevance is increasing constantly. RFID tags enable the definite identification of medicines and permanent, gapless data alignment. This simplifies the distinction between fakes and originals.

Social Media

With social media people can share data, view data and use others' data. Users have the possibility of sharing data publicly or with a predefined specific group of people [START_REF] Luo | An Analysis of Security in Social Networks[END_REF]. Shared data have different levels of quality. They can even be faked to generate a specific impression, for example to compete or to impress. Most social media further provide individual views of specific situations 2 . This means the information about a situation is selected to create specific, person-centered perspectives.

Social media can also be seen as a recorder for time-dependent distributed states [START_REF] Sawyer | Facebook Timeline[END_REF].

The concept of the time line increases the quality of the data on social media because each data item gets an exact timestamp and orders data chronologically.

Social media are also able to acquire data about the relationship between persons, or persons and items, or even items and items, based on specific data which are uploaded by the people themselves [START_REF] Yang | Identifying Implicit Relationships between Social Media Users to Support Social Commerce[END_REF]. The possibility to link data, e.g. by tagging photos with the persons present on them, has proven to be an important tool for relationship management. One of the more recent trends is that people tend to share and comment on data which they find important, rather than uploading data themselves [START_REF] Burkhard | Ich weiß was du letzten Sommer gelesen hast -E-Reader und die Implikationen für den Datenschutz[END_REF].

With social media, the patient could inform the nursing staff that he fell down in the wet room at 12:00 p.m. But how does he do that when he is unconscious?

For further information about an instrument how this could work see https://developers.facebook.com/docs/technical-guides/fql/.

2.5

Social and Sensor Media Fusion

In SoSeMe, data which is collected and joined by sensor media are stored in and distributed by social media. Data is provided by the involved actors/stakeholders who write statements into social media, by the sensor network, and through the hospital information system. The social media set-up plus the attribution of metadata help to contextualize the information, customized for those who access it. This makes the information pick-up much easier and opens a whole new experience in data handling.

In particular, both missing the pick-up of relevant information and giving wrong interpretation to the accessed data become less likely. While the set-up particularly addresses humans, it could equally be employed to steer actuators based on artificial intelligence.

Provided that the patient shared his data with nursing staff and that the patient room is equipped with sensors, the data collected when he fell down in the wet room at 12:00 p.m. can be stored in social media and the nursing staff will be informed and can provide immediate help. The activities in the patient room include people with mixed attributes like patients, visitors and health professionals who communicate with one another and interact with things. There are lots of situations when communication is of critical importance for the health of the patient. The intricacies and problems of this communication are well understood. On the one hand, the need for high quality integration of information is obvious; on the other hand a lot of this information concerns the privacy of patients, which has to be protected. A lot of different kinds of sensors may be placed to observe the room with all its content almost fully, but there is also a lot of social context information being created outside, which also plays a key role.

For a better understanding of the current situation, we have conducted qualitative, semi-structured interviews with the staff in hospitals. Furthermore the processes in a hospital were observed. Those empirical assessments were made according to Pohl [START_REF] Pohl | Requirements Engineering. Fundamentals, Principles, and Techniques[END_REF] in the hospitals Spital Zentrum Biel, Spital Aarberg and Inselspital Bern. Those hospitals were selected to have a comparison between a small hospital which is typically equipped, one that has recent medical equipment as well as infrastructure and a large university hospital. The empirical assessments where focused on the available equipment, available information, nursing and information processes. To evaluate the results, the software MaxQDA 103 was used. Parallel to and based on the empirical assessments we have determined three specific indicative scenarios for investigation (cf. chapter 3.2), for which we then have identified the optative scenarios and the related requirements also according to Pohl. This has yielded ideas about how to conceptually optimize patient rooms in the future, which we explain in chapter 3.3. Then we have built a prototype of a future patient room equipped with a sensor network.

Different prototype implementations were used to find out what is technically possible. Thus another scenario was evaluated. Active sensors were used to identify doctors and nursing staff, patients and medicine. The nurse carried a small device which showed information relevant to the room s/he was in. When the nurse had the wrong medicine for a patient, the device would give a warning. The drawback here is that the prototype reacted really slowly, meaning that the sensor network has to be optimized. This paper does not go deeper into the results generated by the prototype, because they only provide a basis for further project ideas.

Patient Room Today

We looked at the situation of information management in three hospitals in and around Bern, Switzerland. Each had differently equipped patient rooms. However, in all cases there was a paging system, an intravenous pole, an intravenous bag, an infusion set, an Infusomat and a bed.

With the patient paging system the patient can call for a nurse, which simplifies communication between the patient room and the nurses' room. This system consists of a button or a string near the bed, the shower, the toilet and the eating table. When a patient needs help, he pushes the button. Then a lamp turns on beside the door. In the corridor and nurses' room is a display which shows in which room the button was pushed. After entering the room, the nurse turns off the lamp beside the door, so other nurses know that this patient is already being attended to. The nurse can also signal an emergency through this system. Then the door lamp shows the letter N (for 'Notfall', which is German for emergency).

Intravenous bags contain the infusion solution. The name of the infusion and additional information about the content and context (e.g. the nurse's signature) of the bag are written on the bag.

Infusomats 4 are electronic pumps which ensure the supply of liquid drugs during longer periods. Each Infusomat has a controlled hose clip with which an exact dosage for the infusion solution per interval is possible. They show the total amount of infusion solution which has already passed through, how many milliliters per hour should be administered and how many milliliters have already been administered. Some Infusomats have an integrated sensor which counts each drop. When all of the infusion solution has passed through, the device reports the end of the infusion.

Infusions can cause problems like vein inflammation which cannot be detected immediately. Furthermore it is sometimes not possible to determine whether the intravenous catheter is set right into the vein, which could inhibit blood flow.

In several scenarios the bed plays a central part; from here the patient interacts with his environment. As a minimum, the height and the angle of the bedhead are adjustable. In the bed the patient can be transported. In most cases the bed can be extended.

In a patient room there are three main groups of persons: patient, staff and visitors. The patient suffers from illness or the consequences of an accident. He is identified through his name and forename which are written on the bed and the wardrobes. In the researched context, the staff mainly consists of the doctors and nursing staff, which provide services to the patients. They wear a badge on which relevant metadata about their person is written. The doctors prescribe drugs and enter the prescriptions into the hospital information system.

Finally, time management is an important issue. For example there is a schedule for the visits of the chief physician. The use of digital information processing systems is still rather limited. A lot of the information processed only exists in the heads of the staff and is communicated mostly in face-to-face meetings.

Patient Room in the Future

In the following paragraphs the vision of the interviewed persons about the future patient room is summarized and adapted to the main aspects for this case.

The patient room of the future is a smart system and in this case is called smart patient room system (SPRS). It monitors and controls the patient's situation because it has the best access to all relevant information. SPRS is the specific product of SoSeMe for the case patient room.

The patient page system is automated through new technologies. The HIS detects critical situations on the basis of sensor data and sends for a nurse who herself has an individual device which shows her relevant patient data.

The intravenous pole recognizes infusion and drugs. The SPRS compares these with the patient data. If there is a prescription for the correctly identified patient, it starts the administration of the infusion. If any error occurs, the system will warn the nurse about the danger.

The catheter of an infusion could be improved by adding a sensor which can determine if it is properly in the vein or not.

The bed is intelligent, but still easy to use and comfortable. It records the patient's vital signs, body temperature, blood pressure and weight repeatedly and sends the data through a communication channel to social media storage.

Consumables like infusion bags and medicine are equipped with RFID-tags.

Specific Scenario Versions

Throughout the interviews, with nurses working at different hospitals and an M.Sc. class of nurses, we assessed the situation in standard patient rooms and the problems arising because of lack of easily accessible information. Out of the large number of possible scenarios three were selected. The specific scenario 'Infusomat' was selected because it addresses major issues (identifying the patient, dispensing of the wrong medicines) and also includes an actuator, as well as the necessary sensors. The specific scenario 'Vital Signs' was selected because this scenario happens frequently and integration of information flow would improve the work significantly. The specific scenario 'Visitors' was selected to show how people get involved in information diffusion in a patient room. The goal of the selection was to have a minimal set of scenarios that allow all the important benefits and risks to be demonstrated. After the description of today's process of the indicative scenarios, they were optimized as optative scenarios to fit in the future patient room, as shown below. The prototype of the future patient room was then built for optimal support of these scenarios.

Infusomat

A patient is suffering from a chronic lung disease and needs an analgesic. His nurse orders an infusion over the SPRS by voice command through her headset. She arranges the printing of an RFID tag, which she uses to get the analgesic and infusion from the medicine cabinet. She sticks the tag on the infusion bag and adds the analgesic to the infusion. The infusion bag is attached and integrated to the smart infusion booth (SIB), an intravenous pole with built-in electronics. The SPRS reads both SIB and RFID tag, identifies the patient and checks for a match between the data and the prescription. The SPRS gives the order to SIB to adjust. The SIB gives the signal for the infusion. The nurse attaches the infusion to the patient and starts the SIB. After an hour, when the infusion is finished, the SIB sends a signal to the SPRS that the infusion is finished. The SPRS informs the nurse with a voice mail. Then it turns itself off. The nurse removes the infusion.

Vital Signs

During the first four hours after an operation, the patient's vital signs, like blood pressure, temperature, oxygen saturation and wakefulness are determined and added to his electronic health records (EHR) every half an hour. In addition, the nurse asks the patient about nausea, vomiting, pain and the urge to void. The nurse appends the collected data to the EHR with the aid of a mobile device. The data can be accessed by doctors via social media, allowing better treatment if the patient has agreed to share EHR with them.

Visitors

There are two patients in the room. One has company from his wife, the other from a coworker. The SPRS identifies the wife and the coworker by video records. If the visitors wish it, SPRS creates a digital relationship between those two and connects this with various additional data, such as the nature of the relationship between patient and visitor (e.g. the relation between relatives and patients may be stronger than the one between coworkers and patients).

Potential Benefits

The analysis of the three specific versions of the more general patient room scenario have shown different areas where the use of sensor data and the providing of the necessary information in the right form by social media can produce benefits, mainly in the areas of quality and economy. A summary including stakeholders' perspectives is shown below. Note that the stakeholder list is not complete. Other stakeholders outside the patient room which can benefit from SoSeMe include hospitals, the pharmaceutical industry, health insurers, researchers and governments.

Patient and medicine identification improves medicine management

 The system has the possibility to align the medicine and patient data.

Nursing Staff

 Nurses are prevented from making mistakes, because the system warns if someone tries to give the wrong medication.  They can provide the right amount of medicine in a timely manner. Patients  The patients get the correct treatment.

Automated, real-time information exchange around the clock improves communication and data flow

 Information and experiences with specific situations can be exchanged and shared free of barriers and media disruption.  Communication is quick, easy and location-as well as time-independent.  The system supports the nursing stuff to explain the patients' health in an understandable but correct way.  Stakeholder interactions are improved by the exchange of opinions based on data.  There is the possibility of location-and time-independent patient monitoring.

Nursing Staff

 Immediate information access in case of an emergency.  The insight of the patient's relatives can systematically be collected.  They can improve checklists about symptoms, which are relevant for the classification of appropriate therapy. Patients  The patients can participate in the decisions doctors render.

 They get more secure treatments.

 They can move more freely. Relatives  They can seek support from other relatives.

Automatic information acquisition improves stakeholder management

 It is easier to perform analysis based on information about stakeholders. The system allows an easier collaboration.

Nursing Staff

 Staff can be deployed and scheduled more effectively.

 Nurses can organize their nursing services better.

Patients, Relatives

 They get faster and more correct information.

Sensor improve workflow facilitation

 Time-consuming and complex tasks can be facilitated.

Nursing Staff

 Data input through headsets instead of typing.  Nurses can organize their nursing services better. Patients  Record symptoms at moment of event.

Potential Risks

The cooperation of patients is needed for the success of the idea of SoSeMe. However, due to data protection concerns, patients may tend to try to hide things from their doctors [START_REF] Denzler | Das Arzt-Patienten-Verhältnis im digitalen Zeitalter[END_REF] and manipulate sensors on purpose. This strategy may have consequences for the quality of the treatment. Moreover, doctors too may have the impression that their work would be checked more than before and they would have to justify themselves. Because of this feeling, doctors may tend to concentrate on the awareness of third parties rather than their patient's wellbeing.

With the social media in SoSeMe the patient is the data owner and can, as with the EHR, decide who gets access. The idea of SoSeMe depends on the patient's willingness to share his data and also his trust in technology. The amount of information available for the stakeholders increases with the integration of social and sensor media, meaning that analysis of this machine-sourced data could be invalid unless the significance of each piece of information is considered first. This argument is based on the assumption that people weight the information they communicate through speech by variation of pitch level and volume. Also the impression may arise that knowledge about the context is fully available and the importance of a piece of information is weighted differently by different stakeholders. Decisions can be made based on this impression. Furthermore, the nursing staff and doctors have to decide how much they want to know from their patients because of information processing costs and the risk increases with too much information.

Filters and access control may not work reliably or stakeholders abuse their information access. Therefore it is possible that people get access to data which they should not see. Furthermore, should patient data transfer not be encrypted as required by law [START_REF] Bosshard | Rechtliche Grundlagen im medizinischen Alltag, Ein Leitfaden für die Praxis[END_REF], the risk of unauthorized data access and data abuse would increase. The usability of input devices is a further aspect which influences the quality of information in the system and the costs of information processing. As long as information has to be typed in rather than told to somebody, more time is needed or less information can be recorded. On the other hand, audio records cannot be processed optimally by machines. This introduces new areas of error.

Discussion

A future patient room should be as smart as possible so that the patient has more free space and can communicate with fewer barriers. The room should offer the nursing staff facilities within their workflow as well as location-and time-independent communication for patients, staff and visitors.

The combination of social and sensor media can also be used as an emergency system, because it can respond in a timely manner [START_REF] Kuehn | Interoperability and Information Brokers in Public Safety: An Approach toward Seamless Emergency Communications[END_REF]. No matter how promising the integration of sensor data from a patient room into a social network is, it depends on the patient's maturity and sense of responsibility to himself. The interviews we conducted show that the integration of sensor technology can improve workflows. However, the interviewees also made clear that the resulting free capacity would be best used to increase the social interaction between nursing staff and patients and not cost cutting.

The main challenge faced by SoSeMe is data privacy. Interviewees from a technical department declared they would never publish health relevant data. This statement is comforting regarding privacy protection but many people already use online forums or social media to seek help for their illnesses [START_REF] Chun | Social Health Data Integration using Semantic Web[END_REF]. We analyzed the relevant laws in Switzerland. The nursing staff is not allowed to distribute personal data without the permission of the patient5 . They must not give access to third parties without the permission of the patient 6 and it is forbidden even to process the data unless the patient agrees to it first 7 . The patient is the data owner. This means the nursing staff has to be given access to this data and the patient decides who can access that data. With this, the main challenge faced by SoSeMe may be the main benefit, because SoSeMe permits the patients exactly what is stated by the law: an instrument with which they can act as data owner and easily give permission to organizations or persons to access data, process data or deny access altogether. Furthermore, through strict integration of social and sensor media data, privacy in systems can even be improved because violations of data privacy can be tracked.

SoSeMe includes the benefits of the patient's dossier (EHR 8 ) and enriches it. In today's e-health concepts, it is envisioned that patients will take more responsibility for their own dossiers [START_REF] Van Noordende | Security in the Dutch Electronic Patient Record System[END_REF], with hospitals providing added value to their patients by supplying their personal health data in a suitable way. Each patient then has the possibility to share his EHR with whomever, whenever and wherever they want, which includes non-sharing as well. The patient may share data related to their current visit, or if necessary, up to all of their recorded history, as their care requires.

The patient's room situation in a SoSeMe setting is a very complex system. The requirements elicitation on the basis of three rather simple indicative scenarios, defining the indicative information model, and then elaborating the corresponding operative scenarios and the future information model was shown to be a very direct way to define the future system. The applied requirements elicitation techniques in combination with stakeholder interviews proved to be a very effective method. In combination they are appropriate for a discussion on the high abstraction level of potential directions of future systems.

Conclusion and Further Activities

Our research has shown that the integration of digital social media and of sensor networks offers a rich set of options for improving the communication taking place in and around a patient room. At the same time it has revealed significant risks if such an integration is not handled with care. In addition, it may be expected that such experiments would face significant opposition and ethical concerns. Nevertheless the combination of social and sensor media can provide a possible solution to problems arisen in the deployment of a HIS.

Potential benefits include the deployment of SoSeMe within the patient room, which may reduce wrong medication; patients can be monitored in real time and also be treated immediately in case of an emergency. Furthermore, medicine and personnel management can be improved, and workflow facilitated. Participation of patients in decision making can also be supported. Moreover, the idea of time line and collaboration can be a benefit for worldwide research, because with social media it is easier to connect locally independent information. Note that nurses' responsibilities are not being delegated to machines. Machines only act as support.

Since these benefits are so important, we have decided to continue our research and to investigate the specific sub-scenarios described in depth. The patient room can further be equipped with more sensors such as video, audio and wireless sensor systems, which would allow, for example, location and identification of objects. In the patient room this could be used for checking the inventory [START_REF] Neumann | Integration of audiovisual sensors and technologies in a smart room[END_REF], [START_REF] Becker | A wireless sensor network architecture and its application in an assistive environment[END_REF]. To find out what the patient ate a photo can be taken; to find out how much he ate, the food can be weighed. Zooming out of the patient room, in the future we shall look further at the hospital context as a whole or even into larger medical systems, such as the healthcare of a specific region.

Fig. 2

 2 Fig. 2 Interplay between social and sensor media

See also[41].

For further information about this software see http://www.maxqda.de.

Infusomat is a trademark of B. Braun Melsungen AG

Related articles are amongst others SR 101 Art. 13, SR 235.1 Art. 1 and 35

Related article is SR 235.1 Art. 8

Related article is SR 235.1 Art. 17

For further information on a patient dossier in Switzerland see http://www.evita.ch/en/home/.

Acknowledgements

The first thanks go to Emine Seker, Nicola Schwery and Michael Ferreira who provided important content for this project. Further thanks go to Ross Bennie, Alessia Neuroni and Thomas Jarchow, who reviewed this paper.


Peter Koncz
email: peter.koncz@tuke.sk

Ján Paralič
email: jan.paralic@tuke.sk

Active Learning Enhanced Document Annotation for Sentiment Analysis

Keywords: sentiment analysis, active learning, semi-automatic annotation, text mining

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

Introduction

Sentiment analysis, also called opinion mining, is a research area devoted to the methods of automatic quantification of the subjective content expressed in the form of natural language [START_REF] Koncz | An approach to feature selection for sentiment analysis[END_REF]. It aims to detect the presence, orientation or even the intensity of the opinion related to the object of the evaluation or its features/aspects in case of aspect-based sentiment analysis. Within the methods of sentiment analysis, one of the main streams is represented by methods based on using of machine learning algorithms, which deals with the task of sentiment analysis as with a text categorization task. However, these methods are dependent on manually annotated corpora for the training of the classifiers. Moreover these classifiers have been shown domain dependent, i.e. the classifier created for one domain is hardly portable to other domain. Hence, in real application scenario it is usually necessary to build separate corpora for different domains. In order to make the annotation process more effective methods of active learning can be utilized. However active learning is a common strategy used to increase the efficiency of classifiers creation, currently it is a lack of systematical research devoted to its application in the context of sentiment analysis. The need of the integration of active learning to annotation tools for sentiment analysis led us to the comparative evaluation of six active learning strategies. The rest of the work is divided as follows. The second chapter is devoted to related works. In the third chapter the evaluated active learning strategies are described. Consequently the fourth chapter describes their experimental evaluation. Finally, the last part is devoted to conclusions.

Related work

In the last years it was published a huge amount of works devoted to sentiment analysis. Their comprehensive overview can be found in the work of Liu [START_REF] Liu | Sentiment Analysis and Opinion Mining[END_REF]. The methods of sentiment analysis are typically divided into two groups.

The first group is represented by so-called lexicon-based methods. These methods are usually based on sentiment dictionaries and rules for working with them [START_REF] Koncz | Automated creation of corpora for the needs of sentiment analysis[END_REF]. Examples of sentiment dictionaries include the MPQA subjectivity lexicon 1 , used also in our work, Appraisal lexicon2 , National Taiwan University Sentiment Dictionary3 or the SentiWordNet 4 . There are also some works devoted to the possibilities of automation of dictionaries creation, which usually try to utilize the existing structured knowledge resources. Kamps et al. [START_REF] Kamps | Using WordNet to Measure Semantic Orientations of Adjectives[END_REF] described a method for identification of adjectives orientation on the basis of their distance from the words good and bad in a WordNet graph. In the work of Kim and Hovy [START_REF] Kim | Automatic Detection of Opinion Bearing Words and Sentences[END_REF] another solution using WordNet was proposed, based on the extension of the set of emotional words using their synonyms and antonyms. Another solution to populate sentiment dictionaries is to use seed sets of polarity words and extend it by analysis of their coincidences with other words in the corpus of documents as in the work of Turney [START_REF] Pang | Thumbs up?: sentiment classification using machine learning techniques[END_REF]. These dictionaries, as it will be described in the following section, can be utilized in order to compute the sentiment classification uncertainty. Unlike the above mentioned works, the method for generation of sentiment dictionaries used in this work is based only on the annotated corpora of documents.

The second group of sentiment analysis methods is represented by machine learning based or corpus based methods [START_REF] Koncz | Automated creation of corpora for the needs of sentiment analysis[END_REF]. These methods use manually annotated corpora, on the basis of which classifiers are trained for identification of the sentiment. In the frame of this group of methods support vector machines (SVM) [START_REF] Koncz | An approach to feature selection for sentiment analysis[END_REF], [START_REF] Abbasi | Sentiment analysis in multiple languages: Feature selection for opinion classification in Web forums[END_REF][START_REF] Abbasi | Selecting Attributes for Sentiment Classification Using Feature Relation Networks[END_REF][START_REF] Prabowo | Sentiment analysis: A combined approach[END_REF][START_REF] Pang | A sentimental education: sentiment analysis using subjectivity summarization based on minimum cuts[END_REF][START_REF] Xia | Ensemble of feature sets and classification algorithms for sentiment classification[END_REF] and naïve Bayes classifier (NBC) [START_REF] Pang | A sentimental education: sentiment analysis using subjectivity summarization based on minimum cuts[END_REF], [START_REF] Xia | Ensemble of feature sets and classification algorithms for sentiment classification[END_REF] have been widely used. SVM was also shown to be the most advantageous method in the scope of our own works [START_REF] Koncz | An approach to feature selection for sentiment analysis[END_REF], [START_REF] Koncz | Automated creation of corpora for the needs of sentiment analysis[END_REF]. Besides the learning algorithms feature selection methods have been also intensively studied [START_REF] Koncz | An approach to feature selection for sentiment analysis[END_REF], [START_REF] Abbasi | Sentiment analysis in multiple languages: Feature selection for opinion classification in Web forums[END_REF], [START_REF] Abbasi | Selecting Attributes for Sentiment Classification Using Feature Relation Networks[END_REF], where information gain has been shown as one of the most effective methods. One of the main drawbacks of this group of sentiment analysis methods is their dependency on manually annotated corpora. For the robustness of the created solutions it is necessary to take into account the differences between the analyzed texts. Depending on the source as well as other characteristics the particular texts differ in language, size, formality or in the usage of nonlinguistic expression forms like emoticons [START_REF] Petz | On Text Preprocessing for Opinion Mining Outside of Laboratory Environments[END_REF]. Moreover the created classifiers are domain dependent [START_REF] Zhou | Active deep learning method for semi-supervised sentiment classification[END_REF], [START_REF] Dasgupta | Mine the easy, classify the hard: a semi-supervised approach to automatic sentiment classification[END_REF]. In praxis this leads to necessity of separate corpora for particular objects of evaluation, source types or languages. Hence, methods which try to increase the effectiveness of the annotation tools, like active learning, are becoming interesting.

The basic idea of active learning is the selection of unlabeled examples for manual annotation on the basis of their informativeness for the classification task [START_REF] Olsson | A literature survey of active machine learning in the context of natural language processing SE -SICS Technical Report[END_REF]. The particular active learning methods differ in the way how this informativeness is calculated. A comprehensive overview of active learning methods in the context of natural language processing can be found in the work of Olson [START_REF] Olsson | A literature survey of active machine learning in the context of natural language processing SE -SICS Technical Report[END_REF]. Despite the popularity of sentiment analysis in last years, the number of works related to the possibilities of their improvement by utilization of active learning is small. Boiy and Moens [START_REF] Boiy | A machine learning approach to sentiment analysis in multilingual Web texts[END_REF] in their work used three active learning strategies for sentiment analysis of blogs, reviews and forum contributions. The first of them was the classical uncertainty sampling based on the uncertainty of the classification of unlabeled data, which performed similarly as the random strategy. The second strategy was based on relevance sampling which uses examples most likely to be low-represented class members in order to increase the number of examples from class where there are too few examples. The third method was the kernel farthest first which uses examples farthest from the already labeled examples; however this strategy performed worse than the random sampling.

The problem of imbalanced samples is addressed by Li et al. [START_REF] Li | Active learning for imbalanced sentiment classification[END_REF], where an active learning approach for imbalanced sentiment classification tasks was proposed. They used complementary classifiers where the first one was used to get most certain examples from both classes and the second to get most uncertain examples from the minority class for manual annotation, while the classifiers were trained with two disjoint feature subspaces. Dasgupta and Ng [START_REF] Dasgupta | Mine the easy, classify the hard: a semi-supervised approach to automatic sentiment classification[END_REF] used active learning based on SVM where the classifier was trained on automatically labeled unambiguous reviews to identify ambiguous reviews for manual labeling and they confirmed the increase of annotation effectiveness. Zhou et al. [START_REF] Zhou | Active deep learning method for semi-supervised sentiment classification[END_REF] used active learning based on semisupervised learning algorithm called active deep network. The above mentioned works computed the informativeness of examples using the classifiers uncertainty. However, there are some specifics of sentiment analysis which should be considered in the context of active learning. One of them is the possibility to use the above mentioned sentiment dictionaries, which represents an alternative to the informativeness computation methods based on the classifiers uncertainty. Therefore the aim of this work is to verify the possibilities of the use of methods from both mentioned groups of active learning methods considering their applicability in annotation tools.

Active learning strategies for sentiment analysis

On the basis of previous research we selected six active learning strategies applicable in the context of sentiment analysis, which were evaluated in a series of experiments. The first group of methods is represented by methods which use the confidence estimates for particular classes based on results of classification models, which is a common method also for other application domains of active learning. This group is represented by the first three of the bellow mentioned strategies, where the informativeness was computed according to the equation 1. The equation is based on the information entropy using the posterior probability of the positive class ̂(

) and its supplement to one for the negative class for the feature vector of the classified document.

̂( ) ̂( ) ( ̂( )) ( ̂( )) (1)
Active learning strategy based on SVM. This active learning strategy uses the probability estimates of target classes based on SVM, which is well performing method for sentiment analysis and it is commonly used for active learning tasks. In this strategy the model trained on the corpus of annotated documents was used to classify the unlabeled documents. The informativeness of the unlabeled examples is then computed on the basis of difference between the probabilities of target classes. The probability of the positive class for the equation 1 is computed according to the equation 2, where ̂(

) is the posterior probability for the positive class for vector and ( ) is the output of the SVM. The probability of the negative class is computed as its supplement.

̂( ) ( ( ( ))) (2)
The problem of this strategy is the relatively large amount of documents which don't contain any of the words from the model trained on corpus. In this case the computed probability equals for both classes; however these documents are not considered to be the best candidates for annotation. Hence these documents wouldn't be selected for annotation.

Active learning strategy based on Naïve Bayes classifier. Within the methods of machine learning NBC is another commonly used method for sentiment analysis. Also here is the informativeness of the document evaluated on the basis of equation 1. The probability of the positive class is computed on the basis of equation 3.

̂( ) ̂( ) ̂( ) ̂( ) (3)
Active learning strategy based on external model. The above mentioned strategies use classifiers trained on the corpora of annotated documents created during prior iterations. This strategy uses available corpora of annotated documents for sentiment analysis. An example of such a corpus, commonly used for evaluation of sentiment analysis methods, is the movie review corpus from the work of Pang and Lee [START_REF] Pang | A sentimental education: sentiment analysis using subjectivity summarization based on minimum cuts[END_REF], described in more details in the next section. The created model is then used to compute the classification uncertainty as in the previous strategies. The main issue in the utilization of these corpora is the mentioned domain dependency. On the other hand the whole pool of unlabeled documents is evaluated only once.

Active learning strategy based on external dictionaries. This and the following strategies are based on using of dictionaries of positive and negative words. An example sentiment dictionary is the commonly used MPQA Subjectivity Lexicon [START_REF] Wilson | Recognizing Contextual Polarity in Phrase-Level Sentiment Analysis[END_REF], which was used also in this work. From this dictionary we extracted a list of positive and negative words. The number of occurrences of positive words and negative words in each document was used to compute the values of informativeness according to the equation 4. This strategy as well as the following strategies is based on assumption that documents containing words with opposite sentiment are more informative.

(4)

Active learning strategy based on offline generated dictionaries. As it was mentioned in the related works, there are many methods which can be used to get dictionaries of positive and negative words, while the used method does this using the annotated documents. In our case information gain was used, which is a well performing method in feature extraction tasks. Features are in the case of text classification represented by vectors indicating the presence or absence of words or n-grams of words. Information gain was used to get the list of words relevant for sentiment analysis. The orientation of words was extracted as a simple sign of the difference between the number of occurrences of word in positive and negative evaluations. As a source of evaluations we used the corpus from the work of Pang and Lee [START_REF] Pang | A sentimental education: sentiment analysis using subjectivity summarization based on minimum cuts[END_REF]. Thus the sentiment dictionary was created before the active learning, hence the name offline. Active learning strategy based on online generated dictionaries. This strategy is analogous with the previous one, while the difference is in the continuous (online) generation of dictionaries of positive and negative words on the basis of actual corpora of annotated evaluations in each iteration.

Experiments

The aim of the series of experiments was to evaluate the performance of the described active learning strategies in context of their application in annotation tools. For the comparison of evaluated strategies we used the experimental design depicted in Figure 1. At the beginning of the annotation we have a pool of unlabeled documents, from which we select examples for annotation. From this pool are in each iteration selected documents for annotation. The selection of documents is realized on the basis of compared active learning strategies, while in the first iteration the documents are selected randomly. Annotated documents are subsequently added to the corpus. As it will be described in the next chapter, the pool was in reality created by documents with known polarity, but the documents' polarity was not taken into account until adding them to the corpus. This solution was used to simulate the process of the real annotation. The number of documents added in each iteration to the corpus was 20 and in experiments were realized 100 iterations, i.e. the maximal size of corpora was 2000 documents. This corpora were used in each iteration to train the classifiers, which accuracy was evaluated on dedicated test set. The achieved accuracies correspond with the quality of the created corpus and the active learned strategy used to its creation. For the creation of classifiers we used SVM with linear kernel and C equal to 0. In parallel the informativeness of documents in pool was evaluated in case of strategies where this is done in each iteration. These values are then used to select new documents for annotation in the next iteration. The whole process finishes by achieving the required size of corpus. Depending on the strategy sentiment dictionaries and external classifiers should be used. It should be also mentioned that we used binary vector representation of documents and each word was stemmed using the Porter stemmer. Besides the compared active learning strategies we used the baseline strategy, which is a simple random selection of documents from the pool of unlabeled documents.

Samples

For evaluation of possibilities of particular active learning strategies it was necessary to simulate the process of real annotation. Possible resources of evaluations with corresponding numerical evaluation representing the annotation are product review sites.

For this purpose we crawled and parsed reviews from Reviewcenter 5 . From the original set of reviews a total of 17,240 were selected, with half made up by negative reviews (an evaluation from the interval 0 to 1) and half by positive reviews (evaluations equal to 5). The sample was created by random selection of reviews from different fields, with the aim of to create a balanced sample in respect to reviews orientation. From this sample was by stratified random sampling created a test set of evaluations with 1000 documents. The rest of the evaluations were used as a pool of unlabeled documents. The corpora used for training of classifiers were built on the fly by adding new documents in each iteration according to the informativeness of documents evaluated according to active learning strategies. The data sample used for the active learning strategy based on external model and offline generated dictionaries was created from the corpus used by Pang and Lee [START_REF] Pang | A sentimental education: sentiment analysis using subjectivity summarization based on minimum cuts[END_REF]. It is a corpus made up of 1000 positive and 1000 negative reviews of films. This data sample is one of the most commonly used samples for sentiment analysis.

Results

The results achieved by using of particular active learning strategies are depicted in graphs on figures 2 and 3. Axis x represents the sizes of corpora, whereas axis y represents the achieved classification accuracy on the test set. Besides the accuracy values achieved by compared strategies they are depicted also the accuracy values for the baseline strategy as well as the accuracy achieved by using the whole pool of documents for training, which equals 93,6%. The maximal accuracy achieved by the baseline strategy was 74% by using the maximal size of corpus. In Figure 2 are depicted the achieved accuracies for methods using the class probability estimates based on classifiers, i.e. active learning strategies based on SVM, NBC and external model. The best results were achieved by using active learning strategy based on SVM. The maximal achieved accuracy for this strategy was 90,2%. Similar accuracies were achieved also by using the active learning strategy based on NBC. The maximal achieved accuracy for this strategy was 90,3%. For both strategies were the values of accuracy significantly higher in comparison to baseline strategy. In case of active learning based on external model wasn't achieved increase of accuracy. In Figure 3 are depicted the achieved accuracies for methods using sentiment dictionaries, i.e. active learning strategy based on external dictionaries and offline and online generated dictionaries. The best results were achieved by using active learning based on external dictionaries. The maximal achieved accuracy for this strategy was 84,7%. Active learning based on offline generated dictionaries achieved worse results. The maximal achieved accuracy for this strategy was 78,1%. Lowest accuracy was achieved by active learning strategy based on online generated dictionaries. Also in case of these methods were the achieved accuracies better than in case of baseline strategy, however the increase of accuracy for these methods was not so significant. It should be also mentioned that the accuracy increase for these strategies was more significant in first iterations and in some cases the accuracy even decreased after adding new documents.

Conclusions

The achieved results verified the efficiency of active learning methods in process of documents annotation for the needs of sentiment analysis. From the active learning strategies based on classifiers uncertainty active learning based on SVM has been shown as the best performing strategy. One of its advantages is the independency on quality of external resources. Its disadvantage is the necessity of model creation after each iteration. From the active learning strategies based on dictionaries the strategy using an external dictionary achieved the best performance. The advantage of this strategy is in the simplicity of its application. Moreover the dictionaries can be used for highlighting of words in annotated document and improve the efficiency of annotation. From the point of view of the application of these strategies in annotation tools the combination of both types of strategies should be useful, where in the initial phase of annotation the dictionary based methods can be used which will be then replaced by classifiers with uncertainty based methods. In our future work we will design such kind of combined annotation supporting active learning method and adjust it also for the purpose of aspect-based sentiment analysis.

Fig. 1 .

 1 Fig. 1. Experimental design

Fig. 2 .

 2 Fig. 2. Results for methods using classifier uncertainty

Fig. 3 .

 3 Fig. 3. Results for methods using sentiment dictionaries

www.cs.pitt.edu/mpqa

lingcog.iit.edu/arc/appraisal_lexicon_2007b.tar.gz

nlg18.csie.ntu.edu.tw:8080/lwku

sentiwordnet.isti.cnr.it

http://www.reviewcentre.com/

Acknowledgment. This work was partially supported by the Slovak Grant Agency of the Ministry of Education and Academy of Science of the Slovak Republic under grant No. 1/1147/12 and partially by the Slovak Research and Development Agency under the contract No. APVV-0208-10.


Iztok Savnik
email: iztok.savnik@upr.si

Index data structure for fast subset and superset queries

Keywords: subset queries, set containment queries, partial matching, access methods, database index

A new data structure set-trie for storing and retrieving sets is proposed. Efficient manipulation of sets is vital in a number of systems including datamining tools, object-relational database systems, and rule-based expert systems. Data structure set-trie provides efficient algorithms for set containment operations. It allows fast access to subsets and supersets of a given parameter set. The performance of operations is analyzed empirically in a series of experiments on real-world and artificial datasets. The analysis shows that sets can be accessed in O(c * |set|) time where |set| represents the size of parameter set and c is a constant.

Introduction

Set containment queries are common in various systems including datamining tools, object-relational databases, rule-based expert systems, and AI planning systems. Enumeration of subsets of a given universal set U is very common in data mining algorithms [START_REF] Mannila | Levelwise search and borders of theories in knowledge discovery[END_REF] where sets are used as basis for the representation of hypotheses and search space forms a lattice. Often we have to see if a given hypothesis has already been considered by the algorithm. This can be checked by searching the set of hypotheses (sets) that have already been processed. Furthermore, in some cases hypotheses can be easily overthrown if a superset hypothesis has already been shown not valid. Such problems include discovery of association rules, functional dependencies as well as some forms of propositional logic [START_REF] Mannila | Levelwise search and borders of theories in knowledge discovery[END_REF][START_REF] Savnik | Bottom-up Induction of Functional Dependencies from Relations[END_REF][START_REF] Flach | Database dependency discovery: a machine learning approach[END_REF][START_REF] Hoffmann | A New Method to Index and Query Sets[END_REF].

In object-relational database management systems tables can have set-valued attributes i.e. attributes that range over sets. Set containment queries can express either selection or join operation based on set containment condition. Efficient access to relation records based on conditions that involve set operations are vital for fast implementation of such queries [START_REF] Melnik | Adaptive Algorithms for Set Containment Joins[END_REF][START_REF] Terrovitis | A Combination of Trie-trees and Inverted Files for the Indexing of Set-valued Attributes[END_REF][START_REF] Helmer | A performance study of Four Index Structures for Set-Valued Attributes of Low Cardinality[END_REF].

Rule-based expert systems use set containment queries to implement fast patternmatching algorithms that determine which rules are fired in each cycle of expert system execution. Here sets form pre-conditions of rules composed of elementary conditions. Given a set of valid conditions the set of fired rules includes those with pre-condition included in this set [START_REF] Forgy | Rete: A fast algorithm for the many pattern/many object pattern match problem[END_REF][START_REF] Doorenbos | Combining left and right unlinking for matching a large number of learned rules[END_REF].

Finally, in AI planning systems goal sets are used to store goals to be achieved from a given initial state. Planning modules use subset queries in procedure that examines if a given goal set is satisfiable. Part of the procedure represents querying goal sets that were previously shown to be unsatisfiable. Here also sets are used to form basic structure of hypothesis space [START_REF] Blurn | Fast planning through planning graph analysis[END_REF].

In this paper we propose a novel index data structure set-trie that implements efficiently basic two types of set containment queries: subset and superset queries. Set-trie provides storage for sets as well as multisets. Preliminary version of this paper has been published in [START_REF] Savnik | Efficient subset and superset queries[END_REF].

Set-trie is a tree data structure similar to trie [START_REF] Rivest | Partial-Match Retrieval Algorithms[END_REF]. The possibility to extend the performance of usual trie from membership operation to subset and superset operations comes from the fact that we are storing sets (multisets) and not the sequences of symbols as for ordinary tries. In case of sets (multisets) ordering of symbols in a set is not important as it is in the case of text. As it will be presented in the paper, the ordering of set elements is used as the basis for the definition of efficient algorithms for set containment operations. Since the semantics of set containment operations is equivalent to the semantics of multiset containment operations we will in the following text sometimes refer to both, sets and multisets, as sets.

We analyze subset and superset operations in two types of experiments. Firstly, we examine the execution of the operations on real-world data where multisets represent words from the English dictionary. Secondly, we have tested the operations on artificially generated data. In these experiments we tried to see how three main parameters: the size of sets, the size of set-trie tree and the size of test-set, affect the behavior of the operations. Analysis shows that sets can be accessed in O(c * |set|) time where |set| represents the size of parameter set and c is a constant. The constant c is up to 5 for subset case and approximately 150 in average case for the superset case.

The paper is organized as follows. The following section presents the data structure set-trie together with the operations for searching the subsets and supersets in a tree. The Section 3 describes the empirical study of set-trie. We present a series of experiments that measure the behavior of operations and the size of data structure. Related work is presented in Section 4. We give presentation of existent work from the fields of algorithms and data structures, AI systems where sets are used for querying hypotheses and states, and object-relational database systems where indexes are used to access set-valued attributes. Finally, the conclusions and the directions of our further work are given in Section 5.

Data structure set-trie

Set-trie is a tree composed of nodes labeled with indices from 1 to N where N is the size of the alphabet. The root node is labeled with {} and its children can be the nodes labeled from 1 to N . A root node alone represents an empty set. A node labeled i can have children labeled with numbers greater than or equal i. Each node can have a flag denoting the last element in the set. Therefore, a set is represented by a path from the root node to a node with flag set to true. Let us give an example of set-trie. Figure 2 presents a set-trie containing the sets {1, 3}, {1, 3, 5}, {1, 4}, {1, 2, 4}, {2, 4}, {2, 3, 5}. Note that flagged nodes are represented with circles. Since we are dealing with sets for which the ordering of the elements is not important, we can define a syntactical order of symbols by assigning each symbol a unique index. Words are sequences of symbols ordered by indices. The ordering of symbols is exploited for the representation of sets of words as well as in the implementation of the above stated operations.

Set-trie is a tree storing a set of words which are represented by a path from the root of set-trie to a node corresponding to the indices of elements from words. As with tries, prefixes that overlap are represented by a common path from the root to an internal vertex of set-trie tree.

The operations for searching subsets and supersets of a set X in S use the ordering of U . The algorithms do not need to consider the tree branches for which we know they do not lead to results. The search space for a given X and tree representing S can be seen as a subtree determined primarily by the search word X but also with the search tree corresponding to S.

Set containment operations

Let us first give formal definition of the basic subset and superset operations. Let U be a set of ordered symbols. The subsets of U are denoted as words. Given a set of words S and a subset of U named X, we are interested in the following queries.

1) existsSubset(S, X) returns true if ∃Y ∈ S : Y ⊆ X and f alse otherwise.

2) existsSuperset(S, X): returns true if ∃Y ∈ S : X ⊆ Y and f alse otherwise.

3) getAllSubsets(S, X): returns all sets Y such that Y ∈ S ∧ Y ⊆ X. 4) getAllSupersets(S, X): returns all sets Y such that Y ∈ S ∧ X ⊆ Y .

Let us now present a data structure Word for storing sets of symbols. Symbols in words are represented as integer numbers. Elements of a set represented by W ord can be scanned using the following mechanism. The operation word.gotoF irstElement sets the current element of word to the first element of ordered set. Then, the operation word.existsCurrentElement checks if word has the current element set. The operation word.currentElement returns the current element, and the operation word.gotoN extElement goes to the next element in the set.

Using data structure W ord we can now describe the operations of the data structure set-trie. The first operation is insertion. The operation insert(root,word) enters a new word into the set-trie referenced by the root node. The operation is presented by Algorithm 1.

Algorithm 1 insert(node, word) node's flag_last = true; 10: end if Each invocation of operation insert either traverses through the existing tree nodes or creates new nodes to construct a path from the root to the flagged node corresponding to the last element of the ordered set.

The following operation search(node,word) searches for a given word in the tree node. It returns true when it finds all symbols from the word, and false as soon one symbol is not found. The algorithm is shown in Algorithm 2. It traverses the tree node by using the elements of ordered set word to select the children.

Algorithm 2 search(node, word) Let us give a few comments to present the algorithm in more detail. The operation have to be invoked with the call search(root,word.gotoFirstElement) so that root is the root of the set-trie tree and the current element of the word is the first element of word. Each activation of search tries to match the current element of word with the child of node. If the match is not successful it returns f alse otherwise it proceeds with the following element of word.

The operation existsSubset(node,word) checks if there exists a subset of word in the given tree referenced by node. The subset that we search in the tree has fewer elements than word. Therefore, besides that we search for the exact match we can also skip one or more elements in word and find a subset that matches the rest of the elements of word. The operation is presented in Algorithm 3.

Algorithm 3 existsSubset(node,set) Algorithm 3 tries to match elements of word by descending simultaneously in tree and in word. The first IF statement (line 1) checks if a subset of word is found in the tree i.e. the current node of a tree is the last element of subset. The second IF statement (line 4) checks if word has run of the elements. The third IF statement (line 8) verifies if the parallel descend in word and tree is possible. In the positive case, the algorithm calls existsSubset with the next element of word and a child of node corresponding to matched symbol (parallel descend). Finally, if match did not succeed, current element of word is skipped and existsSubset is called with same node and next element of word in line 13.

The operation existsSubset can be easily extended to find all subsets of a given word in a tree node. After finding the subset in line 15 the subset is stored and the search continues in the same manner as before. The experimental results with the operation getAllSubsets(node,word) are presented in the following section.

The operation existsSuperset(node,word) checks if there exists a superset of word in the tree referenced by node. While in operation existsSubset we could skip some el-Algorithm 4 existsSuperset(node, word) end if 13: end for ements from word, here we can do the opposite: the algorithm can skip some elements in supersets represented by node. Therefore, word can be matched with the subset of superset from a tree. The operation is presented in Algorithm 4 Let us present Algorithm 4 in more detail. The first IF statement checks if we are already at the end of word. If so, then the parameter word is covered completely with a superset from tree. Lines 5-6 set the lower and upper bounds of iteration. In each pass we either take current child and call existsSuperset on unchanged word (line 11), or, descend in parallel on both word and tree in the case that we reach the upper bound i.e. the next element in word (line 9).

Again, the operation existsSuperset can be quite easily extended to retrieve all supersets of a given word in a tree node. However, after word (parameter) is matched completely (line 2 in Algorithm 4), there remains a subtree of trailers corresponding to a set of supersets that subsume word. This subtree is rooted in a tree node, let say node k , that corresponds to the last element of word. Therefore, after the node k is matched against the last element of the set in line 2, the complete subtree has to be traversed to find all supersets that go through node k .

Experiments

The performance of the presented operations is analyzed in four experiments. The main parameters of experiments are: number of words in tree, size of the alphabet, and maximal length of words. The parameters are named: numT reeW ord, alphabetSize, and maxSizeW ord, respectively. In every experiment we measure the number of visited nodes necessary for an operation to terminate.

In the first experiment, set-trie is used to store real-world data -it stores multisets obtained from words of English Dictionary. In the following three experiments we use artificial data -datasets include randomly generated sets of sets. In these experiments we analyze in detail the interrelations between one of the stated tree parameters and the number of visited nodes.

In all experiments we observe four operations presented in the previous section: existsSubset (abbr. esb) and its extension getAllSubsets (abbr. gsb), and existsSuperset (abbr. esr) and its extension getAllSupersets (abbr. gsr).

Experiment with real-world data

Let us now present the first experiment in more detail. The number of words in test set is 224,712 which results in a tree with 570,462 nodes. The length of words are between 5 and 24 and the size of the alphabet (alphabetSize) is 25. The test set contains 10,000 words.

Results are presented in Table 1 andFigure Let us give some comments on the results presented in Table 2. First of all, we can see that the superset operations (esr and gsr) visit more nodes than subset operations (esb and gsb).

The number of nodes visited by esr and gsr decreases as the length of words increases. This can be explained by more constrained search in the case of longer words, while it is very easy to find supersets of shorter words and, furthermore, there are a lot of supersets of shorter words in the tree.

Fig. 3. Number of visited nodes

Since operation gsr returns all supersets (of a given set), it always visits more nodes than the operation esr. However, searching for the supersets of longer words almost always results in failure and for this reason the number of visited nodes is the same for both operations.

The number of visited nodes for esb in the case that words have more than 5 symbols is very similar to the length of words. Below this length of words both esb and gsb visit the same number of nodes, because there were no subset words of this length in the tree and both operations visit the same nodes.

The number of visited nodes for gsb linearly increases as the word length increases. We have to visit all the nodes that are actually used for the representation of all subsets of a given parameter set.

Experiments with artificial data

Three experiments were done by using artificially generated data. Experiments are named experiment1, experiment2 and experiment3. 1) In experiment1 we observe relation between maximal length of words to number of visited nodes of set-triein all four operations. 2) experiment2 shows the relation between number of words stored in set-trie and number of visited nodes in set-triein all four operations. 3) experiment3 investigates the relation between the size of alphabet and number of visited nodes of set-triein all four operations.

Let us start with experiment1. Here we observe the influence of maximal length of words to the performance of all four operations. We created four trees with alphabetSize Figure 3 shows the performance of all four operations on all four trees. The performance of superset operations is affected more by the change of word length than the subset operations.

With an even distribution of data in all four trees, esr visits most nodes for input word lengths that are about half of the size of maxSizeW ord (as opposed to dictionary data where it visits most nodes for word lengths approximately one fifth of maxSizeW ord). For word lengths equal to maxSizeW ord the number of visited nodes is roughly the same for all trees, but that number increases slightly as the word length increases.

esb operation visits fewer than 10 nodes most of the time, but for tree3 it goes up to 44. The experiment was repeated multiple (about 10) times, and in every run the operation jumped up in a different tree. As will be seen later in experiment2, it seems that numT reeW ord 50 is just on the edge of the value where esb stays constantly below 10 visited nodes. It is safe to say that the change in maxSizeW ord has no major effect on existsSubSet operation.

In contrast to gsr, gsb visits less nodes for the same input word length in trees with greater maxSizeW ord, but the change is minimal. For example for word length 35 in tree2 (maxSizeW ord 40) gsb visits 7,606 nodes, in tree3 (maxSizeW ord 60) it visits 5,300 nodes and in tree4 (maxSizeW ord 80) it visits 4,126 nodes. Figure 4 shows the number of visited nodes for each operation on four trees: tree1, tree4, tree7 and tree10 (only every third tree is shown to reduce clutter). When in-creasing numT reeW ord the number of visited nodes increases for esr, gsr and gsb operations. esb is least affected by the increased number of words in the tree. In contrast to the other three operations, the number of visited nodes decreases when numT reeW ord increases.

For input word lengths around half the value of maxSizeW ord (between 13 and 17) the number of visited nodes for esr increases with the increase of the number of words in the tree. For input word lengths up to 10, the difference between trees is minimal. After word lengths about 20 the difference in the number of visited nodes between trees starts to decline. Also, trees 7 to 10 have very similar results. It seems that after a certain number of words in the tree the operation remains constant.

The increased number of words in the tree affects the gsr operation mostly in the first quarter of maxSizeW ord. The longer the input word, the lesser the difference between trees. Still, this operation is affected most by the change of numT reeW ord. The average number of visited nodes for all input word lengths in tree1 is 8,907 and in tree10 it is 68,661. Due to the nature of operation, this behavior is expected. The more words there are in the tree, the more supersets can be found for an input word.

As already noted above, when the number of words in the tree increases, number of visited nodes for esb decreases. After a certain number of words, in our case this was around 50,000, the operation terminates with minimal (possible) number of visited nodes for any word length. The increase of numT reeW ord pushes down the performance of operation (from left to right). This can be seen in Figure 4 by comparing tree1 and tree4. In tree1 the operation visits more then 10 after word length 15, and in tree4 it visits more than 10 nodes after word length 23. Overall the number of visited nodes is always low.

The chart of gsb operation looks like a mirrored chart of gsr. The increased number of words in tree has more effect on input word lengths where the operation visits more nodes (longer words). Below word length 15 the difference between trees is in the range of 100 visited nodes. At word length 30 gsb visits 1,729 nodes in tree1 and 8,150 nodes in tree10. Explanation of the increased number of visited nodes is similar as for gsr operation: the longer the word, the more subsets it can have, the more words in the tree, the more words with possible subsets there are.

In experiment3 we are interested about how a change of alphabet size affects the operations. Five trees are created with maxSizeW ord 50 and numT reeW ord 50,000. alphabetSize is 20, 40, 60, 80 and 100, for tree1, tree2, tree3, tree4 and tree5, respectively. The number of nodes in the trees are: 869,373, 1,011,369, 1,069,615, 1,102,827 and 1,118,492. The test set contains 5,000 words.

When increasing alphabetSize the tree becomes sparser-the number of child nodes of a node is larger, but the number of nodes in all five trees is roughly the same. Operation gsr and more notably gsb operation, visit less nodes for the same input word length: the average number of visited nodes decreased when alphabetSize increases. Operation esr on the other hand visits more nodes in trees with larger alphabetSize. Number of visited nodes of esr increases with the increase of alphabetSize. This is because it is harder to find supersets of given words, when the number of symbols that make up words is larger. This is more evident for word lengths below half Operation gsr is not affected much by the change of alphabetSize. More evident change appears when alphabetSize is increased over 20 (tree1). The number of visited nodes in trees 2 to 5 is almost the same, but it does decrease with the increase of alphabetSize.

In tree1 esb visits on average 3 nodes. When we increase alphabetSize the number of visited nodes also increases, but as in gsr the difference between trees 2 to 5 is small.

The change of alphabetSize has more significant effect on longer input words for the gsr operation. The number of visited nodes decreased when alphabetSize increased. Here again the most evident change is when going over alphabetSize 20. In each subsequent increase, the difference in the number of visited nodes is smaller.

Related work

The problem of querying sets of sets appears in various areas of Computer Science. Firstly, the problem has been studied in the form of substring search by Rivest [START_REF] Rivest | Partial-Match Retrieval Algorithms[END_REF], Baeza-Yates [START_REF] Baeza-Yates | Fast text searching for regular expressions or automation searching on tries[END_REF] and Charikar [START_REF] Charikar | New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching and Related Problems[END_REF]. Secondly, the subset queries are studied in various sub-areas of AI for storing and querying: pre-conditions of a large set of rules [START_REF] Forgy | Rete: A fast algorithm for the many pattern/many object pattern match problem[END_REF], states in planning for storing goal sets [START_REF] Hoffmann | A New Method to Index and Query Sets[END_REF] and hypotheses in data mining algorithms [START_REF] Mamoulis | Similarity Search in Sets and Categorical Data Using the Signature Tree[END_REF]. Finally, querying sets is an important problem in object-relational databases management systems where attributes of relations can range over sets [START_REF] Terrovitis | A Combination of Trie-trees and Inverted Files for the Indexing of Set-valued Attributes[END_REF][START_REF] Melnik | Adaptive Algorithms for Set Containment Joins[END_REF][START_REF] Helmer | A performance study of Four Index Structures for Set-Valued Attributes of Low Cardinality[END_REF][START_REF] Tousidou | Signature-based Structures for Objects with Set-valued Attributes[END_REF][START_REF] Zhang | On Supporting Containment Queries in Relational Database Management Systems[END_REF].

Partial-matching and containment query problem

The data structure we propose is similar to trie [START_REF] Rivest | Partial-Match Retrieval Algorithms[END_REF][START_REF] Cormen | Introduction to Algorithms[END_REF]. Since we are not storing sequences but sets we can exploit the fact that the order in sets is not important. Therefore, we can take advantage of this to use syntactical order of elements of sets and obtain additional functionality of tries.

Our problem is similar to searching substrings in strings for which tries and Suffix trees can be used. Firstly, Rivest examines [START_REF] Rivest | Partial-Match Retrieval Algorithms[END_REF] the problem of partial matching with the use of hash functions and trie trees. He presents an algorithm for partial match queries using tries. However, he does not exploit the ordering of indices that can only be done in the case that sets or multisets are stored in tries.

Baeza-Yates and Gonnet present an algorithm [START_REF] Baeza-Yates | Fast text searching for regular expressions or automation searching on tries[END_REF] for searching regular expressions using Patricia trees as the logical model for the index. They simulate a finite automata over a binary Particia tree of words. The result of a regular expression query is a superset or subset of the search parameter.

Finally, Charikar et. al. [START_REF] Charikar | New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching and Related Problems[END_REF] present two algorithms to deal with a subset query problem. The purpose of their algorithms is similar to existsSuperSet operation. They extend their results to a more general problem of orthogonal range searching, and other problems. They propose a solution for "containment query problem" which is similar to our 2. query problem introduced in Section 1.

Querying hypotheses and states in AI systems

The initial implementation of set-trie was in the context of a datamining tool f dep which is used for the induction of functional from relations [START_REF] Savnik | Bottom-up Induction of Functional Dependencies from Relations[END_REF][START_REF] Flach | Database dependency discovery: a machine learning approach[END_REF]. It has been further used in datamining tool mdep for the induction of multivalued dependencies from relations [START_REF] Savnik | Discovery of multivalued dependencies from relations[END_REF]. In both cases sets are used as the basis for the representation of dependencies. Hypotheses (dependencies) are checked against the negative cover of invalid dependencies represented by means of set-trie. Furthermore, positive cover including valid dependencies is minimized by using set-trie as well.

Doorenbos in [START_REF] Doorenbos | Combining left and right unlinking for matching a large number of learned rules[END_REF] proposes an index structure for querying pre-conditions of rules to be matched while selecting the next rule to activate in a rule-based system Rete [START_REF] Forgy | Rete: A fast algorithm for the many pattern/many object pattern match problem[END_REF]. Index structure stores conditions in separate nodes that are linked together to form preconditions of rules. Common conditions of rules are shared among the rules: lists of conditions with common prefix share all nodes that form prefix. Given a set of conditions that are fulfilled all rules that contain as pre-condition a subset of given set of conditions can be activated.

Similar index structure is proposed by Hoffman and Koehler by means of Unlimited Branching Tree (abbr. UBTree) to store set of sets. The main difference with the representation of rules in expert systems is that UBTree does not use variables. Children of node are stored in a list attached to node. A set is in UBTree represented by a path from root to final node; path is labeled by elements of a set. The search procedures for subset and superset problems are similar to those we propose, however, the main difference in procedures is that we explicitly use ordering of sets for search while Hoffman and Koehler give a more general algorithm allowing other heuristic to be exploited. Our publication in 1993 [START_REF] Savnik | Bottom-up Induction of Functional Dependencies from Relations[END_REF] evidently presents the independence of work.

Indexing set-valued attributes of object-relational databases

Sets are among important data modeling constructs in object-relational and objectoriented database systems. Set-valued attributes are used for the representation of properties that range over sets of atomic values or objects. Database community has shown significant interest in indexing structures that can be used as access paths for querying set-valued attributes [START_REF] Terrovitis | A Combination of Trie-trees and Inverted Files for the Indexing of Set-valued Attributes[END_REF][START_REF] Melnik | Adaptive Algorithms for Set Containment Joins[END_REF][START_REF] Helmer | A performance study of Four Index Structures for Set-Valued Attributes of Low Cardinality[END_REF][START_REF] Tousidou | Signature-based Structures for Objects with Set-valued Attributes[END_REF][START_REF] Zhang | On Supporting Containment Queries in Relational Database Management Systems[END_REF].

Set containment queries were studied in the frame of different index structures. Helmer and Moercotte investigated four index structures for querying set-valued attributes of low cardinality [START_REF] Helmer | A performance study of Four Index Structures for Set-Valued Attributes of Low Cardinality[END_REF]. All four index structures are based on conventional techniques: signatures and inverted files. Index structures compared are: sequential signature files, signature trees, extendable signature hashing, and B-tree based implementation of inverted lists. Inverted file index showed best performance over other data structures in most operations.

Zhang et al. [START_REF] Zhang | On Supporting Containment Queries in Relational Database Management Systems[END_REF] investigated two alternatives for the implementation of containment queries: a) separate IR engine based on inverted lists and b) native tables of RDBMS. They have shown that while RDBMS are poorly suited for containment queries they can outperform inverted list engine in some conditions. Furthermore, they have shown that with some modifications RDBMS can support containment queries much more efficiently.

Another approach to the efficient implementation of set containment queries is the use of signature-based structures. Tousidou et al. [START_REF] Tousidou | Signature-based Structures for Objects with Set-valued Attributes[END_REF] combine the advantages of two access paths: linear hashing and tree-structured methods. They show through the empirical analysis that S-tree with linear hash partitioning is efficient data structure for subset and superset queries.

Conclusions

The paper presents a data structure set-trie that can be used for efficient storage and retrieval of subsets or supersets of a given word. The algorithms of set containment operations are analyzed empirically. It has been demonstrated that the algorithms are stable when used on real-world and artificially generated data. Empirical analysis was used to determine the behavior of each particular set containment operations. The performance of set-trie is shown to be efficient enough for storage and retrieval of sets in practical applications.

Initial experiments have been done to investigate if set-trie can be employed for searching substrings and superstrings in texts. For this purpose the data structure settrie has to be augmented with the references to the position of words in text. As in the case of indexes used in information retrieval [START_REF] Manning | An Introduction to Information Retrieval[END_REF] set-trie can be decomposed into dictionary and postings. Empirical analysis which would show memory consumption and efficiency of set-trie used for indexing huge quantities of texts remains to be completed.

Fig. 1 .

 1 Fig. 1. Example of set-trie

Fig. 4 .

 4 Fig. 4. Experiment 1 -increasing maxSizeW ord

Fig. 5 .

 5 Fig. 5. Experiment 2 -increasing numT reeW ord

Fig. 6 .

 6 Fig. 6. Experiment 3 -increasing alphabetSize

  2. Since there are 10,000 words and 23 different word lengths in the test set, approximately 435 input words are of the same length. Table 1 and Figure 2 present the average number of visited nodes for each input word length (except for gsr where values below word length 6 are intentionally cut off).

	word length	esr	gsr esb gsb
	2	523 169694 1	1
	3	3355 103844 3	3
	4	12444 64802 6	6
	5	9390 34595 11 12
	6	11500 22322 14 19
	7	12148 17003 18 32
	8	8791 10405 19 46
	9	6985 7559 19 78
	10	3817 3938 21 102
	11	3179 3201 20 159
	12	2808 2820 20 221
	13	2246 2246 22 290
	14	1651 1654 19 403
	15	1488 1488 18 575
	16	895	895 19 778
	17	908	908 20 925
	18	785	785 18 1137
	19	489	489 22 1519
	20	522	522 19 1758
	21	474	474 19 2393
	22	399	399 17 3044
	23	362	362 17 3592
	24	327	327 19 4167
	Fig. 2. Visited nodes for dictionary words