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 prc+ posed Hilbert curve achieves better clustering than older methods ("bit-shuffling", or Peano curve), for every situation we tried.
Faloutsos et al. REF proposed the use of the Hilbert code, presenting that the good distance-preserving mappings can improve the performance of a spatial index and a spatial query and demonstrated that the Hilbert code achieved better clustering than Z-ordering (actually, the Peano curve) and bit-shuffling.
Fractals for secondary key retrieval
PODS '89
Computer Science