DBScholar

Back to papers

Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension

Summary: Introduce fractal dimension to quantify deviation from uniformity; show many real spatial point sets behave as fractals with non-integer dimensions. Use fractal dimension + cardinality to derive a formula predicting R-tree range-query I/Os for skewed data (error usually <5–10%), enabling analysis and optimizer estimates without uniformity/independence assumptions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h43b1fef1b106bda6
Venue
PODS
Year
1994
Pagerank
0.00011848523
Overall Rank
1,142 | 92.33%
DOI
10.1145/182591.182593

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{faloutsos_pods94,
        address = {New York, NY, USA},
        series = {{PODS} '94},
        title = {{Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension}},
        url = {https://dl.acm.org/doi/10.1145/182591.182593},
        doi = {10.1145/182591.182593},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Faloutsos, Christos and Kamel, Ibrahim},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank Citing Paper Year Venue Pagerank
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.0004503446
206 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00024986675
686 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00014775707
1,405 A Model for the Prediction of R-tree Performance 1996 PODS 0.0001076417
1,527 On the Analysis of Indexing Schemes 1997 PODS 0.00010350889
1,912 MindReader: Querying databases through multiple examples 1998 VLDB 9.3904326e-05
2,016 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.1771614e-05
2,079 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 9.0775779e-05
2,827 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.967335e-05
3,034 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.7330662e-05
3,182 General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows 2002 SIGMOD 7.561954e-05
4,060 Tight bounds for 2-dimensional indexing schemes 1998 PODS 6.8250997e-05
4,155 Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension 1996 VLDB 6.7762032e-05
4,834 A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries 1998 PODS 6.3883011e-05
6,052 Spatial Join Selectivity Using Power Laws 2000 SIGMOD 5.9028248e-05
8,726 Towards Practical Constraint Databases (Extended Abstract) 1996 PODS 5.2905577e-05
9,128 Modeling Skew in Data Streams 2006 SIGMOD 5.2234555e-05
9,544 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 5.1611019e-05
9,597 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1557462e-05
10,326 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD 5.0346745e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.001992968
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011405675
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.0003475226
101 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00033937215
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031645463
119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.0003137356
1,085 On B-tree Indices for Skewed Distributions 1992 VLDB 0.00012112632
1,144 Optimization Strategies for Spatial Query Processing 1991 VLDB 0.00011842581
1,861 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.4871409e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,303 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB
2 1,518 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB
3 4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD
4 10,048 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
5 2,828 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD
6 6,168 Modeling skewed distributions using multifractals and the '80-20 law' 1996 VLDB
7 1,861 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD
8 1,405 A Model for the Prediction of R-tree Performance 1996 PODS
9 4,155 Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension 1996 VLDB
10 2,827 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB