@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",

}