Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension

Summary: Uses Hausdorff fractal dimension, rather than uniformity, to derive closed-form estimates of n-dimensional quadtree block counts for self-similar spatial data. Predicts linear-quadtree/Z-order space and query costs, validated across diverse real datasets. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hb839218f1f59432b
Venue: VLDB
Year: 1996
Pagerank: 6.7762032e-05
Overall Rank: 4,155 | 72.07%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Christos Faloutsos (University of Maryland)
2. Volker Gaede (Humboldt University of Berlin)

BibTeX Citation

@article{faloutsos_vldb96,
        title = {{Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension}},
        author = {Faloutsos, Christos and Gaede, Volker},
        journal = {PVLDB},
        series = {{VLDB} '96},
        pages = {40--50},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,157	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00011774968
1,527	On the Analysis of Indexing Schemes	1997	PODS	0.00010350889
3,221	A Raster Approximation for the Processing of Spatial Joins	1998	VLDB	7.5149339e-05

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
42	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00045773967
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045337853
264	A Class of Data Structures for Associative Searching	1984	PODS	0.00022757762
358	A Retrieval Technique for Similar Shapes	1991	SIGMOD	0.00020019939
1,035	Redundancy in Spatial Databases	1989	SIGMOD	0.00012393393
1,142	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00011848523
2,827	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	7.967335e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,215	Indexing Methods for Moving Object Databases: Games and Other Applications	2013	SIGMOD
2	6,748	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS
3	6,216	Window Query-Optimal Clustering of Spatial Objects	1995	PODS
4	4,060	Tight bounds for 2-dimensional indexing schemes	1998	PODS
5	1,157	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS
6	5,328	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB
7	1,861	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD
8	4,865	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS
9	2,827	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB
10	1,142	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS