Analysis of the Clustering Properties of Hilbert Space-filling Curve
Analysis of the Clustering Properties of Hilbert Space-filling Curve
Files
Publication or External Link
Date
1998-10-15
Authors
Moon, Bongki
Jagadish, H.V.
Faloutsos, Christos
Saltz, Joel
Advisor
Citation
DRUM DOI
Abstract
Several schemes for linear mapping of multidimensional space
have been proposed for many applications such as
access methods for spatio-temporal databases, image compression and so on.
In all these applications, one of the most desired properties
from such linear mappings is clustering, which means
the locality between objects in the multidimensional space
is preserved in the linear space.
It is widely believed that Hilbert space-filling curve
achieves the best clustering.
In this paper we provide closed-form formulas of
the number of clusters required by a given query region
of an arbitrary shape (e.g., polygons and polyhedra)
for Hilbert space-filling curve.
Both the asymptotic solution for a general case and the exact solution
for a special case generalize the previous work,
and they agree with the empirical results that
the number of clusters depends on the hyper-surface area of the query region
and not on its hyper-volume.
We have also shown that Hilbert curve achieves better clustering
than z-curve.
From the practical point of view,
the formulas given in this paper provide a simple measure
which can be used to predict the required disk access behaviors
and hence the total access time.
(Also cross-referenced as UMIACS-TR-96-20)