Optimality of Clustering Properties of Space-Filling Curves

Date
2014-05-01
Authors
Xu, Pan
Tirthapura, Srikanta
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Computer Science
Organizational Unit
Journal Issue
Series
Abstract

Space-filling curves have been used in the design of data structures for multidimensional data for many decades. A fundamental quality metric of a space-filling curve is its “clustering number” with respect to a class of queries, which is the average number of contiguous segments on the space-filling curve that a query region can be partitioned into. We present a characterization of the clustering number of a general class of space-filling curves, as well as the first nontrivial lower bounds on the clustering number for any space-filling curve. Our results answer questions that have been open for more than 15 years.

Description

This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Xu, Pan, and Srikanta Tirthapura. "Optimality of clustering properties of space-filling curves." ACM Transactions on Database Systems (TODS) 39, no. 2 (2014): 10. DOI: 10.1145/2556686. Posted with permission.

Keywords
space filling curves, clustering, Hilbert curve, lower bound
Citation
DOI
Collections