Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Link Indexing

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 concept of link indexing, focusing on adjacency lists, properties like locality and similarity, and techniques to exploit them. It discusses gap encoding, varying length encoding, copying data from similar lists, and representing adjacency lists efficiently. The instructor also presents challenges in representing URLs in a web graph and ways to optimize main memory storage.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

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

Related concepts (17)

Adjacency list

In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs. An adjacency list representation for a graph associates each vertex in the graph with the collection of its neighbouring vertices or edges.

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.

Computer data storage

Computer data storage is a technology consisting of computer components and recording media that are used to retain digital data. It is a core function and fundamental component of computers. The central processing unit (CPU) of a computer is what manipulates data by performing computations. In practice, almost all computers use a storage hierarchy, which puts fast but expensive and small storage options close to the CPU and slower but less expensive and larger options further away.

Magnetic-core memory

Magnetic-core memory was the predominant form of random-access computer memory for 20 years between about 1955 and 1975. Such memory is often just called core memory, or, informally, core. Core memory uses toroids (rings) of a hard magnetic material (usually a semi-hard ferrite) as transformer cores, where each wire threaded through the core serves as a transformer winding. Two or more wires pass through each core. Magnetic hysteresis allows each of the cores to "remember", or store a state.

Related lectures (30)

Virtual Memory

Covers virtual memory, program relocation, memory protection, TLB, and memory hierarchy interactions.

Memory Cache Principles

Explores memory cache principles, emphasizing spatial locality, latency impact, and cache efficiency strategies.

Graphs: Properties and Representations

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

Link-based ranking: PageRank & HITS

Explores link-based ranking through PageRank and HITS algorithms, covering practical examples and challenges in web search and ranking methods.

Optimal Binary Search Tree