2009/05/26 by Attikos, Christos, Doumpos, Michael
#Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.0905.4138
Fractal dimension is widely adopted in spatial databases and data mining, among others as a measure of dataset skewness. State-of-the-art algorithms for estimating the fractal dimension exhibit linear runtime complexity whether based on box-counting or approximation schemes. In this paper, we revisit a correlation fractal dimension estimation algorithm that redundantly rescans the dataset and, extending that work, we propose another linear, yet faster and as accurate method, which completes in a single pass.