Martin Aumüller

Martin Aumüller

Auto-generated profile, based on publicly available information

Martin Aumüller

IT University of Copenhagen, Copenhagen, Denmark

Research Focus & Metrics

Academic Career Length

18Years (2009-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
28 September 2017
Verified
Book Chapter
Closed access
PDF file
MAMartin Aumüller
Martin Aumüller
EBErik Bernhardsson
Erik Bernhardsson
AFAlexander Faithfull
Alexander Faithfull

1 November 2021 in Information Systems
Verified
Journal Article
Open access
MAMartin Aumüller
Martin Aumüller
MCMatteo Ceccarello
Matteo Ceccarello

8 October 2013 in Algorithmica
Verified
Journal Article
Closed access
PDF file
MAMartin Aumüller
Martin Aumüller
MDMartin Dietzfelbinger
Martin Dietzfelbinger
PWPhilipp Woelfel
Philipp Woelfel

17 November 2015 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
PDF file
MAMartin Aumüller
Martin Aumüller
MDMartin Dietzfelbinger
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 different ways, giving rise to different algorithms. Recently, a dual-pivot algorithm due to Yaroslavskiy received much attention, because it replaced the well-engineered quicksort algorithm in Oracle’s Java 7 runtime library. Nebel and Wild (ESA 2012) analyzed this algorithm and showed that on average it uses 1.9 n ln n + O ( n ) comparisons to sort an input of size n , beating standard quicksort, which uses 2 n ln n + O ( n ) comparisons. We introduce a model that captures all dual-pivot algorithms, give a unified analysis, and identify new dual-pivot algorithms that minimize the average number of key comparisons among all possible algorithms up to a linear term. This minimum is 1.8 n ln n + O ( n ). For the case that the pivots are chosen from a small sample, we include a comparison of dual-pivot quicksort and classical quicksort. Specifically, we show that dual-pivot quicksort benefits from a skewed choice of pivots. We experimentally evaluate our algorithms and compare them to Yaroslavskiy’s algorithm and the recently described 3-pivot quicksort algorithm of Kushagra et al. (ALENEX 2014).

4 January 2017
Verified
Conference Paper
Closed access
TAThomas D. Ahle
Thomas D. Ahle
MAMartin Aumüller
Martin Aumüller
RPRasmus Pagh
Rasmus Pagh
We present a data structure for *spherical range reporting* on a point set $S$, i.e., reporting all points in $S$ that lie within radius $r$ of a given query point $q$. Our solution builds upon the Locality-Sensitive Hashing (LSH) framework of Indyk and Motwani, which represents the asymptotically best solutions to near neighbor problems in high dimensions. While traditional LSH data structures have several parameters whose optimal values depend on the distance distribution from $q$ to the points of $S$, our data structure is parameter-free, except for the space usage, which is configurable by the user. Nevertheless, its expected query time basically matches that of an LSH data structure whose parameters have been *optimally chosen for the data and query* in question under the given space constraints. In particular, our data structure provides a smooth trade-off between hard queries (typically addressed by standard LSH) and easy queries such as those where the number of points to report is a constant fraction of $S$, or where almost all points in $S$ are far away from the query point. In contrast, known data structures fix LSH parameters based on certain parameters of the input alone. The algorithm has expected query time bounded by $O(t (n/t)^\rho)$, where $t$ is the number of points to report and $\rho\in (0,1)$ depends on the data distribution and the strength of the LSH family used. We further present a parameter-free way of using multi-probing, for LSH families that support it, and show that for many such families this approach allows us to get expected query time close to $O(n^\rho+t)$, which is the best we can hope to achieve using LSH. The previously best running time in high dimensions was $\Omega(t n^\rho)$. For many data distributions where the intrinsic dimensionality of the point set close to $q$ is low, we can give improved upper bounds on the expected query time.Comment: 21 pages, 5 figures, due to the limitation "The abstract field cannot be longer than 1,920 characters", the abstract appearing here is slightly shorter than that in the PDF fil

10 October 2016 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
PDF file
MAMartin Aumüller
Martin Aumüller
MDMartin Dietzfelbinger
Martin Dietzfelbinger
PKPascal Klaue
Pascal Klaue
Multi-Pivot Quicksort refers to variants of classical quicksort where in the partitioning step k pivots are used to split the input into k + 1 segments. For many years, multi-pivot quicksort was regarded as impractical, but in 2009 a two-pivot approach by Yaroslavskiy, Bentley, and Bloch was chosen as the standard sorting algorithm in Sun’s Java 7. In 2014 at ALENEX, Kushagra et al. introduced an even faster algorithm that uses three pivots. This article studies what possible advantages multi-pivot quicksort might offer in general. The contributions are as follows: Natural comparison-optimal algorithms for multi-pivot quicksort are devised and analyzed. The analysis shows that the benefits of using multiple pivots with respect to the average comparison count are marginal and these strategies are inferior to simpler strategies such as the well-known median-of- k approach. A substantial part of the partitioning cost is caused by rearranging elements. A rigorous analysis of an algorithm for rearranging elements in the partitioning step is carried out, observing mainly how often array cells are accessed during partitioning. The algorithm behaves best if three to five pivots are used. Experiments show that this translates into good cache behavior and is closest to predicting observed running times of multi-pivot quicksort algorithms. Finally, it is studied how choosing pivots from a sample affects sorting cost. The study is theoretical in the sense that although the findings motivate design recommendations for multipivot quicksort algorithms that lead to running-time improvements over known algorithms in an experimental setting, these improvements are small.