MEM0R1ES: Memory-based Information Systems

The advent of the Web reshaped the way in which humans memorize information, arguably unlike any other technological advance of the last decades. Rather than remembering the information itself, people are primed to find the needed information through Web search engines. At the light of this result, psychologists are starting to reconsider the standard framework for which memory is the process by which information is encoded, stored, and retrieved. Content that can be easily retrieved from the Web is encoded to enhance the recall for where to access it; therefore it is only partially stored. As a matter of fact, Internet users are exposed daily to a staggering amount of personal information, especially since Online Social Networks started to play a key role in their lives (i.e., smartphone users spend 20% of their time on the Facebook app). While a great deal of effort has been spent in recommending relevant content to the user (e.g., targeted advertisements, similar news, etc.), there are no comprehensive studies on how much of this information is memorized by the user. In this thesis, we will show the feasibility of memory-based information systems, namely, systems that take into account the idiosyncrasies of human memories. Departing from classical integrated infrastructures providing static views over heterogeneous sources (e.g., through a wrapper-mediator infrastructure or inverted indices), we propose to mimic the way our brain stores and accesses information in order to provide a more natural extension of our cognitive functions when it comes to tap into the chaotic piles of digital information that we generate daily. Building an information system that mimics the way our brain stores and accesses data would dramatically reduce the cognitive burden of the user interactions, while at the same time returning more relevant information. This thesis is divided in two parts. In the first part, we present our effort in redefining 3 fundamental information systems, taking into account the way in which human memories work. Namely, we rethought a search architecture over personal data, we devised a new crowdsourcing paradigm (leveraging the Transactive Memory paradigm), and we envisioned a novel Database Management System. In the second part, we introduce our long-term efforts to gain insights on the human memories in a non-invasive way, by developing appealing software applications that could reach thousands of users. Such work-in-progress has a fundamental importance when it comes to design novel information systems (as we did in the first part of this thesis), because it allows us to rank the information based on its memorability. In what is currently called the ``information era'', showing only what is memorable to the user could become the key feature to tame the deluge of data we are exposed to daily.

Sharing of probabilistically correlated data in peer-to-peer networks

Roman Schmidt

The impact of Peer-to-Peer (P2P) networks on the Internet landscape is undisputed. It has led to a series of new applications, e.g., as part of the so-called Web 2.0. The shift from the classical client-server based paradigm of the Internet, with a clear distinction between information providers and consumers, towards consumers sharing information among each other led to the rise of the P2P paradigm. The distributed setting enables users to share their content autonomously and locally, i.e, information remains at computers at the edge of the Internet and is not gathered and organized at central servers. Structured overlay networks were designed to organize the huge quantity of data shared in P2P networks by building a global, though distributed, index of shared information. Whereas the initial aim of these systems was to provide efficient lookup operations for single keyword operations, the need for more complex operations emerged very quickly. Peer Data Management Systems (PDMS) is one such example of application that enables data integration and complex query processing similar to (distributed) database systems on top of structured overlays. Complex query operators usually require joint access to multiple data entries whereas single key lookups usually only affect a single data entry. The partitioning of the distributed index of standard structured overlays is optimized towards single key lookups and joint data access as required by PDMS was neglected so far. (Distributed) databases have already shown that (index-)data organization supporting correlated data access is necessary and crucial for efficient processing, as network usage is minimized. We aim at applying this insight to structured overlays by clustering correlated data frequently accessed jointly by applications, including PDMS but also other types of applications. Data correlations can be derived from different sources, data properties, processing properties, users and applications. We study and present solutions for three different types of correlations in the context of different applications: (i) range queries where exploiting the order relationship of data is a fundamental basis for any database-like system; (ii) distributed probabilistic inference where exploiting user-defined complex data correlations gains importance through the Web 2.0; (iii) multi-term queries where exploiting data correlations derived from data access statistics enables simple but powerful keyword search to users. Our approach exploits properties of structured overlays, such as order-preserving hashing, to realize efficient range query processing. We further introduce a distributed clustering algorithm based on the spring relaxation technique to cluster strongly correlated data entries at one node respectively in its proximity. Joint data access is thus performed on a single or few nodes to reduce network bandwidth consumption and therefore to increase system performance. Our approaches are realized on top of the structured overlay network P-Grid although they are generic enough to be applied to other P2P networks with similar properties. This thesis presents details about the Java implementation of P-Grid, its architectural design and its evaluation on PlanetLab, today's standard testbed for P2P systems. The implementation of P-Grid in a Java application finally enabled us to build a PDMS system on top relying on P-Grid's efficient query processing. We present the UniStore system, a distributed data management system aiming at public data management and support for database-like query operators on heterogeneous data, and its evaluation on PlanetLab.

EPFL2008

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

Learning Explainable User Sentiment and Preferences for Information Filtering

Nikolaos Pappas

In the last decade, online social networks have enabled people to interact in many ways with each other and with content. The digital traces of such actions reveal people's preferences towards online content such as news or products. These traces often result from interactions such as sharing or liking, but also from interactions in natural language. The continuous growth of the amount of content and of digital traces has led to information overload: surrounded by large volumes of information, people are facing difficulties when searching for information relevant to their interests. To improve user experience, information systems must be able to assist users in achieving their search goals, effectively and efficiently. This thesis is concerned with two important challenges that information systems need to address in order to significantly improve search experience and overcome information overload. First, these systems need to model accurately the variety of user traces, and second, they need to meaningfully explain search results and recommendations to users. To address these challenges, this thesis proposes novel methods based on machine learning to model user sentiment and preferences for information filtering systems, which are effective, scalable, and easily interpretable by humans. We focus on two prominent types of user traces in social networks: on the one hand, user comments accompanied by unary preferences such as likes, and on the other hand, user reviews accompanied by numerical preferences such as star ratings. In both cases, we advocate that by better understanding user text through mining its semantics and modeling its structure, we can not only improve information filtering, but also explain predictions to users. Within this context, we aim to answer three main research questions, namely: (i)~how do item semantics help to predict unary preferences; (ii)~how do sentiments of free-form user texts help to predict unary preferences; and (iii)~how to model fine-grained numerical preferences from user review texts. Our goal is to model and extract from user text the knowledge required to answer these questions, and to obtain insights on how to design better information filtering systems that are more effective and improve user experience. To answer the first question, we formulate the recommendation problem based on unary preferences as a top-N retrieval task and we define an appropriate dataset and metrics for measuring performance. Then, we propose and evaluate several content-based methods based on semantic similarities under presence or absence of preferences. To answer the second question, we propose a sentiment-aware neighborhood model which integrates the sentiment of user comments with unary preferences, either through fixed or through learned mapping functions. For the latter type, we propose a learning algorithm which adapts the sentiment of user comments to unary preferences at collective or individual levels. To answer the third question, we cast the problem of modeling user attitude toward aspects of items as a weakly supervised problem, and we propose a weighted multiple-instance learning method for solving it. Lastly, we show that the learned saliency weights, apart from being easily interpretable, are useful indicators for review segmentation and summarization.

EPFL2016