Inverted index | EPFL Graph Search

In computer science, an inverted index (also referred to as a postings list, postings file, or inverted file) is a database index storing a mapping from content, such as words or numbers, to its locations in a table, or in a document or a set of documents (named in contrast to a forward index, which maps from documents to content). The purpose of an inverted index is to allow fast full-text searches, at a cost of increased processing when a document is added to the database. The inverted file may be the database file itself, rather than its index. It is the most popular data structure used in document retrieval systems, used on a large scale for example in search engines. Additionally, several significant general-purpose mainframe-based database management systems have used inverted list architectures, including ADABAS, DATACOM/DB, and Model 204. There are two main variants of inverted indexes: A record-level inverted index (or inverted file index or just inverted file) contains a li

Method of data retrieval, and search engine using such a method

Saket Sathe, Gleb Skobeltsyn

A method of data retrieval from a data repository in response to a query having either list of keywords and/or list of attribute-value pairs, the method comprising the steps of: providing an inverted index generated from the data repository, the inverted index indicating the attribute with which each term is encountered in each entity when such an attribute is available; retrieving data from the inverted index by searching said inverted index based on said attribute-value pairs or keywords; providing scores to entities. A method of forming an inverted index from a data repository and a search engine for retrieval of data from a data repository is also provided.

2011

MEM0R1ES: Memory-based Information Systems

Michele Catasta

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.

EPFL2015

MEM0R1ES: Memory-based Information Systems

Michele Catasta

EPFL2015