Optimality of Clustering Properties of Space-Filling Curves
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.
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.