PicShark: Mitigating Metadata Scarcity Through Large-Scale P2P Collaboration

Abstract With the commoditization of digital devices, personal information and media sharing is becoming a key application on the pervasive Web. In such a context, data annotation rather than data production is the main bottleneck. Metadata scarcity represents a major obstacle preventing effcient information processing in large and heterogeneous communities. However, social communities also open the door to new possibilities for addressing local metadata scarcity by taking advantage of global collections of resources. We propose to tackle the lack of metadata in large-scale distributed systems through a collaborative process leveraging on both content and metadata. We develop a community-based and self-organizing system called PicShark in which information entropy in terms of missing metadata is gradually alleviated through decentralized instance and schema matching. Our approach focuses on semi- structured metadata and confines computationally expensive operations to the edge of the network, while keeping distributed operations as simple as possible to ensure scalability. PicShark builds on structured Peer-to-Peer networks for distributed look-up operations, but extends the application of self-organization principles to the propagation of metadata and the creation of schema mappings. We demonstrate the practical applicability of our method in an image sharing scenario and provide experimental evidences illustrating the validity of our approach.

Emergent semantics

Philippe Cudré-Mauroux

In the past, the problem of semantic interoperability in information systems was mostly solved by means of centralization, both at a system and at a logical level. This approach has been successful to a certain extent, but offers limited scalability and flexibility. Peer-to-Peer systems as a new brand of system architectures indicate that the principles of decentralization and self-organization might offer new solutions to many problems that scale well to very large numbers of users, or to systems where central authorities do not prevail. Therefore, we suggest a new way of building global agreements, i.e., semantic interoperability, based on decentralized, self-organizing interactions only. In the first part of this thesis, we discuss traditional data integration techniques relying on global schemas, perfect schema mappings and contained query rewritings. We elaborate on the current ecology of the World Wide Web, where autonomous information sources come and go in dynamic and unpredictable ways. In the current environment, data, schemas and schema mappings can all be generated without human intervention and get encoded in syntactic structures with limited expressivity. We argue that traditional top-down integration techniques are inapplicable to that new context and propose a new integration architecture based on decentralized mappings and dynamic self-organization. In the second part of this thesis, we propose a set of principles to foster semantic interoperability in very large scale information systems. We start by introducing new metrics for the schema mappings, based on both syntactic losses (completeness) and semantic mismatch (soundness) to selectively reformulate queries in a decentralized network of heterogeneous parties. We detail analytical methods to evaluate our metrics, and show how to take advantage of those methods to gradually alleviate mapping inconsistencies across the network. We describe a totally decentralized message passing scheme using belief propagation on transitive closures of schema mapping operations to efficiently evaluate the degree of semantic mismatch between pairs of acquainted information systems. Finally, we propose a graph-theoretic analysis of the network of mappings to quantify the quality of the global agreement that can be achieved in that way. The third and last part of this thesis is devoted to the presentation of two systems illustrating the practical applicability of our ideas. The first system we introduce, GridVine, is a Semantic Overlay Network supporting decentralized data integration techniques through pairwise schema mappings and monotonic schema inheritance. GridVine follows the principle of data independence by separating a logical layer, the semantic overlay for managing and mapping data and schemas, from a physical layer consisting of a self-organizing Peer-to-Peer overlay network for efficient routing of messages. The second system, called PicShark, takes advantage of semi-structured metadata to meaningfully share pictures in collaborative settings. PicShark builds on our principles to dynamically create both annotations and mappings, and to gradually minimize information entropy – in terms of missing metadata and schematic heterogeneity – in a self-organizing and decentralized context. Throughout this thesis, we advocate a holistic view on semantics in large-scale information systems: we model semantics as bottom-up and dynamic agreements among heterogeneous parties. We consider both the representation of semantics and the discovery of the interpretation of symbols as the result of a self-organizing process performed by distributed agents whose utility functions depend on the proper interpretation of the symbols. Our view sharply contrasts with previous top-down contributions analyzing data sources in isolation or focusing on global vocabularies and rigid sets of interpretations curated off-line. In a world where digital information is abundant but human attention remains scarce, we believe that autonomous, best-effort processes such as the ones proposed throughout this thesis will play an ever increasing role in complementing traditional top-down integration approaches to handle massive amounts of digitalized and heterogeneous information assets.

EPFL2007

Leveraging User-Generated Content for Information Discovery on the Web

Adriana Budura

The large-scale adoption of the Web 2.0 paradigm has revolutionized the way we interact with the Web today. End-users, so far mainly passive consumers of information are now becoming active information producers, creating, uploading, and commenting on all types of digital content. As a consequence, the Web has evolved from a collection of static HTML pages to a highly interactive system, where information is being published and consumed at high rates. This has tremendously increased the amount of data available on the Web today, which brings about new challenges in terms of information management. At the same time, the increased user participation represents a new and extremely valuable source of data. While interacting with different Web 2.0 portals, users freely provide all types of information, such as annotations describing the shared resources, friendship links connecting similar users, etc., which can be exploited in order to improve the methods designed to manage online content. A particularly interesting example of user-generated data are the so-called social annotations, that users attach to resources in the context of collaborative tagging systems. This kind of meta-information opens up new opportunities for improved content search, new means to organize personal data, and ways of mining user profiles based on their annotations. Virtual friendship connections between users, as we can observe in social networks, are another rich source of information as they often group users with similar interests together, give means to study information diffusion and open ground to enhanced expert finding tasks. In this thesis, we leverage information extracted from user-generated data, in order to solve current information management problems, such as data retrieval, mining and integration. We explore different scenarios, where online content is enriched with user-defined meta-information and we identify specific problems, which we solve by leveraging this information. We start by addressing the problem of context-based information discovery in collaborative tagging systems, where we take advantage of user-defined entity graphs – such as a citation graph of publications or a friendship graph of users. In this setting, effective search solutions require a certain amount of annotations, however, content is often poorly annotated. We therefore propose a method that exploits the context-related information embedded in the graph structure, in order to automatically infer new annotations. Our approach propagates tags along the edges of the graph, based on the assumption that the neighborhood of a resource holds additional information about the resource itself. We see a similar graph structure in social communities, where users are connected via friendship links and where the neighborhood of a user reflects her community of interest. We adopt the hypothesis that users mainly annotate resources of interest to them and interpret the annotations (i.e., tags) as an interest profile. Hence, we propose a novel framework for tag-based community detection in collaborative tagging systems, that considers both the tagging behavior of users, as well as their friendship graph. Based on a set of tags, our method returns a closely connected community of users, whose tags jointly cover the initial set. In order to further investigate the issue of generating user profiles based on their annotations, we switch our attention from the open Web to an enterprise setting. Social software, such as collaborative tagging systems, has also been included in the enterprise space, where it opens up new opportunities to address the problem of expert search. We take advantage of the data extracted from two enterprise-internal portals and explore correlations between the users‚ tagging behavior and their corresponding areas of expertise. Based on these correlations, we devise a method that derives expertise profiles for users. Finally, we investigate how user-generated meta-information can be exploited in the domain of structured data on the Web, i.e., data that is organized according to the relational model and complies to application-specific schemas. In order to enable transparent search solutions on such data, schema heterogeneity needs to be overcome by means of data integration techniques. We explore how such techniques can benefit from the user-generated meta-information in the form of links between similar entries in different databases. Based on these links, we devise a method to create mappings between the elements of different schemas from a real-world collection of online bioinformatic databases.

EPFL2010

Emergent semantics

Philippe Cudré-Mauroux

EPFL2007

Leveraging User-Generated Content for Information Discovery on the Web

Adriana Budura

EPFL2010