Accelerating the HyperLogLog Cardinality Estimation Algorithm
Use este enlace para citar
http://hdl.handle.net/2183/28968
A non ser que se indique outra cousa, a licenza do ítem descríbese como Atribución 4.0 Internacional
Coleccións
- GI-GAC - Artigos [192]
Metadatos
Mostrar o rexistro completo do ítemTítulo
Accelerating the HyperLogLog Cardinality Estimation AlgorithmData
2017Cita bibliográfica
Cem Bozkus, Basilio B. Fraguela, "Accelerating the HyperLogLog Cardinality Estimation Algorithm", Scientific Programming, vol. 2017, Article ID 2040865, 8 pages, 2017. https://doi.org/10.1155/2017/2040865
Resumo
[Abstract] 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 𝑂(𝑛) to 𝑂(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.
Versión do editor
Dereitos
Atribución 4.0 Internacional This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.