Analysis of the Clustering Properties of the Hilbert Space-Filling Curve

By Bongki Moon, Hosagrahar Visvesvaraya Jagadish, Christos Faloutsos, Joel H. Saltz. IEEE Transactions on Knowledge and Data Engineering, 2001

815 citations recorded by the source corpus.

Several schemes for the linear mapping of a multidimensional space have been proposed for various applications, such as access methods for spatio-temporal databases and image compression. In these applications, one of the most desired properties from such linear mappings is clustering, which means the locality between objects in the multidimensional space being preserved in the linear space. It is widely believed that the Hilbert space-filling curve achieves the best clustering (Abel and Mark, 1990; Jagadish, 1990). We analyze the clustering property of the Hilbert space-filling curve by deriving closed-form formulas for the number of clusters in a given query region of an arbitrary shape (e.g., polygons and polyhedra). Both the asymptotic solution for the general case and the exact solution for a special case generalize previous work. They agree with the empirical results that the number of clusters depends on the hypersurface area of the query region and not on its hypervolume. We also show that the Hilbert curve achieves better clustering than the z curve. From a practical point of view, the formulas given provide a simple measure that can be used to predict the required disk access behaviors and, hence, the total access time.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/dd81feac3795444066ef591373ac62e112666b95

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

General purpose molecular dynamics simulations fully implemented on graphics processing units (2008, background): “An even better option is to reorder the particles based on the path of a space filling curve [19] [20], which have received a lot of attention lately for efficient database searches on multi-dimensional data sets.”
Preventing Location-Based Identity Inference in Anonymous Spatial Queries (2007, background): “With high probability [24], if two points are in close proximity in the 2D space, they will also be close in the 1D transformation.”
Private queries in location based services: anonymizers are not necessary (2008, background): “If two POIs are close in the 2-D space, they are likely to be close in the Hilbert ordering, as well [21].”
PRIVE: anonymous location-based queries in distributed mobile systems (2007, background): “With high probability, if two points are close in the 2D space, they will also be close in the Hilbert transformation [18].”
Hybrid LSTM and Encoder–Decoder Architecture for Detection of Image Forgeries (2019, background): “The Hilbert curve has been shown to outperform many other curves in maintaining the spatial locality, when transforming from a multidimensional space to a one-dimensional space [63].”
Data exploration of turbulence simulations using a database cluster (2007, background): “In fact, the compact spatial organization of the Morton order results in low I/O complexity for all convex regions [18].”
Outlier mining in large high-dimensional data sets (2005, background): “…large and high-dimensional data sets are considered, a good algorithm for the solution of the Outlier Detection Problem is the naive nestedloop algorithm which, in order to compute the weight of each point, must consider the distance from all the points of the data set, thus requiring O(N2d) time.”
Fast Data Anonymization with Low Information Loss (2007, methodology): “With high probability, if two points are close in the multi-dimensional space, they will also be close in the Hilbert transformation [15].”