Probabilistic Data Structures for Blockchain-Based Internet of Things Applications

11

Cardinality Estimation Probabilistic Data Structures

11.1 Introduction

The next category of PDS is for cardinality estimation that is popularly used in query processing and data base design. Database models uses algorithms of cardinality estimation to compute selectivity of a predicate. Linear counting, LogLog, HyperLogLog are some of the algorithms that falls under this category. The aim of such a PDS is to count number of unique elements of a set where duplicates are present. For instance, for a set S=[1,2,3,1,2,3,4] the cardinality os the set is 4. An important use case for such PDS is to compute number of unique visitors for a particular website. As per data given by, from May 2019 to Sep 2019, the total visit on Amazon web page is ...