Probabilistic data structures for big data analytics: A comprehensive review

doi:10.1016/j.knosys.2019.104987

2020-01-01

PRE

DOI：10.1016/j.knosys.2019.104987

原文链接

原文求助

摘要

En 中文

An exponential increase in the data generation resources is widely observed in last decade, because of evolution in technologies such as-cloud computing, IoT, social networking, etc. This enormous and unlimited growth of data has led to a paradigm shift in storage and retrieval patterns from traditional data structures to Probabilistic Data Structures (PDS). PDS are a group of data structures that are extremely useful for Big data and streaming applications in order to avoid high-latency analytical processes. These data structures use hash functions to compactly represent a set of items in stream-based computing while providing approximations with error bounds so that well-formed approximations get built into data collections directly. Compared to traditional data structures, PDS use much less memory and constant time in processing complex queries. This paper provides a detailed discussion of various issues which are normally encountered in massive data sets such as-storage, retrieval, query,etc. Further, role of PDS in solving these issues is also discussed where these data structures are used as temporary accumulators in query processing. Several variants of existing PDS along with their application areas have also been explored which give a holistic view of domains where these data structures can be applied for efficient storage and retrieval of massive data sets. Mathematical proofs of various parameters considered in the PDS have also been discussed in the paper. Moreover, the relative comparison of various PDS with respect to various parameters is also explored. (C) 2019 Elsevier B.V. All rights reserved.

Keyword:

Big data

Internet of things (IoT)

Probabilistic data structures

Bloom filter

Quotient filter

Count min sketch

HyperLogLog counter

MM-hash

Locality sensitive hashing