ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Fractals for Secondary Key Retrieval.

Christos Faloutsos, Shari Roseman: Fractals for Secondary Key Retrieval. PODS 1989: 247-252
@inproceedings{DBLP:conf/pods/FaloutsosR89,
  author    = {Christos Faloutsos and
               Shari Roseman},
  title     = {Fractals for Secondary Key Retrieval},
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {247-252},
  ee        = {http://doi.acm.org/10.1145/73721.73746, db/conf/pods/FaloutsosR89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper we propose the use of fractals and especially the Hilbert curve, in order to design good distance-preserving mappings. Such mappings improve the performance of secondary-key- and spatial- access methods, where multi-dimensional points have to be stored on an l-dimensional medium (e.g., disk). Good clustering reduces the number of disk accesses on retrieval, improving the response time. Our experiments on range queries and nearest neighbor queries showed that the proposed Hilbert curve achieves better clustering than older methods ("bit-shuffling", or Peano curve), for every situation we tried.

Copyright © 1989 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania. ACM Press 1989, ISBN 0-89791-308-6
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]
...
[2]
...
[3]
Haran Boral, Steve Redfield: Database Machine Morphology. VLDB 1985: 59-71 BibTeX
[4]
...
[5]
Jean-Pierre Cheiney, Pascal Faudemay, Rodolphe Michel, Jean-Marc Thévenin: A Reliable Backend Using Multiattribute Clustering and Select-Join Operator. VLDB 1986: 220-227 BibTeX
[6]
...
[7]
...
[8]
Christos Faloutsos: Gray Codes for Partial Match and Range Queries. IEEE Trans. Software Eng. 14(10): 1381-1393(1988) BibTeX
[9]
...
[10]
J. G. Griffiths: An Algorithm for Displaying a Class of Space-filling Curves. Softw., Pract. Exper. 16(5): 403-411(1986) BibTeX
[11]
...
[12]
...
[13]
...
[14]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
[15]
Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 BibTeX
[16]
Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190 BibTeX
[17]
...
[18]
Ronald L. Rivest: Partial-Match Retrieval Algorithms. SIAM J. Comput. 5(1): 19-50(1976) BibTeX
[19]
Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31 BibTeX
[20]
James A. Thom, Kotagiri Ramamohanarao, Lee Naish: A Superjoin Algorithm for Deductive Databases. VLDB 1986: 189-196 BibTeX
[21]
...
[22]
...

Referenced by

  1. H. V. Jagadish, Laks V. S. Lakshmanan, Divesh Srivastava: Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse. SIGMOD Conference 1999: 37-48
  2. Bongki Moon, Joel H. Saltz: Scalability Analysis of Declustering Methods for Multidimensional Range Queries. IEEE Trans. Knowl. Data Eng. 10(2): 310-327(1998)
  3. Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas: Fast and Effective Retrieval of Medical Tumor Shapes. IEEE Trans. Knowl. Data Eng. 10(6): 889-904(1998)
  4. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  5. Yannis Kotidis, Nick Roussopoulos: An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees. SIGMOD Conference 1998: 249-258
  6. Shashi Shekhar, Duen-Ren Liu: CCAM: A Connectivity-Clustered Access Method for Networks and Network Computations. IEEE Trans. Knowl. Data Eng. 9(1): 102-119(1997)
  7. Euripides G. M. Petrakis, Christos Faloutsos: Similarity Searching in Medical Image Databases. IEEE Trans. Knowl. Data Eng. 9(3): 435-447(1997)
  8. Christos Faloutsos, H. V. Jagadish, Yannis Manolopoulos: Analysis of the n-Dimensional Quadtree Decomposition for Arbitrary Hyperectangles. IEEE Trans. Knowl. Data Eng. 9(3): 373-383(1997)
  9. Stefan Berchtold, Christian Böhm, Daniel A. Keim, Hans-Peter Kriegel: A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space. PODS 1997: 78-86
  10. Scott T. Leutenegger, J. M. Edgington, Mario A. Lopez: STR: A Simple and Efficient Algorithm for R-Tree Packing. ICDE 1997: 497-506
  11. Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas: Fast Nearest Neighbor Search in Medical Image Databases. VLDB 1996: 215-226
  12. Nick Koudas, Christos Faloutsos, Ibrahim Kamel: Declustering Spatial Databases on a Multi-Computer Architecture. EDBT 1996: 592-614
  13. Christos Faloutsos: Fast Searching by Content in Multimedia Databases. IEEE Data Eng. Bull. 18(4): 31-40(1995)
  14. Christos Faloutsos, King-Ip Lin: FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets. SIGMOD Conference 1995: 163-174
  15. Walid G. Aref, Daniel Barbará, Stephen Johnson, Sharad Mehrotra: Efficient Processing of Proximity Queries for Large Databases. ICDE 1995: 147-154
  16. Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509
  17. Manish Arya, William F. Cody, Christos Faloutsos, Joel E. Richardson, Arthur Toya: QBISM: Extending a DBMS to Support 3D Medical Images. ICDE 1994: 314-325
  18. Christos Faloutsos, Ibrahim Kamel: High Performance R-trees. IEEE Data Eng. Bull. 16(3): 28-33(1993)
  19. Ibrahim Kamel, Christos Faloutsos: Parallel R-trees. SIGMOD Conference 1992: 195-204
  20. Christos Faloutsos, Yi Rong: DOT: A Spatial Access Method Using Fractals. ICDE 1991: 152-159
  21. Jack A. Orenstein: A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces. SIGMOD Conference 1990: 343-352
  22. H. V. Jagadish: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990: 332-342
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:57 2009