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: 8521
Venue: VLDB
Year: 1996
Pagerank: 6.9272604e-05
Overall Rank: 4,070 | 72.08%
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,137	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00012027131
1,512	On the Analysis of Indexing Schemes	1997	PODS	0.00010536001
3,170	A Raster Approximation for the Processing of Spatial Joins	1998	VLDB	7.6703896e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
41	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00046675394
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
253	A Class of Data Structures for Associative Searching	1984	PODS	0.00023200431
350	A Retrieval Technique for Similar Shapes	1991	SIGMOD	0.00020425134
1,019	Redundancy in Spatial Databases	1989	SIGMOD	0.00012622386
1,129	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00012061727
2,774	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	8.1372328e-05

Semantically Similar Papers

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