Title
Optimality of Clustering Properties of Space-Filling Curves
Campus Units
Computer Science, Electrical and Computer Engineering
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
5-2014
Journal or Book Title
ACM Transactions on Database Systems
Volume
39
Issue
2
First Page
10
DOI
10.1145/2556686
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.
Copyright Owner
ACM
Copyright Date
2014
Language
en
File Format
application/pdf
Recommended Citation
Xu, Pan and Tirthapura, Srikanta, "Optimality of Clustering Properties of Space-Filling Curves" (2014). Electrical and Computer Engineering Publications. 168.
https://lib.dr.iastate.edu/ece_pubs/168
Comments
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.