Nothing Special   »   [go: up one dir, main page]

skip to main content
article

A new algorithm for encoding and decoding the Hilbert order

Published: 01 July 2007 Publication History

Abstract

An iterative algorithm is described, based on the replication process of the Hilbert matrix, for encoding and decoding the Hilbert order. The time complexity of the proposed algorithm is smaller than those published previously, and the space complexity is bounded by a constant. Moreover, the new algorithm has a wider applicability when compared with existing algorithms for certain machine-word lengths. A new variant of the Hilbert curve is suggested to overcome a shortcoming of the traditional Hilbert curve for the mapping problem. The proposed coding algorithms for the traditional Hilbert curve are also applicable to the new variant without increasing the time and space complexities. Copyright © 2006 John Wiley & Sons, Ltd.

References

[1]
1. Peano G. Sur une courbe qui remplit toute en aire plaine. Mathematische Annaler 1890; 36.
[2]
2. Hilbert D. Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annaler 1891; 38:459-460.
[3]
3. Breinholt G, Schierz C. Algorithm 781: Generating Hilbert's space-filling curve by recursion. ACM Transactions on Mathematical Software 1998; 24(2):184-189.
[4]
4. Goodchild MF, Grandfield AW. Optimizing raster storage: An examination of four alternatives. Proceedings of the 6th International Symposium on Automated Cartography, Ottawa, ON, Canada, 1983; 400-407.
[5]
5. Gotsman C, Lindenbaum M. On the metric properties of discrete space-filling curves. Proceedings of International Conference on Pattern Recognition, vol. 3. IEEE Press: Piscataway, NJ, 1994; 98-102.
[6]
6. Gotsman C, Lindenbaum M. Euclidean Voronoi labeling on the multidimensional Grid. Pattern Recognition Letters 1995; 16:409-415.
[7]
7. Gotsman C, Lindenbaum M. On the metric properties of discrete space-filling curves. IEEE Transactions on Image Processing 1996; 5(5):794-797.
[8]
8. Jagadish HV. Linear clustering of objects with multiple attributes. ACM SIGMOD Record 1990; 19(2):332-342.
[9]
9. Song Z, Roussopoulos N. Using Hilbert curve in image storing and retrieving. Proceedings of the 2000 ACM Workshops on Multimedia, Los Angeles, CA, 2000, vol. 11. ACM Press: New York, 2000; 167-170.
[10]
10. Zhang YF. Space-filling curve ordered dither. Computers and Graphics 1998; 22(4):559-563.
[11]
11. Böhm C, Berchtold S, Keim DA. Searching in high-dimensional spaces Index structures for improving the performance of multimedia databases. ACM Computing Surveys 2001; 33(3):322-373.
[12]
12. Lu F, Zhou CH. A GIS spatial indexing approach based on hilbert ordering code. Journal of Computer-Aided Design and Computer Graphics 2001; 13(5):424-429.
[13]
13. Butz AR. Alternative algorithm for Hilbert's space-filling curve. IEEE Transactions on Computers 1971; 20:424-426.
[14]
14. Null A. Space-filling curves, or how to waste time with a plotter. Software: Practice and Experience 1971; 1:403-410.
[15]
15. Wirth N. Algorithms + Data Structures = Programs. Prentice-Hall: Englewood Cliffs, NJ, 1976.
[16]
16. Goldschlager LM. Short algorithms for space-filling curves. Software: Practice and Experience 1981; 11:99.
[17]
17. Witten IH, Wyvill B. On the generation and use of space-filling curves. Software: Practice and Experience 1983; 13:519-525.
[18]
18. Cole AJ. A note on space filling curves. Software: Practice and Experience 1983; 13:1181-1189.
[19]
19. Griffiths JG. Table-driven algorithms for generating space-filling curves. Computer-Aided Design 1985; 17(1):37-41.
[20]
20. Griffiths JG. An algorithm for displaying a class of space-filling curves. Software: Practice and Experience 1986; 16(5):403-411.
[21]
21. Sagan H. On the geometrization of the Peano curve and the arithmetization of the Hilbert curve. International Journal of Mathematical Education in Science and Technology 1992; 23(3):403-411.
[22]
22. Dickov RM. 2D L-Systems. http://forum.swarthmore.edu/advanced/robertd/lsys2d.html {April 1996}.
[23]
23. Fisher AJ. A new algorithm for generating Hilbert curves. Software: Practice and Experience 1986; 16:5-12.
[24]
24. Liu X, Schrack G. Encoding and decoding the Hilbert order. Software--Practice and Experience 1996; 26(12):1335-1346.
[25]
25. Liu X, Schrack G. An algorithm for encoding and decoding the 3-D Hilbert order. IEEE Transactions on Image Processing 1997; 6(9):1333-1337.
[26]
26. Liu X, Schrack G. A new ordering strategy applied to spatial data processing. International Journal of Geographical Information Science 1998; 12(1):3-22.
[27]
27. Bartholdi JJ III, Goldsman P. Vertex-labeling algorithms for the Hilbert spacefilling curve. Software--Practice and Experience 2001; 31(5):395-408.
[28]
28. Lin SY, Chen CS, Liu L, Huang CH. Tensor product formulation for Hilbert space-filling curves. Proceedings of the International Conference on Parallel Processing (ICPP 2003), Kaohsiung, Taiwan, 6-9 October 2003. IEEE Computer Society Press: Los Alamitos, CA, 2003; 99-106.
[29]
29. Gupta SKS, Huang CH, Sadayappan P, Johnson RW. A framework for generating distributed-memory parallel programs for block recursive algorithms. Journal of Parallel and Distributed Computing 1996; 34(2):137-153.

Cited By

View all
  • (2020)Locality properties of 3D data orderings with application to parallel molecular dynamics simulationsInternational Journal of High Performance Computing Applications10.1177/109434201984628233:5(998-1018)Online publication date: 17-Jun-2020
  • (2019)Cache-oblivious High-performance Similarity JoinProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3319859(87-104)Online publication date: 25-Jun-2019
  • (2017)Cache-oblivious Matrix Multiplication for Exact TU FactorisationProceedings of the International Workshop on Parallel Symbolic Computation10.1145/3115936.3115949(1-10)Online publication date: 23-Jul-2017
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Software
Software  Volume 37, Issue 8
July 2007
107 pages
ISSN:0038-0644
EISSN:1097-024X
Issue’s Table of Contents

Publisher

John Wiley & Sons, Inc.

United States

Publication History

Published: 01 July 2007

Author Tags

  1. Hilbert curve
  2. decoding
  3. encoding
  4. space-filling curve

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2020)Locality properties of 3D data orderings with application to parallel molecular dynamics simulationsInternational Journal of High Performance Computing Applications10.1177/109434201984628233:5(998-1018)Online publication date: 17-Jun-2020
  • (2019)Cache-oblivious High-performance Similarity JoinProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3319859(87-104)Online publication date: 25-Jun-2019
  • (2017)Cache-oblivious Matrix Multiplication for Exact TU FactorisationProceedings of the International Workshop on Parallel Symbolic Computation10.1145/3115936.3115949(1-10)Online publication date: 23-Jul-2017
  • (2012)Computational and methodological aspects of terrestrial surface analysis based on point cloudsComputers & Geosciences10.5555/2899073.289911342:C(64-70)Online publication date: 1-May-2012
  • (2011)All-nearest-neighbors finding based on the Hilbert curveExpert Systems with Applications: An International Journal10.1016/j.eswa.2010.12.07738:6(7462-7475)Online publication date: 1-Jun-2011

View Options

View options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media