An Efficient Algorithm to Count the Relations in a Range of Binary Relations Represented by a k²-Tree
Martita Munoz Candia, Gilberto Gutiérrez, Rodrigo Torres-Avilés · IEEE Access · 2021
Two sets A and B, whose elements fulfill a total order on operator ≤, can have a binary relation R ⊆ A × B represented by the k2-tree compact data structure, which greatly improves storage space. Currently, Count query is managed by either using Range query or to modify the structure to have aggregate information, implying additional time or space in order to perform the query. This article presents Compact Count, which exploits the k2-tree properties to reduce the paths to be scanned to count the numbers in a range r, thus ensuring an expected runtime of O(logkr logkn) and storage of O(logkr) with the k2-tree parameters n and k. Our algorithm was compared through a series of experiments that consider both synthetic data with different distributions and real data, with a solution based on the Range algorithm. Experimental results show that Compact Count is 250 to 1,000 times faster than Range on synthetic and real data, respectively, with a small additional storage cost, as expected by the theoretical analysis.