zbMATH — the first resource for mathematics

Fast estimation of fractal dimension and correlation integral on stream data. (English) Zbl 1173.68873
Summary: We give a very space-efficient, yet fast method for estimating the fractal dimensionality of the points in a data stream. Algorithms to estimate the fractal dimension exist, such as the straightforward quadratic algorithm and the faster \(O(N\log N)\) or even \(O(N)\) box-counting algorithms. However, the sub-quadratic algorithms require \(\Omega (N)\) space. In this paper, we propose an algorithm that computes the fractal dimension in a single pass, using a constant amount of memory relative to data cardinality. Experimental results on synthetic and real world data sets demonstrate the effectiveness of our algorithm.

68W25 Approximation algorithms
68P15 Database theory
68W20 Randomized algorithms
Full Text: DOI
[1] Alon, N.; Matias, Y.; Szegedy, M., The space complexity of approximating the frequency moments, (), 20-29 · Zbl 0922.68057
[2] Belussi, A.; Faloutsos, C., Estimating the selectivity of spatial queries using the ‘correlation’ fractal dimension, (), 299-310
[3] Berchtold, S.; Böhm, C.; Braunmüller, B.; Keim, D.; Kriegel, H.-P., Fast parallel similarity search in multimedia databases, (), 1-12
[4] Faloutsos, C.; Kamel, I., Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension, (), 4-13, Also available as CS-TR-3198, UMIACS-TR-93-130
[5] Mandelbrot, B., Fractal geometry of nature, (1977), W.H. Freeman New York
[6] Pagel, B.-U.; Korn, F.; Faloutsos, C., Deflating the dimensionality curse using multiple fractal dimensions, (), 589-598
[7] Papadimitriou, S.; Kitagawa, H.; Gibbons, P.B.; Faloutsos, C., LOCI: fast outlier detection using the local correlation integral, (), 315-326
[8] Papadopoulos, A.; Manolopoulos, Y., Performance of nearest neighbor queries in R-trees, (), 394-408
[9] Schroeder, M., Fractals, chaos, power laws: minutes from an infinite paradise, (1991), W.H. Freeman and Company New York · Zbl 0758.58001
[10] Traina, C.; Traina, A.J.M.; Wu, L.; Faloutsos, C., Fast feature selection using the fractal dimension, (), 158-171
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.