Optimality of Clustering Properties of Space-Filling Curves
Computer Science, Electrical and Computer Engineering
Journal or Book Title
ACM Transactions on Database Systems
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.
Xu, Pan and Tirthapura, Srikanta, "Optimality of Clustering Properties of Space-Filling Curves" (2014). Electrical and Computer Engineering Publications. 168.