42 citations · 194 across the 18 of their papers we have counts for
10 papers · 1 filter
JumpBackHash: Say Goodbye to the Modulo Operation to Distribute Keys Uniformly to Buckets
Otmar Ertl
Introduction. Distributed data processing and storage systems require efficient methods to distribute keys across buckets. While simple and fast, the traditional modulo-based mappi…
ExaLogLog: Space-Efficient and Practical Approximate Distinct Counting up to the Exa-Scale
Otmar Ertl
This work introduces ExaLogLog, a new data structure for approximate distinct counting, which has the same practical properties as the popular HyperLogLog algorithm. It is commutat…
UltraLogLog: A Practical and More Space-Efficient Alternative to HyperLogLog for Approximate Distinct Counting
Otmar Ertl
Since its invention HyperLogLog has become the standard algorithm for approximate distinct counting. Due to its space efficiency and suitability for distributed systems, it is wide…
Estimation from Partially Sampled Distributed Traces
Otmar Ertl
Sampling is often a necessary evil to reduce the processing and storage costs of distributed tracing. In this work, we describe a scalable and adaptive sampling approach that can p…
SetSketch: Filling the Gap between MinHash and HyperLogLog
Otmar Ertl
MinHash and HyperLogLog are sketching algorithms that have become indispensable for set summaries in big data applications. While HyperLogLog allows counting different elements wit…
ProbMinHash -- A Class of Locality-Sensitive Hash Algorithms for the (Probability) Jaccard Similarity
Otmar Ertl
The probability Jaccard similarity was recently proposed as a natural generalization of the Jaccard similarity to measure the proximity of sets whose elements are associated with r…
BagMinHash - Minwise Hashing Algorithm for Weighted Sets
Otmar Ertl
Minwise hashing has become a standard tool to calculate signatures which allow direct estimation of Jaccard similarities. While very efficient algorithms already exist for the unwe…
New Cardinality Estimation Methods for HyperLogLog Sketches
Otmar Ertl
This work presents new cardinality estimation methods for data sets recorded by HyperLogLog sketches. A simple derivation of the original estimator was found, that also gives insig…
SuperMinHash - A New Minwise Hashing Algorithm for Jaccard Similarity Estimation
Otmar Ertl
This paper presents a new algorithm for calculating hash signatures of sets which can be directly used for Jaccard similarity estimation. The new approach is an improvement over th…
New cardinality estimation algorithms for HyperLogLog sketches
Otmar Ertl
This paper presents new methods to estimate the cardinalities of data sets recorded by HyperLogLog sketches. A theoretically motivated extension to the original estimator is presen…