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.00011431306
Overall Rank: 1,226 | 91.76%
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
335	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00020660268
364	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00019976696
488	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00017457851
837	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00013551047
1,128	Managing Intervals Efficiently in Object-Relational Databases	2000	VLDB	0.00011905274
1,157	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00011774968
1,878	Effectively Learning Spatial Indices	2020	VLDB	9.4451309e-05
2,064	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.0942902e-05
2,294	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.6837534e-05
2,388	Parallel R-trees	1992	SIGMOD	8.5375939e-05
3,560	Interactive Analysis of Web-Scale Data	2009	CIDR	7.2072209e-05
4,336	Joining Interval Data in Relational Databases	2004	SIGMOD	6.6560067e-05
4,850	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD	6.3808017e-05
5,714	An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees	1998	SIGMOD	6.0202342e-05
7,755	Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse	1999	SIGMOD	5.4590631e-05
8,179	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB	5.3826446e-05
10,002	BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data	2024	SIGMOD	5.0979044e-05
10,206	Continuous Query Processing in Data Streams Using Duality of Data and Queries	2006	SIGMOD	5.059736e-05
11,660	Efficient Cost Modeling of Space-filling Curves	2024	VLDB	4.9793485e-05
13,047	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB	4.9793485e-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.00033937215
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00031645463
264	A Class of Data Structures for Associative Searching	1984	PODS	0.00022757762
6,732	A Superjoin Algorithm for Deductive Databases	1986	VLDB	5.6938051e-05
6,733	A Reliable Parallel Backend Using Multiattribute Clustering and Select-Join Operator	1986	VLDB	5.6938051e-05
6,734	Database Machine Morphology	1985	VLDB	5.6938051e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,780	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
2	4,060	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,584	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,560	Cache-oblivious High-performance Similarity Join	2019	SIGMOD
7	5,328	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB
8	3,887	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD
9	335	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB
10	364	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD