Publications related to Locality-sensitive hashing

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

Riemannian Optimization for Solving High-Dimensional Problems with Low-Rank Tensor Structure

Michael Maximilian Steinlechner

In this thesis, we present a Riemannian framework for the solution of high-dimensional optimization problems with an underlying low-rank tensor structure. Here, the high-dimensionality refers to the size of the search space, while the cost function is scal ...

EPFL2016

Search for Time-Dependent CPT Violation in Hadronic and Semileptonic B Decays

Olivier Schneider, Aurelio Bay, Yiming Li, Remi Léandre Albert Louvot, Chao Wang, Tagir Aushev, Jun Yong Kim, Ji Hyun Kim, Xiao Wang, Jing Li

We report a new sensitive search for C P T violation, which includes improved measurements of the C P T-violating parameter z and the total decay-width difference normalized to the averaged width delta(d) delta(d) of the two B-d mass eigenstates . The resu ...

American Physical Society2012

Distributed Similarity Search in High Dimensions Using Locality Sensitive Hashing

Karl Aberer, Parisa Haghani, Sebastian Michel

In this paper we consider distributed K-Nearest Neighbor (KNN) search and range query processing in high dimensional data. Our approach is based on Locality Sensitive Hashing (LSH) which has proven very efficient in answering KNN queries in centralized set ...

2009

LSH At Large - Distributed KNN Search in High Dimensions

Karl Aberer, Philippe Cudré-Mauroux, Sebastian Michel, Parisa Haghani

We consider K-Nearest Neighbor search for high dimensional data in large-scale structured Peer-to-Peer networks. We present an efficient mapping scheme based on p-stable Locality Sensitive Hashing to assign hash buckets to peers in a Chord-style overlay ne ...

2008

3D Face Recognition using Sparse Spherical Representations

Pascal Frossard, Effrosyni Kokiopoulou, Ivana Tosic, Roser Sala Llonch

This paper addresses the problem of 3D face recognition using spherical sparse representations. We first propose a fully automated registration process that permits to align the 3D face point clouds. These point clouds are then represented as signals on th ...

2008

Hash-and-Sign with Weak Hashing Made Secure

Serge Vaudenay, Sylvain Pasini

Digital signatures are often proven to be secure in the random oracle model while hash functions deviate more and more from this idealization. Liskov proposed to model a weak hash function by a random oracle together with another oracle allowing to break s ...

Springer2007

Similarity Queries on Structured Data in Structured Overlays

Manfred Hauswirth, Roman Schmidt

Structured P2P systems based on distributed hash tables are a popular choice for building large-scaled data management systems. Generally, they only support exact match queries, but data heterogeneities often demand for more complex query types, particular ...

2006