Fractals for Secondary Key Retrieval

Summary: Uses fractal space‑filling curves (Hilbert) to create distance‑preserving mappings from multidimensional keys to 1D disk orderings for secondary-key/spatial access. Experiments show Hilbert consistently improves clustering over bit‑shuffling and Peano, reducing disk I/O. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h129f2968c978630b
Venue: PODS
Year: 1989
Pagerank: 0.00011427053
Overall Rank: 1,228 | 91.75%
DOI: 10.1145/73721.73746

Incoming Non-self Citations Over Time

Authors

1. Christos Faloutsos (University of Maryland)
2. Shari Roseman (University of Maryland)

BibTeX Citation

@inproceedings{faloutsos_pods89,
        address = {New York, NY, USA},
        series = {{PODS} '89},
        title = {{Fractals for Secondary Key Retrieval}},
        url = {https://dl.acm.org/doi/10.1145/73721.73746},
        doi = {10.1145/73721.73746},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Faloutsos, Christos and Roseman, Shari},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
336	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00020652147
363	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00019980483
488	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00017451091
839	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.0001354488
1,129	Managing Intervals Efficiently in Object-Relational Databases	2000	VLDB	0.00011899744
1,157	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.0001176973
1,877	Effectively Learning Spatial Indices	2020	VLDB	9.4498401e-05
2,065	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.0904572e-05
2,298	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.6797199e-05
2,390	Parallel R-trees	1992	SIGMOD	8.5335833e-05
3,553	Interactive Analysis of Web-Scale Data	2009	CIDR	7.20663e-05
4,336	Joining Interval Data in Relational Databases	2004	SIGMOD	6.6528595e-05
4,851	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD	6.377837e-05
5,716	An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees	1998	SIGMOD	6.0173987e-05
7,761	Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse	1999	SIGMOD	5.4565021e-05
8,186	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB	5.3800965e-05
10,007	BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data	2024	SIGMOD	5.0954911e-05
10,213	Continuous Query Processing in Data Streams Using Duality of Data and Queries	2006	SIGMOD	5.0573553e-05
11,666	Efficient Cost Modeling of Space-filling Curves	2024	VLDB	4.9769913e-05
13,053	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
101	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033923053
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00031633451
265	A Class of Data Structures for Associative Searching	1984	PODS	0.00022748432
6,739	A Superjoin Algorithm for Deductive Databases	1986	VLDB	5.6911821e-05
6,740	A Reliable Parallel Backend Using Multiattribute Clustering and Select-Join Operator	1986	VLDB	5.6911821e-05
6,741	Database Machine Morphology	1985	VLDB	5.6911821e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,786	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
2	4,061	Tight bounds for 2-dimensional indexing schemes	1998	PODS
3	1,142	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS
4	6,587	Efficient Search of Multidimensional B-Trees	1995	VLDB
5	2,827	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB
6	7,566	Cache-oblivious High-performance Similarity Join	2019	SIGMOD
7	5,334	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB
8	3,886	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD
9	336	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB
10	363	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD