@inproceedings{f67d242b744b4c07bf01ebb96d05c181,
title = "On the optimality of clustering properties of space filling curves",
abstract = "Space filling curves have for long been used in the design of data structures for multidimensional data. 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 non-trivial lower bounds on the clustering number for any space filling curve. Our results also answer an open problem that was posed by Jagadish in 1997.",
keywords = "clustering, hilbert curve, lower bound, space filling curve",
author = "Pan Xu and Srikanta Tirthapura",
year = "2012",
doi = "10.1145/2213556.2213587",
language = "English (US)",
isbn = "9781450312486",
series = "Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems",
pages = "215--224",
booktitle = "PODS '12 - Proceedings of the 31st Symposium on Principles of Database Systems",
note = "31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '12 ; Conference date: 21-05-2012 Through 23-05-2012",
}