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

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 is the area of multimedia databases is illustrated with a discussion of the problems that arise.

REFERENCES

• 1: D. J. Abel and D. M. Mark. A comparative analysis of some two-dimensional orderings. Intl. Journal of Geographical Information Systems, 4(1):21-31, 1990.
• 2: D. J. Abel and J. Smith. A data structure and algorithm based on a linear key for a rectangle retrieval problem. Computer Vision Graphics Image Processing, 24:1I13, 1983.
• 3: C. Akinlar, W. G. Aref, I. Kamel, and S. Mukherjee. Automatic disks: The building block for a scalable distributed file system. In In PTOC. of the 5th Intl. Workshop on Multimedia Information Systems, MIS, Palm Springs Desert, Oct. 1999.
• 4: Jochen Alber , Rolf Niedermeier, On Multi-dimensional Hilbert Indexings, Proceedings of the 4th Annual International Conference on Computing and Combinatorics, p.329-338, August 12-14, 1998
• 5: Walid G. Aref , Ibrahim Kamel, On Multi-dimensional Sorting Orders, Proceedings of the 11th International Conference on Database and Expert Systems Applications, p.774-783, September 04-08, 2000
• 6: W. G. Aref , I. Kamel , S. Ghandeharizadeh, Disk Scheduling in Video Editing Systems, IEEE Transactions on Knowledge and Data Engineering, v.13 n.6, p.933-950, November 2001 [doi>10.1109/69.971188]
• 7: W. G. Aref, M. F. Mokbel, and I. Kamel. On the analysis of high-dimensional space-filling curves. Technical report, Computer Sciences Department, Purdue University, IN, Mar. 2001.
• 8: Tetsuo Asano , Desh Ranjan , Thomas Roos , Emo Welzl , Peter Widmayer, Space-filling curves and their use in the design of geometric data structures, Theoretical Computer Science, v.181 n.1, p.3-15, July 15, 1997 [doi>10.1016/S0304-3975(96)00259-9]
• 9: Christian Böhm , Gerald Klump , Hans-Peter Kriegel, XZ-Ordering: A Space-Filling Curve for Objects with Spatial Extension, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.75-90, July 20-23, 1999
• 10: Greg Breinholt , Christoph Schierz, Algorithm 781: generating Hilbert's space-filling curve by recursion, ACM Transactions on Mathematical Software (TOMS), v.24 n.2, p.184-189, June 1998 [doi>10.1145/290200.290219]
• 11: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• 12: A. J. Cole. A note on space filling curves. Software-Practice and Experience, SPE, 13(12):1181-1189, 1983.
• 13: A. J. Cole. Halftoning without dither or edge enhancement. The Visual Computer, 7-232-246, 1991.
• 14: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 15: C. Faloutsos, Gray Codes for Partial Match and Range Queries, IEEE Transactions on Software Engineering, v.14 n.10, p.1381-1393, October 1988 [doi>10.1109/32.6184]
• 16: Christos Faloutsos, Analytical results on the quadtree decomposition of arbitrary rectangles, Pattern Recognition Letters, v.13 n.1, p.31-40, Jan. 1992 [doi>10.1016/0167-8655(92)90112-D]
• 17: Christos Faloutsos , Yi Rong, DOT: A Spatial Access Method Using Fractals, Proceedings of the Seventh International Conference on Data Engineering, p.152-159, April 08-12, 1991
• 18: C. Faloutsos , S. Roseman, Fractals for secondary key retrieval, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.247-252, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73746]
• 19: R. A. Finkel and J. L. Bently. Quad trees: a data structure for retrieval on composite keys. Acta Informatica, 4:1-9, 1974.
• 20: Garth A. Gibson , David F. Nagle , Khalil Amiri , Fay W. Chang , Eugene M. Feinberg , Howard Gobioff , Chen Lee , Berend Ozceri , Erik Riedel , David Rochberg , Jim Zelenka, File server scaling with network-attached secure disks, Proceedings of the 1997 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.272-284, June 15-18, 1997, Seattle, Washington, United States
• 21: L. M. Goldschlager. Short algorithms for space-filling curves. Software-Practice and Experience, SPE, 11(1):99-100, 1981.
• 22: F. Gray. Pulse code communications. US Patent 2632058, 1953.
• 23: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 24: D. Hilbert. Ueber stetige abbildung einer linie auf ein flashenstuck. Mathematishe Annalen, pages 459460, 1891.
• 25: H. V. Jagadish, Linear clustering of objects with multiple attributes, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.332-342, May 23-26, 1990, Atlantic City, New Jersey, United States
• 26: Ibrahim Kamel , Christos Faloutsos, On packing R-trees, Proceedings of the second international conference on Information and knowledge management, p.490-499, November 01-05, 1993, Washington, D.C., United States [doi>10.1145/170088.170403]
• 27: Ibrahim Kamel , Christos Faloutsos, Hilbert R-tree: An Improved R-tree using Fractals, Proceedings of the 20th International Conference on Very Large Data Bases, p.500-509, September 12-15, 1994
• 28: R. H. Katz. High performance network- and channel-attached storage. Proceedings of IEEE, 80(8), Aug. 1992.
• 29: Jonathan K. Lawder , Peter J. H. King, Using Space-Filling Curves for Multi-dimensional Indexing, Proceedings of the 17th British National Conferenc on Databases: Advances in Databases, p.20-35, July 03-05, 2000
• 30: J. K. Lawder , P. J. H. King, Querying multi-dimensional data indexed using the Hilbert space-filling curve, ACM SIGMOD Record, v.30 n.1, p.19-24, March 2001 [doi>10.1145/373626.373678]
• 31: Swanwa Liao , Mario A. Lopez , Scott T. Leutenegger, High Dimensional Similarity Search With Space Filling Curves, Proceedings of the 17th International Conference on Data Engineering, p.615-622, April 02-06, 2001
• 32: John Mellor-Crummey , David Whalley , Ken Kennedy, Improving memory hierarchy performance for irregular applications, Proceedings of the 13th international conference on Supercomputing, p.425-433, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305228]
• 33: Bongki Moon , H. v. Jagadish , Christos Faloutsos , Joel H. Saltz, Analysis of the Clustering Properties of the Hilbert Space-Filling Curve, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.124-141, January 2001 [doi>10.1109/69.908985]
• 34: E. H. Moore. On certain crinkly curves. iPrans. Am. Math Sot., pages 72-90, 1900.
• 35: G. Morton. A computer oriented geodetic data base and a new technique in file sequences. IBM, 1966.
• 36: Rolf Niedermeier , Klaus Reinhardt , Peter Sanders, Towards Optimal Locality in Mesh-Indexings, Proceedings of the 11th International Symposium on Fundamentals of Computation Theory, p.364-375, September 01-03, 1997
• 37: R. Niedermeier and P. Sanders. On the manhattan-distance between points on space-filling mesh-indexing. Technical Report IB 18/96, Universitat Karlsruhe, Fakultat fur Informatik, May 1996.
• 38: Jack A. Orenstein, Spatial query processing in an object-oriented database system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.326-336, May 28-30, 1986, Washington, D.C., United States
• 39: J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588037]
• 40: Chao-Wei Ou , Manoj Gunwani , Sanjay Ranka, Architecture-independent locality-improving transformations of computational graphs embedded in k-dimensions, Proceedings of the 9th international conference on Supercomputing, p.289-298, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224573]
• 41: G. Peano. Sur une courbe qui remplit toute une air plaine. Mathematishe Annalen, 36:157-160, 1890.
• 42: H. Sagan. Space Filling Curves. Springer, Berlin, 1994.
• 43: Kenneth C. Sevcik , Nick Koudas, Filter Trees for Managing Spatial Data over a Range of Size Granularities, Proceedings of the 22th International Conference on Very Large Data Bases, p.16-27, September 03-06, 1996
• 44: W. Sierpinski. Sur une nouvelle courbe qui remplit toute une aire plaine. Bull. Acad. Sci. Cracouie, SerieA, pages 462478, 1912.
• 45: Mithuna Thottethodi , Siddhartha Chatterjee , Alvin R. Lebeck, Tuning Strassen's matrix multiplication for memory efficiency, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-14, November 07-13, 1998, San Jose, CA
• 46: H. Tropf and H.Herzog. Multidimensional range search in dynamically balanced trees. Angewandte Informatik, pages 71-77, 1981.
• 47: Luiz Velho , Jonas de Miranda Gomes, Digital halftoning with space filling curves, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.81-90, July 1991
• 48: Luiz Velho , Jonas Gomes, Stochastic screening dithering with adaptive clustering, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.273-276, September 1995 [doi>10.1145/218380.218452]
• 49: M. White. N-trees: Large ordered indexes for multi-dimensional space. statistical research division. US Bureau of the Census, 1980.
• 50: I. Witten and M. Neal. Using peano curves for bilevel display of continuous tone images. IEEE Computer Graphics and Applications, pages 47-52, 1982.
• 51: I. Witten and B. Wyvill. On the generation and use of space-filling curves. Software-Practice and Experience, 3:519-525, 1983.
• 52: H. Zhang and S. Liu. Order of pixel traversal and parallel volume ray-tracing on the distributed shared volume buffer. Eurographics Worlcshop on Visualization, 1995.
• 53: Yuefeng Zhang , Robert E. Webber, Space diffusion: an improved parallel halftoning technique using space-filling curves, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.305-312, September 1993 [doi>10.1145/166117.166156]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Multimedia databases

General Terms:
Algorithms, Performance, Theory