Optimality of Clustering Properties of Space-Filling Curves

Date
2014-05-01
Authors
Xu, Pan
Tirthapura, Srikanta
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Computer Science
Organizational Unit
Journal Issue
Series
Department
Computer ScienceElectrical and Computer Engineering
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.

Comments

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.

Description
Keywords
Citation
DOI
Collections