SFCGen: A framework for efficient generation of multi-dimensional space-filling curves by recursion

ABSTRACT

Because they are continuous and self-similar, space-filling curves have been widely used in mathematics to transform multi-dimensional problems into one-dimensional forms. For scientific applications, reordering computation by certain space-filling curves can significantly improve data reuse because of the locality properties of these curves. However, when space-filling curves are used in programs for reordering data, traversal or indexing of the curves must be efficient. To address this problem, we present the table-driven framework SFCGen to efficiently generate multi-dimensional space-filling curves on the fly. The framework is general and easy enough to be used in any application that can be partitioned recursively in multiple dimensions. We describe a movement specification table, a universal turtle algorithm to enumerate points along a space-filling curve, a table-based indexing algorithm to transform coordinates of a point into its position along the curve and an algorithm to pregenerate the table automatically. As examples, we show how high-dimensional Hilbert, Morton, and Peano curves and a two-dimensional Sierpiński curve can be generated with our algorithms. We present performance results for Hilbert, Morton, and Peano curves and compare the efficiency of our curve generation algorithm with the most recent work on generating Hilbert curves. Our experimental results on three modern microprocessor-based platforms show that SFCGen performs up to 63&percent; faster than the most recent recursive algorithm on 2D curve generation and up to a factor of 132 faster than two previous byte-oriented non-recursive implementations. On curve indexing, SFCGen performs as much as a factor of three faster than the byte-oriented implementation. Our results on 4D space-filling curves also show that SFCGen scales very well with curve level for higher dimensional spaces.

REFERENCES

• 1: Abel, D. J. and Mark, D. M. 1990. A comparative analysis of some two-dimensional orderings. Int. J. Geog. Info. Syst. 4, 1, 21--31.
• 2: C. J. Alpert , A. B. Kahng, Multi-way partitioning via spacefilling curves and dynamic programming, Proceedings of the 31st annual conference on Design automation, p.652-657, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196603]
• 3: John J. Bartholdi, III , Paul Goldsman, Vertex-labeling algorithms for the Hilbert spacefilling curve, Software—Practice & Experience, v.31 n.5, p.395-408, April 2001 [doi>10.1002/spe.376]
• 4: Michael Bertilsson , Ernest F. Brickell , Ingemar Ingemarsson, Cryptanalysis of video encryption based on space-filling curves, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.403-411, November 1990, Houthalen, Belgium
• 5: Bially, T. 1969. Space-filling curves: Their generation and their application to bandwidth reduction. IEEE Trans. Info. Theory IT-15, 6 (Nov.), 658--664.
• 6: Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001 [doi>10.1145/502807.502809]
• 7: 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]
• 8: S. Browne , J. Dongarra , N. Garner , K. London , P. Mucci, A scalable cross-platform infrastructure for application performance tuning using hardware counters, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.42-es, November 04-10, 2000, Dallas, Texas, United States
• 9: Butz, A. R. 1968. Space filling curves and mathematical programming. Information and Control 12, 314--330.
• 10: Butz, A. R. 1969. Convergence with Hilbert's space filling curve. J. Comput. Syst. Sci. 3, 2, 128--146.
• 11: Butz, A. R. 1971. Alternative algorithm for Hilbert's space-filling curve. IEEE Trans. Comput. C-20, 4 (Apr.), 424--426.
• 12: Siddhartha Chatterjee , Alvin R. Lebeck , Praveen K. Patnala , Mithuna Thottethodi, Recursive array layouts and fast parallel matrix multiplication, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.222-231, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305645]
• 13: Cole, A. J. 1981. A note on space filling curves. Software--Practice and Experience 13, 12 (Dec.), 1181--1189.
• 14: Drakopoulos, V., Tziovaras, A., Böhm, A., and Dalla, L. 1999. Fractal interpolation techniques for the generation of space-filling curves. In Hellenic European Research on Computer Mathematics and Its Applications, E. A. Lipitakis, Ed. LEA, 843--850.
• 15: Jeremy D. Frens , David S. Wise, Auto-blocking matrix-multiplication or tracking BLAS3 performance from source code, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.206-216, June 18-21, 1997, Las Vegas, Nevada, United States
• 16: Goldschlager, L. M. 1981. Short algorithms for space-filling curves. Software--Practice and Experience 11, 1 (Jan.), 99--100.
• 17: Hilbert, D. 1891. Über die stetige abbildung einer linie auf ein flachenstück. Math. Ann. 38, 459--460.
• 18: Y. Charlie Hu , Alan Cox , Willy Zwaenepoel, Improving fine-grained irregular shared-memory benchmarks by data reordering, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.33-es, November 04-10, 2000, Dallas, Texas, United States
• 19: 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
• 20: Guohua Jin , John Mellor-Crummey , Robert Fowler, Increasing temporal locality with skewing and recursive blocking, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.43-43, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582077]
• 21: Akhil Kumar, A Study of Spatial Clustering techniques, Proceedings of the 5th International Conference on Database and Expert Systems Applications, p.57-71, September 07-09, 1994
• 22: S. Kuo , M. Winslett , Y. Cho , J. Lee , Y. Chen, Efficient input and output for scientific simulations, Proceedings of the sixth workshop on I/O in parallel and distributed systems, p.33-44, May 05-05, 1999, Atlanta, Georgia, United States [doi>10.1145/301816.301828]
• 23: Lamarque, C. H. and Robert, F. 1996. Image analysis using space-filling curves and 1D wavelet bases. Pattern Recognition 29, 8, 1309--1322.
• 24: 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]
• 25: Lindenmayer, A. 1968. Mathematical models for cellular interaction in development, parts I and II. J. Theore. Biol. 18, 280--315.
• 26: Yossi Matias , Adi Shamir, A Video Scrambling Technique Based On Space Filling Curves, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.398-417, August 16-20, 1987
• 27: 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]
• 28: Moghaddam, B., Hintz, K. J., and Stewart, C. V. 1991. Space-filling curves for image compression. In Proceedings of the SPIE. 414--421.
• 29: Mohamed F. Mokbel , Walid G. Aref, Irregularity in multi-dimensional space-filling curves with applications in multimedia databases, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502671]
• 30: Mohamed F. Mokbel , Walid G. Aref , Ibrahim Kamel, Analysis of Multi-Dimensional Space-Filling Curves, Geoinformatica, v.7 n.3, p.179-209, September 2003 [doi>10.1023/A:1025196714293]
• 31: Moore, D. 2000. http://www.caam.rice.edu/~dougm/twiddle/Hilbert.
• 32: Morton, G. M. 1966. A computer oriented geodetic data base and a new technique in file sequencing. Technique Report, IBM, Canada.
• 33: Musgrave, K. 1991. A Peano curve generation algorithm. In Graphics Gems II, J. Arvo, Ed. Academic Press, San Diego, CA, 25.
• 34: Ohno, Y. and Ohyama, K. 1991. A catalog of symmetric self-similar space-filling curves. J. Recreational Math. 23, 161--173.
• 35: Peano, G. 1890. Sur une courbe qui remplit toute une aire plane. Mathematishe Annalen 36, 157--160.
• 36: Loren K. Platzman , John J. Bartholdi, III, Spacefilling curves and the planar travelling salesman problem, Journal of the ACM (JACM), v.36 n.4, p.719-737, Oct. 1989 [doi>10.1145/76359.76361]
• 37: Prusinkiewicz, P., Lindenmayer, A., and Fracchia, F. D. 1991. Synthesis of space-filling curves on the square grid. In Fractals in the Fundamental and Applied Sciences, H. O. Peitgen, J. M. Henriques, and L. F. Penedo, Eds. Elsevier Science Publisher BV, Amsterdam, The Netherlands, 341--366.
• 38: Sagan, H. 1992. On the geometrization of the Peano curve and the arithmetization of the Hilbert curve. Int. J. Math. Educ. Sci. Tech. 23, 403--411.
• 39: Sagan, H. 1993. A three-dimensional Hilbert curve. Int. J. Math. Educ. Sci. Tech. 24, 541--545.
• 40: Sagan, H. 1994. Space-Filling Curves. Springer-Verlag, New York, NY.
• 41: Sierpiński, W. 1912. Sur une nouvelle courbe countinue qui remplit toute une aire plane. Bull. Acad. Sci. de Cracovie (Sci. math. et nat., Série A), 462--478.
• 42: Stevens, R. J., Lehar, A. F., and Preston, F. H. 1983. Manipulation and presentation of multidimensional image data using the Peano scan. IEEE Trans. Pattern Anal. Mach. Intell. 5, 520--526.
• 43: Luiz Velho , Jonas de Miranda Gomes, Digital halftoning with space filling curves, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.81-90, July 1991
• 44: Witten, I. H. and Wyvill, B. 1983. On the generation and use of space-filling curves. Software--Practice and Experience 13, 519--525.
• 45: 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:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Line and curve generation

General Terms:
Algorithms, Design, Performance

Keywords:
Space-filling curve