![](/images/graphics-bg.png)
Accelerating the HyperLogLog Cardinality Estimation Algorithm
Joint Authors
Fraguela, Basilio B.
Bozkus, Cem
Source
Issue
Vol. 2017, Issue 2017 (31 Dec. 2017), pp.1-8, 8 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2017-09-14
Country of Publication
Egypt
No. of Pages
8
Main Subjects
Abstract EN
In recent years, vast amounts of data of different kinds, from pictures and videos from our cameras to software logs from sensor networks and Internet routers operating day and night, are being generated.
This has led to new big data problems, which require new algorithms to handle these large volumes of data and as a result are very computationally demanding because of the volumes to process.
In this paper, we parallelize one of these new algorithms, namely, the HyperLogLog algorithm, which estimates the number of different items in a large data set with minimal memory usage, as it lowers the typical memory usage of this type of calculation from O(n) to O(1).
We have implemented parallelizations based on OpenMP and OpenCL and evaluated them in a standard multicore system, an Intel Xeon Phi, and two GPUs from different vendors.
The results obtained in our experiments, in which we reach a speedup of 88.6 with respect to an optimized sequential implementation, are very positive, particularly taking into account the need to run this kind of algorithm on large amounts of data.
American Psychological Association (APA)
Bozkus, Cem& Fraguela, Basilio B.. 2017. Accelerating the HyperLogLog Cardinality Estimation Algorithm. Scientific Programming،Vol. 2017, no. 2017, pp.1-8.
https://search.emarefa.net/detail/BIM-1203313
Modern Language Association (MLA)
Bozkus, Cem& Fraguela, Basilio B.. Accelerating the HyperLogLog Cardinality Estimation Algorithm. Scientific Programming No. 2017 (2017), pp.1-8.
https://search.emarefa.net/detail/BIM-1203313
American Medical Association (AMA)
Bozkus, Cem& Fraguela, Basilio B.. Accelerating the HyperLogLog Cardinality Estimation Algorithm. Scientific Programming. 2017. Vol. 2017, no. 2017, pp.1-8.
https://search.emarefa.net/detail/BIM-1203313
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1203313