Carnegie Mellon University
Browse

Fractals for Secondary Key Retrieval

Download (55.96 kB)
journal contribution
posted on 1985-01-01, 00:00 authored by Christos Faloutsos, Shari Roseman
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 1-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.

History

Publisher Statement

All Rights Reserved

Date

1985-01-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC