Community-based collaborative information systems provide the exibility of storing information without having to adhere to any prede ned, rigid schema. However, the stored knowledge lacks common structure, which is crucial in terms of data access and search capability. We present a novel concept for semistructured information systems, which features a dynamic and self-learning schema system and provides the users with recommendations when entering information. The recommendations ensure the creation and maintenance of a common, homogeneous schema while at the same time not restricting the user's exibility to enter any kind of information.
When storing information, there are two common ways of doing so: either one uses a (relational) database to store information in a structured way or one stores information in a mostly unstructured manner.
The rst approach is very well suited for applications which have to store strictly structured information. Considering the example of bank accounts, all information is structured and can easily be matched into a schema for the storage of e.g. bank accounts and their owners. A big disadvantage is that a change within the schema can be very time-consuming and complex, as it has to be done manually and the already stored information has to be adapted to the new structure. Therefore, the end-user is xed to a given schema and cannot insert additional information not matching the given schema. For exible information systems, such a restricting approach is not very well suited, as it can result in a big loss of information because of the fact that the user cannot insert all information he might want to.
On the other hand, the second, unstructured way of storage
allows the user to store information in any arbitrary
structure or format. This approach has the advantage that the
user does not have to match the data into some prede ned
schema. A popular example of such exible systems are wiki
systems, where information can simply be added as text.
However, such structureless storage prevents every
possibility to provide structured access or search facilities on the
stored information, as for example relational databases do.
Consider the example of Wikipedia, which does not provide
structured search capabilities at all. The only way to search
through this unstructured information is to perform fulltext
search, which is incapable of answering precise queries like
\Which Austrian cities have between 10,000 and 20,000
inhabitants?". For this reason information repositories need
to support both structured and unstructured information to
fully exploit the advantages of both worlds, as also pointed
out by Weikum et al. [
The rest of the paper is organized as follows. In Section 2 the basic concept of our approach is described. Section 3 outlines the measures taken for the creation of a common schema. Our proposed solution is described in Section 4 and related work is outlined in Section 5. Section 6 summarizes the paper and points out open research issues.
The Snoopy concept o ers the same exibility as wiki systems but at the same time provides the possibility to structure information like (relational) databases. This is achieved by using a self-adapting and self-learning schema system and recommendations, which support the user during the insertion process.
In the Snoopy concept, information about a certain subject is stored as a collection, similar to a wiki page. A collection consists of an arbitrary number of key-value pairs, which can be speci ed by the user without any restrictions. The following example shows how information about the city \Innsbruck" can be stored in a simple and understandable way:
The key-value pairs are similar to relational database columns
(keys) and its rows (values). Despite the fact that
information is still plain text, it still features structure. Such
semistructured data, where structure is present but does
not comply to a uni ed schema, can be used for structured
access (e.g. queries like \All entries containing the
property Country:Austria"). One of the main challenges of such
semistructured data is the proliferation of keys and values.
Furnas et. al. [
The Snoopy concept takes a di erent approach and pushes part of these structural adaptions to the user. The user knows more about the collection he enters than any process, machine or community, which try to enhance the information after the author inserted it. Therefore, the key idea of the Snoopy concept is to \snoop\ as much information as possible from the user during the insertion process. Furthermore, the user is guided by an adapting, self-learning guidance engine which provides recommendations to the user based on key-value pairs entered earlier. These recommendations support the user in aligning the information he intends to enter to a commonly used schema.
It is important to note that all these recommendations are just suggestions and the user is not forced to use these recommendations in any way. Therefore, the user is able to enter information without any restrictions.
The process of integrating and transforming two or more
(database) schemata into a common schema has proven to
be a very complex task [
The self-adapting schema is implicit and dynamically calculated based on already stored information. It consists of keys which are used together by the majority of similar collections. Hence, newly entered information can in uence the schema and can result in a change of the schema. For example adding the key \numberOfStudents" to many collections about cities can lead to a recommendation of this key to further users.
As information systems contain information of various structures and types, the Snoopy concept automatically computes a suitable number of schemata according to the stored information - without any prede ned settings. Schema alignment in the case of the Snoopy concept can be achieved by taking the following measures, which are all based on recommendations of values and keys.
The suggestion of keys and structure is the most important feature within the Snoopy concept. Considering a user entering information about cities (consisting of key-value pairs) into the system, there might be additional useful keys that the user might not think of at rst hand. This is where the recommendation engine comes into play. If a user wants to add the key "inhabitants", the system computes that 90 percent of the users who added \inhabitants" as a key, also added \mayor". The recommendation feature is based on a data mining process within the already existing collections, which calculates keys that frequently occur together. Having done these computations, the system suggests this additional key to the user who can then accept this key and enter a respective value. Assume, the user wants to store information about the city \Innsbruck". Based on the already inserted keys \country", \state" and \numberOfInhabitants", the system recommends adding the keys \mayor" and \ZIP". Recommendations are simply further form elds displayed to the user that give him the opportunity to enter appropriate values for the suggested keys. The recommendations encourage the user to insert more information than originally intended and thereby increase the amount of information in the system.
When entering new key-value pairs, the user gets assistance by an auto-completion system. This feature suggests keys that are already stored in the information system, are similarly structured and therefore semantically related to the currently entered key. If the user types e.g. \number", the system automatically provides the user with the possibility to choose \number of inhabitants" or \number of districts", which are keys that are already existent in the database. The user still has the opportunity to provide a new key, e.g. \number of universities" by ignoring the recommendations and continue typing. This recommendation contributes to the creation of a common schema and data basis and is demonstrated by the following example. If the user wants to enter the key \inhabitants", after typing \inhab", the user is informed that a similar key \number of inhabitants" is already present. As accepting the recommendation is faster than typing the word \inhabitants", the user is encouraged to accept the recommendation.
Our proposed solution is mostly concerned with the computation of recommendations and the underlying storage mechanisms, which are explained in the following section.
The computation of the recommendations can be achieved
by using association rules [
This is the basis of the calculation of recommendation candidates, which are then further examined in order to provide the best possible recommendations to the user. Based on this (probably large) set of association rules, the nal recommendations are computed taking the following impact factors into acount: (i) support of a rule, (ii) novelty of properties, (iii) recent popularity rise of properties and (iv) some random choice to give new properties a chance to be used and therefore rise in popularity.
Fundamentally, the computation process of the recommendations has to ful ll the following requirements: (i) ability to cope with huge amounts of data, (ii) compute recommendation candidates based on mining association rules, (iii) evaluation of the candidate sets according to the previously mentioned factors and (iv) real-time calculation of recommendations.
The underlying storage system is a crucial part of the
application as it holds all Snoopy data. Basically, the main task
is to store many key-value pairs belonging to a certain
subject (collection). This pattern suggests storing this data as
triples using the W3C Resource Description Framework [
Basically, the underlying RDF storage system has to ful ll the following requirements in order to ensure a scalable, efcient and highly performant system: (i) SPARQL support to query all stored data in a fast and e cient way, (ii) optimized RDF store: triples have to be stored in the most e cient and compact way as the representation of knowledge as triples leads to a very large number of triples, (iii) an interface optimized for data mining tasks, as SPAQRL is not best suited for data mining (iv) fast data mining: mining structure and content within the triples is the most time-critical part of the application as all recommendations are based on it.
SnoopyDB, a rst prototype of the Snoopy concept has
already been developed and evaluated in [
The Snoopy concept can bene t from many research areas which cover parts of the Snoopy concept. Lots of research is done on how to introduce structure in Wikipedia or generally in information systems. All of the following approaches try to enhance information after the insertion process, do not consult the user and do not bene t from the user's extensive knowledge during the insertion process.
The DBPedia project [
We presented the Snoopy-concept, a novel approach for creating and maintaining a common schema in semistructured information systems by using recommendations. These recommendations guide the user during the insertion process in order to align the information to a commonly used schema and vocabulary. The implicit schema is based on all stored information in the system and adapts itself to the structure of this data. The recommendations are based on association rules and were implemented in a prototype. First results showed that recommendations ensure homogeneous schemata and vocabulary in a multi-user semistructured information system and therefore improve the structured data access capabilities. Further work will include ranking of rules enabling the system to compute top-n recommendations aiming at a higher precision of recommendations. Furthermore, capabilities to query the stored information e ciently have to be introduced and the storage mechanisms have to be improved.