Address Block Counting Using Two-Tier Cardinality Estimation

Abstract

An address block is defined as a set of continuous addresses between two points in an address space. Counting the number of distinct address blocks that have been accessed during a measurement period can provide useful information for cyber security, computer networks, and storage systems. However, this counting problem becomes challenging when addresses are accessed randomly since adjacent addresses must be carefully identified and merged into one block. This study presents a new algorithm that can accurately estimate the number of distinct address blocks where each address access is monitored only once. This new algorithm requires only three counters to keep the numbers of distinct addresses and one-bit truncated addresses, respectively, in two-tier counting architecture. Both time and space complexities are significantly improved because only three counters are required for cardinality estimation instead of traditional hash table or tree data structures. Experimental results show that the new scheme saves more than 50% memory space and runs two times faster than a tree-based existing algorithm; the relative error of estimation is less than 10%.

Keywords

• Cardinality estimation
• streaming algorithm
• data analysis
• counting
• ransomware