Optimality of clustering properties of space-filling curves

Pan Xu, Srikanta Tirthapura

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

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.

Original languageEnglish (US)
Article numbera10
JournalACM Transactions on Database Systems
Volume39
Issue number2
DOIs
StatePublished - May 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems

Keywords

  • Clustering
  • Hilbert curve
  • Lower bound
  • Space-filling curves
  • Z-curve

Fingerprint

Dive into the research topics of 'Optimality of clustering properties of space-filling curves'. Together they form a unique fingerprint.

Cite this