DBScholar

Back to papers

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
869
Venue
PODS
Year
1989
Pagerank
0.00011672157
Overall Rank
1,202 | 91.76%
DOI
10.1145/73721.73746

Incoming Non-self Citations Over Time

Authors

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
329 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00021068647
354 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00020355578
483 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017756569
815 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013835761
1,137 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00012027131
1,139 Managing Intervals Efficiently in Object-Relational Databases 2000 VLDB 0.0001202217
1,840 Effectively Learning Spatial Indices 2020 VLDB 9.6404567e-05
2,020 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 9.2983514e-05
2,249 A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces 1990 SIGMOD 8.8700017e-05
2,341 Parallel R-trees 1992 SIGMOD 8.7233426e-05
3,497 Interactive Analysis of Web-Scale Data 2009 CIDR 7.3634378e-05
4,268 Joining Interval Data in Relational Databases 2004 SIGMOD 6.7925685e-05
4,751 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 6.5241784e-05
5,638 An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees 1998 SIGMOD 6.138684e-05
7,612 Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse 1999 SIGMOD 5.5834218e-05
8,003 Towards Designing and Learning Piecewise Space-Filling Curves 2023 VLDB 5.5084586e-05
10,017 Continuous Query Processing in Data Streams Using Duality of Data and Queries 2006 SIGMOD 5.1758281e-05
11,193 BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data 2024 SIGMOD 5.093636e-05
11,342 Efficient Cost Modeling of Space-filling Curves 2024 VLDB 5.093636e-05
12,757 Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases 2005 VLDB 5.093636e-05
Previous Page 1 / 1 Next

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
96 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00034590762
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.0003221055
253 A Class of Data Structures for Associative Searching 1984 PODS 0.00023200431
6,608 A Superjoin Algorithm for Deductive Databases 1986 VLDB 5.8231458e-05
6,609 A Reliable Parallel Backend Using Multiattribute Clustering and Select-Join Operator 1986 VLDB 5.8231458e-05
6,610 Database Machine Morphology 1985 VLDB 5.8231458e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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