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

Lecture

Data Streams: Algorithms and Applications

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.

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

Matthias Grossglauser

Official source

Related concepts (26)

Dimensionality reduction

Dimensionality reduction, or dimension reduction, is the transformation of data from a high-dimensional space into a low-dimensional space so that the low-dimensional representation retains some meaningful properties of the original data, ideally close to its intrinsic dimension. Working in high-dimensional spaces can be undesirable for many reasons; raw data are often sparse as a consequence of the curse of dimensionality, and analyzing the data is usually computationally intractable (hard to control or deal with).

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.

Related lectures (33)

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.

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.

Textual Data Analysis: Classification & Dimensionality Reduction

Explores textual data classification, focusing on methods like Naive Bayes and dimensionality reduction techniques like Principal Component Analysis.

Clustering: Unsupervised Learning

Explores dimensionality reduction, clustering algorithms, and the state of machine learning.

K-Nearest Neighbors & Feature Expansion