Analysis of the Clustering Properties of Hilbert Space-filling Curve

dc.contributor.authorMoon, Bongkien_US
dc.contributor.authorJagadish, H.V.en_US
dc.contributor.authorFaloutsos, Christosen_US
dc.contributor.authorSaltz, Joelen_US
dc.date.accessioned2004-05-31T22:38:10Z
dc.date.available2004-05-31T22:38:10Z
dc.date.created1996-03en_US
dc.date.issued1998-10-15en_US
dc.description.abstractSeveral 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)en_US
dc.format.extent452347 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/804
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3611en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-96-20en_US
dc.titleAnalysis of the Clustering Properties of Hilbert Space-filling Curveen_US
dc.typeTechnical Reporten_US

Files

Original bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
CS-TR-3611.ps
Size:
441.75 KB
Format:
Postscript Files
Loading...
Thumbnail Image
Name:
CS-TR-3611.pdf
Size:
239.8 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of CS-TR-3611.ps