Wong, Angeline; Wu, Leejay; Gibbons, Phillip B.; Faloutsos, Christos Fast estimation of fractal dimension and correlation integral on stream data. (English) Zbl 1173.68873 Inf. Process. Lett. 93, No. 2, 91-97 (2005). 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. Cited in 1 Document MSC: 68W25 Approximation algorithms 68P15 Database theory 68W20 Randomized algorithms Keywords:approximation algorithms; databases; randomized algorithms; fractal dimension; box counting PDF BibTeX XML Cite \textit{A. Wong} et al., Inf. Process. Lett. 93, No. 2, 91--97 (2005; Zbl 1173.68873) Full Text: DOI References: [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.