Concept

Locality sensitive hashing

Publications associées (17)

Randomized low-rank approximation and its applications

In this thesis we will present and analyze randomized algorithms for numerical linear algebra problems. An important theme in this thesis is randomized low-rank approximation. In particular, we will study randomized low-rank approximation of matrix functio ...

EPFL2024

Sketches, metrics and fast algorithms

Navid Nouri

As it has become easier and cheaper to collect big datasets in the last few decades, designing efficient and low-cost algorithms for these datasets has attracted unprecedented attention. However, in most applications, even storing datasets as acquired has ...

EPFL2022

Video Prediction Recalling Long-term Motion Context via Memory Alignment Learning

Hakgu Kim

Our work addresses long-term motion context issues for predicting future frames. To predict the future precisely, it is required to capture which long-term motion context (e.g., walking or running) the input motion (e.g., leg movement) belongs to. The bott ...

IEEE COMPUTER SOC2021

Smaller, Faster & Lighter KNN Graph Constructions

Rachid Guerraoui, Anne-Marie Kermarrec, Olivier Ruas

We propose GoldFinger, a new compact and fast-to-compute binary representation of datasets to approximate Jaccard’s index. We illustrate the effectiveness of GoldFinger on the emblematic big data problem of K-Nearest-Neighbor (KNN) graph construction and s ...

2020

Fingerprinting Big Data: The Case of KNN Graph Construction

Rachid Guerraoui, Anne-Marie Kermarrec, Olivier Ruas

We propose fingerprinting, a new technique that consists in constructing compact, fast-to-compute and privacy-preserving binary representations of datasets. We illustrate the effectiveness of our approach on the emblematic big data problem of K-Nearest-Nei ...

2019

Exploration and Inference in Spatial Extremes Using Empirical Basis Functions

Emeric Rolland Georges Thibaud

Statistical methods for inference on spatial extremes of large datasets are yet to be developed. Motivated by standard dimension reduction techniques used in spatial statistics, we propose an approach based on empirical basis functions to explore and model ...

SPRINGER2019

Improved Credit Bounds for the Credit-Based Shaper in Time-Sensitive Networking

Jean-Yves Le Boudec, Eleni Stai, Ehsan Mohammadpour

In Time-Sensitive Networking (TSN), it is important to formally prove per-flow latency and backlog bounds. To this end, recent works have applied network calculus and obtained latency bounds from service curves. The latency component of such service curves ...

2019

HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces

Akhil Arora, Arnab Bhattacharya, Piyush Kumar

Nearest neighbor searching of large databases in high-dimensional spaces is inherently difficult due to the curse of dimensionality. A flavor of approximation is, therefore, necessary to practically solve the problem of nearest neighbor search. In this pap ...

ASSOC COMPUTING MACHINERY2018

Structure-Preserving Low Multilinear Rank Approximation Of Antisymmetric Tensors

Daniel Kressner

This paper is concerned with low multilinear rank approximations to antisymmetric tensors, that is, multivariate arrays for which the entries change sign when permuting pairs of indices. We show which ranks can be attained by an antisymmetric tensor and di ...

Siam Publications2017

Large Scale Graph Learning from Smooth Signals

Nathanaël Perraudin, Vasilis Kalofolias

Graphs are a prevalent tool in data science, as they model the inherent structure of the data. They have been used successfully in unsupervised and semi-supervised learning. Typically they are constructed either by connecting nearest samples, or by learnin ...

2017