18 citations · 70 across the 15 of their papers we have counts for
18 papers
Poisoning Attacks on the PGM-index
Atsuki Sato, Martin Aumüller, Yusuke Matsui
The PGM-index (Ferragina and Vinciguerra, VLDB'20) is one of the most practical learned indexes, owing to its theoretical elegance and consistently strong empirical performance. It…
VIBE: Vector Index Benchmark for Embeddings
Elias Jääsaari, Ville Hyvönen, Matteo Ceccarello +2
Approximate nearest neighbor (ANN) search is a performance-critical component of many machine learning pipelines, and rigorous benchmarking is essential for assessing the performan…
Differentially Private High-Dimensional Approximate Range Counting, Revisited
Martin Aumüller, Fabrizio Boninsegna, Francesco Silvestri
Locality Sensitive Filters are known for offering a quasi-linear space data structure with rigorous guarantees for the Approximate Near Neighbor search (ANN) problem. Building on L…
Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search
Harsha Vardhan Simhadri, George Williams, Martin Aumüller +9
Despite the broad range of algorithms for Approximate Nearest Neighbor Search, most empirical evaluations of algorithms have focused on smaller datasets, typically of 1 million poi…
Differentially Private Sketches for Jaccard Similarity Estimation
Martin Aumüller, Anders Bourgeat, Jana Schmurr
This paper describes two locally-differential private algorithms for releasing user vectors such that the Jaccard similarity between these vectors can be efficiently estimated. The…
The Role of Local Intrinsic Dimensionality in Benchmarking Nearest Neighbor Search
Martin Aumüller, Matteo Ceccarello
This paper reconsiders common benchmarking approaches to nearest neighbor search. It is shown that the concept of local intrinsic dimensionality (LID) allows to choose query sets o…
PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors
Martin Aumüller, Tobias Christiani, Rasmus Pagh +1
We present PUFFINN, a parameterless LSH-based index for solving the -nearest neighbor problem with probabilistic guarantees. By parameterless we mean that the user is only requi…
Fair Near Neighbor Search: Independent Range Sampling in High Dimensions
Martin Aumüller, Rasmus Pagh, Francesco Silvestri
Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. There are several variants of the similarity search problem, and one of…
Simple and Fast BlockQuicksort using Lomuto's Partitioning Scheme
Martin Aumüller, Nikolaj Hass
This paper presents simple variants of the BlockQuicksort algorithm described by Edelkamp and Weiss (ESA 2016). The simplification is achieved by using Lomuto's partitioning scheme…
ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms
Martin Aumüller, Erik Bernhardsson, Alexander Faithfull
This paper describes ANN-Benchmarks, a tool for evaluating the performance of in-memory approximate nearest neighbor algorithms. It provides a standard interface for measuring the…
Distance-Sensitive hashing
Martin Aumüller, Tobias Christiani, Rasmus Pagh +1
Locality-sensitive hashing (LSH) is an important tool for managing high-dimensional noisy or uncertain data, for example in connection with data cleaning (similarity join) and nois…
Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths
Martin Aumüller, Martin Dietzfelbinger, Clemens Heuberger +2
We present an average case analysis of a variant of dual-pivot quicksort. We show that the used algorithmic partitioning strategy is optimal, i.e., it minimizes the expected number…
A Simple Hash Class with Strong Randomness Properties in Graphs and Hypergraphs
Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel
We study randomness properties of graphs and hypergraphs generated by simple hash functions. Several hashing applications can be analyzed by studying the structure of -uniform r…
Parameter-free Locality Sensitive Hashing for Spherical Range Reporting
Thomas D. Ahle, Martin Aumüller, Rasmus Pagh
We present a data structure for *spherical range reporting* on a point set , i.e., reporting all points in that lie within radius of a given query point . Our solutio…
Counting Zeros in Random Walks on the Integers and Analysis of Optimal Dual-Pivot Quicksort
Martin Aumüller, Martin Dietzfelbinger, Clemens Heuberger +2
We present an average case analysis of two variants of dual-pivot quicksort, one with a non-algorithmic comparison-optimal partitioning strategy, the other with a closely related a…
How Good is Multi-Pivot Quicksort?
Martin Aumüller, Martin Dietzfelbinger, Pascal Klaue
Multi-Pivot Quicksort refers to variants of classical quicksort where in the partitioning step pivots are used to split the input into segments. For many years, multi-p…
Optimal Partitioning for Dual-Pivot Quicksort
Martin Aumüller, Martin Dietzfelbinger
Dual-pivot quicksort refers to variants of classical quicksort where in the partitioning step two pivots are used to split the input into three segments. This can be done in differ…
Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash
Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel
It is shown that for cuckoo hashing with a stash as proposed by Kirsch, Mitzenmacher, and Wieder (2008) families of very simple hash functions can be used, maintaining the favorabl…