Irregularity in multi-dimensional space-filling curves with applications in multimedia databases

Mohamed F. Mokbel, Walid G. Aref

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

A space-filling curve is a way of mapping the multi-dimensional space into the one-dimensional space. It acts like a thread that passes through every cell element (or pixel) in the N-dimensional space so that every cell is visited at least once. Thus, a space-filling curve imposes a linear order of the cells in the N-dimensional space. There are numerous kinds of space-filling curves. The difference between such curves is in their way of mapping to the one-dimensional space. Selecting the appropriate curve for any application requires a brief knowledge of the mapping scheme provided by each space-filling curve. Irregularity is proposed as a quantitative measure of the quality of the mapping of the space-filling curve. Closed formulas are developed to compute the irregularity for any general dimension D with N points in each dimension for different space-filling curves. A comparative study of different space-filling curves with respect to irregularity is conducted and results are presented and discussed. The applicability of this research in the area of multimedia databases is illustrated with a discussion of the problems that arise.

Original languageEnglish (US)
Title of host publicationInternational Conference on Information and Knowledge Management, Proceedings
EditorsH. Paques, L. Liu
Pages512-519
Number of pages8
StatePublished - Dec 1 2001
EventProceedings of the 2001 ACM CIKM: 10th International Conference on Information and Knowledge Management - Atlanta, GA, United States
Duration: Nov 5 2001Nov 10 2001

Other

OtherProceedings of the 2001 ACM CIKM: 10th International Conference on Information and Knowledge Management
CountryUnited States
CityAtlanta, GA
Period11/5/0111/10/01

Fingerprint Dive into the research topics of 'Irregularity in multi-dimensional space-filling curves with applications in multimedia databases'. Together they form a unique fingerprint.

  • Cite this

    Mokbel, M. F., & Aref, W. G. (2001). Irregularity in multi-dimensional space-filling curves with applications in multimedia databases. In H. Paques, & L. Liu (Eds.), International Conference on Information and Knowledge Management, Proceedings (pp. 512-519)