Lecture

Information Retrieval: Indexing and Retrieval

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

CS-423: Distributed information systems

This course introduces the foundations of information retrieval, data mining and knowledge bases, which constitute the foundations of today's Web-based distributed information systems. ...

Description

This lecture covers the fundamental concepts of information retrieval, focusing on indexing techniques such as inverted files and their physical organization. It also delves into the process of distributed retrieval, discussing algorithms like Fagin's Algorithm and the Threshold Algorithm. The importance of exploiting locality and similarity in adjacency lists is highlighted, along with practical examples of finding top elements for given queries. Additionally, the lecture explores the challenges of scalability and efficiency in large-scale web indexing, emphasizing the need for optimized data structures and algorithms.

Instructor

Karl Aberer

Karl Aberer received his PhD in mathematics in 1991 from the ETH Zürich. From 1991 to 1992 he was postdoctoral fellow at the International Computer Science Institute (ICSI) at the University of California, Berkeley. In 1992, he joined the Integrated Publication and Information Systems institute (IPSI) of GMD in Germany, where he was leading the research division Open Adaptive Information Management Systems. In 2000 he joined EPFL as full professor. Since 2005 he is the director of the Swiss National Research Center for Mobile Information and Communication Systems ( NCCR-MICS, www.mics.ch ). He is member of the editorial boards of VLDB Journal, ACM Transaction on Autonomous and Adaptive Systems and World Wide Web Journal. He has been consulting for the Swiss government in research and science policy as a member of the Swiss Research and Technology Council ( SWTR ) from 2003 - 2011.

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (32)

Search engine indexing

Search engine indexing is the collecting, parsing, and storing of data to facilitate fast and accurate information retrieval. Index design incorporates interdisciplinary concepts from linguistics, cognitive psychology, mathematics, informatics, and computer science. An alternate name for the process, in the context of search engines designed to find web pages on the Internet, is web indexing. Popular search engines focus on the full-text indexing of online, natural language documents.

Adjacency matrix

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal. If the graph is undirected (i.e. all of its edges are bidirectional), the adjacency matrix is symmetric. The relationship between a graph and the eigenvalues and eigenvectors of its adjacency matrix is studied in spectral graph theory.

Graph (abstract data type)

In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within mathematics. A graph data structure consists of a finite (and possibly mutable) set of vertices (also called nodes or points), together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges (also called links or lines), and for a directed graph are also known as edges but also sometimes arrows or arcs.

Web indexing

Web indexing, or internet indexing, comprises methods for indexing the contents of a website or of the Internet as a whole. Individual websites or intranets may use a back-of-the-book index, while search engines usually use keywords and metadata to provide a more useful vocabulary for Internet or onsite searching. With the increase in the number of periodicals that have articles online, web indexing is also becoming important for periodical websites. Back-of-the-book-style web indexes may be called "web site A-Z indexes".

Information retrieval

Information retrieval (IR) in computing and information science is the process of obtaining information system resources that are relevant to an information need from a collection of those resources. Searches can be based on full-text or other content-based indexing. Information retrieval is the science of searching for information in a document, searching for documents themselves, and also searching for the metadata that describes data, and for databases of texts, images or sounds.

Related lectures (64)

Indexing and Distributed Retrieval

Explores indexing techniques, inverted files, map-reduce algorithms, and top-k document retrieval methods in text retrieval systems.

Graphs: Properties and Representations

Covers graph properties, representations, and traversal algorithms using BFS and DFS.

Algorithms in Computer Science: Search and Sort Techniques

Provides an overview of essential search and sort algorithms in computer science.

Information Retrieval Indexing: Part 2

Explores constructing an inverted file for information retrieval indexing and the map-reduce programming model.

Matrix Multiplication and Heaps: Efficient Algorithms