-
Notifications
You must be signed in to change notification settings - Fork 6
/
index.html
51 lines (40 loc) · 3.47 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
<!DOCTYPE html>
<html lang="en-us">
<head>
<meta charset="UTF-8">
<meta name="google-site-verification" content="boAwYTu-oFSycVA1A0NGlbb-99rA7YUT6wOp-WDh7t4" />
<title>Hyperloglog-sketch-estimation-paper by oertl</title>
<meta name="viewport" content="width=device-width, initial-scale=1">
<link rel="stylesheet" type="text/css" href="gh-pages/stylesheets/normalize.css" media="screen">
<link href='https://fonts.googleapis.com/css?family=Open+Sans:400,700' rel='stylesheet' type='text/css'>
<link rel="stylesheet" type="text/css" href="gh-pages/stylesheets/stylesheet.css" media="screen">
<link rel="stylesheet" type="text/css" href="gh-pages/stylesheets/github-light.css" media="screen">
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-86898058-1', 'auto');
ga('send', 'pageview');
</script>
</head>
<body>
<section class="page-header">
<h1 class="project-name">New cardinality estimation algorithms <br> for HyperLogLog sketches</h1>
<h2 class="project-tagline">Paper about the estimation of cardinalities from HyperLogLog sketches</h2>
<a href="http://oertl.github.io/hyperloglog-sketch-estimation-paper/paper/paper.pdf" class="btn">Download Paper</a>
<a href="https://github.com/oertl/hyperloglog-sketch-estimation-paper" class="btn">View on GitHub</a>
<a href="https://github.com/oertl/hyperloglog-sketch-estimation-paper/zipball/master" class="btn">Download .zip</a>
<a href="https://github.com/oertl/hyperloglog-sketch-estimation-paper/tarball/master" class="btn">Download .tar.gz</a>
</section>
<section class="main-content">
<h2>
<a id="abstract" class="anchor" href="#abstract" aria-hidden="true"><span aria-hidden="true" class="octicon octicon-link"></span></a>Abstract</h2>
<p>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 presented that eliminates the bias for small and large cardinalities. Based on the maximum likelihood principle a second unbiased method is derived together with a robust and efficient numerical algorithm to calculate the estimate. The maximum likelihood approach can also be applied to more than a single HyperLogLog sketch. In particular, it is shown that it gives more precise cardinality estimates for union, intersection, or relative complements of two sets that are both represented by HyperLogLog sketches compared to the conventional technique using the inclusion-exclusion principle. All the new methods are demonstrated and verified by extensive simulations.</p>
<footer class="site-footer">
<span class="site-footer-owner"><a href="https://github.com/oertl/hyperloglog-sketch-estimation-paper">Hyperloglog-sketch-estimation-paper</a> is maintained by <a href="https://github.com/oertl">Otmar Ertl</a>.</span>
<span class="site-footer-credits">This page was generated by <a href="https://pages.github.com">GitHub Pages</a> using the <a href="https://github.com/jasonlong/cayman-theme">Cayman theme</a> by <a href="https://twitter.com/jasonlong">Jason Long</a>.</span>
</footer>
</section>
</body>
</html>