Lecture

Data Streams: Algorithms and Applications

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

COM-308: Internet analytics

Internet analytics is the collection, modeling, and analysis of user data in large-scale online services, such as social networking, e-commerce, search, and advertisement. This class explores a number of the key functions of such online services that have ...

Description

This lecture introduces the concept of data streams, focusing on computing statistics with sub-linear memory and estimating quantities efficiently. It covers techniques like counting distinct elements, finding heavy hitters, and approximating count-distinct using algorithms like Flajolet-Martin. The lecture also explores document similarity, discussing shingles, sketches, and sketch comparison methods. Additionally, it delves into distances and nearest-neighbor queries in high-dimensional data, presenting randomized dimension reduction techniques such as the Johnson-Lindenstrauss Lemma and random projection. The instructor provides practical examples and applications, emphasizing the importance of these algorithms in handling 'Big Data' challenges.

Instructor

Matthias Grossglauser

Matthias Grossglauser is a Professor of Computer and Communication Sciences at EPFL in Lausanne, Switzerland, where he co-directs the Information and Network Dynamics lab. His current research interests center on machine learning, stochastic networks, and discrete choice models, and on their applications in artificial intelligence, reinforcement learning, network science, computational social sciences, and recommender systems. He is also a member of the Federal Communications Commission (ComCom), the indepe

Official source

Related concepts (31)

Nonlinear dimensionality reduction

Nonlinear dimensionality reduction, also known as manifold learning, refers to various related techniques that aim to project high-dimensional data onto lower-dimensional latent manifolds, with the goal of either visualizing the data in the low-dimensional space, or learning the mapping (either from the high-dimensional space to the low-dimensional embedding or vice versa) itself. The techniques described below can be understood as generalizations of linear decomposition methods used for dimensionality reduction, such as singular value decomposition and principal component analysis.

Curse of dimensionality

The curse of dimensionality refers to various phenomena that arise when analyzing and organizing data in high-dimensional spaces that do not occur in low-dimensional settings such as the three-dimensional physical space of everyday experience. The expression was coined by Richard E. Bellman when considering problems in dynamic programming. Dimensionally cursed phenomena occur in domains such as numerical analysis, sampling, combinatorics, machine learning, data mining and databases.

Nearest neighbor search

Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function: the less similar the objects, the larger the function values. Formally, the nearest-neighbor (NN) search problem is defined as follows: given a set S of points in a space M and a query point q ∈ M, find the closest point in S to q. Donald Knuth in vol.

K-nearest neighbors algorithm

In statistics, the k-nearest neighbors algorithm (k-NN) is a non-parametric supervised learning method first developed by Evelyn Fix and Joseph Hodges in 1951, and later expanded by Thomas Cover. It is used for classification and regression. In both cases, the input consists of the k closest training examples in a data set. The output depends on whether k-NN is used for classification or regression: In k-NN classification, the output is a class membership.

Approximation algorithm

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time.

Related lectures (64)

Nearest Neighbor Search: Johnson-Lindenstrauss Lemma

Covers the Nearest Neighbor search algorithm and the Johnson-Lindenstrauss lemma for dimensionality reduction, exploring preprocessing techniques and locality-sensitive hashing.

Nearest Neighbor Rules: Part 2

Explores the Nearest Neighbor Rules, k-NN algorithm challenges, Bayes classifier, and k-means algorithm for clustering.

KNN: Nearest Neighbor Classifier

Covers the k-Nearest-Neighbor classifier, hand-written digit recognition, multi-class k-NN, data reduction, applications, graph construction, limitations, and the curse of dimensionality.

Dimensionality Reduction

Introduces artificial neural networks and explores various dimensionality reduction techniques like PCA, LDA, Kernel PCA, and t-SNE.

Textual Data Analysis: Classification & Dimensionality Reduction