Title

Optimality of Clustering Properties of Space-Filling Curves

Campus Units

Computer Science, Electrical and Computer Engineering

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

5-2014

Journal or Book Title

ACM Transactions on Database Systems

Volume

39

Issue

2

First Page

10

DOI

10.1145/2556686

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.

Copyright Owner

ACM

Language

en

File Format

application/pdf

This document is currently not available here.

Published Version

Share

COinS