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}
}

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 ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

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

Online Edition: ACM Digital Library

References

[1]: ...
[2]: ...
[3]: Haran Boral, Steve Redfield: Database Machine Morphology. VLDB 1985: 59-71
[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
[6]: ...
[7]: ...
[8]: Christos Faloutsos: Gray Codes for Partial Match and Range Queries. IEEE Trans. Software Eng. 14(10): 1381-1393(1988)
[9]: ...
[10]: J. G. Griffiths: An Algorithm for Displaying a Class of Space-filling Curves. Softw., Pract. Exper. 16(5): 403-411(1986)
[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)
[15]: Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336
[16]: Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190
[17]: ...
[18]: Ronald L. Rivest: Partial-Match Retrieval Algorithms. SIAM J. Comput. 5(1): 19-50(1976)
[19]: Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31
[20]: James A. Thom, Kotagiri Ramamohanarao, Lee Naish: A Superjoin Algorithm for Deductive Databases. VLDB 1986: 189-196
[21]: ...
[22]: ...