ACRMiner: An Incremental Approach for Finding Dense and Sparse Rectangular Regions from a 2D Interval Dataset

Abstract

In many applications, transactions are associated with intervals related to time, temperature, humidity or other similar measures.  The term "2D interval data" or "rectangle data" is used when there are two connected intervals with each transaction. Two connected intervals give rise to a rectangle. The rectangles may overlap producing regions with different density values. The density value or support of a region is the number of rectangles that contain it. A region is closed if its density is strictly bigger than any region properly containing it. For rectangle dataset, these regions are rectangular in shape.In this paper an algorithm named ACRMiner has been proposed that takes as input a sequence of rectangles and computes all closed overlapping rectangles and their density values. The algorithm is incremental and thus is suitable for dynamic environment. Depending on an input threshold the regions can be classified as dense and sparse.Here a tree-based data structure named as ACR-Tree is used. The method has been implemented and tested on synthetic and real-life datasets and results have been reported. Few applications of this algorithm have been discussed. The worst-case time complexity the algorithmis O(n⁵) where n is the number of input rectangles.