[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Clustering Analyses of Two-Dimensional Space-Filling Curves: Hilbert and z-Order Curves

  • Original Research
  • Published:
SN Computer Science Aims and scope Submit manuscript

Abstract

A discrete space-filling curve provides a linear traversal or indexing of a multi-dimensional grid space. This paper presents two analytical studies on clustering analyses of the 2-dimensional Hilbert and z-order curve families. The underlying measure is the mean number of cluster over all identically shaped subgrids. We derive the exact formulas for the clustering statistics for the 2-dimensional Hilbert and z-order curve families. The two exact analytical results yield: (1) a comparison of their relative performances with respect to this measure: when the grid-order is sufficiently larger than the subgrid-order (typical scenario for most applications), Hilbert curve family performs significantly better than z-order curve family, and (2) good agreements with asymptotic analyses of continuous space-filling curves and of (non-continuous) z-order curve in the literature.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  1. Alber J, Niedermeier R. On multi-dimensional curves with Hilbert property. Theory Comput Syst. 2000;33(4):295–312.

    Article  MathSciNet  MATH  Google Scholar 

  2. Asano T, Ranjan D, Roos T, Welzl E, Widmayer P. Space-filling curves and their use in the design of geometric data structures. Theor Comput Sci. 1997;181(1):3–15.

    Article  MathSciNet  MATH  Google Scholar 

  3. Bader M. Space-Filling Curves—An Introduction with Applications in Scientific Computing, vol. 9. Texts in Computational Science and Engineering. Berlin: Springer; 2013.

    MATH  Google Scholar 

  4. Ban X, Goswami M, Zeng W, Gu X, Gao J. Topology dependent space filling curves for sensor networks and applications. In: Proceedings of the IEEE INFOCOM 2013, Turin, Italy, April 14–19, 2013. New York: IEEE; 2013. p. 2166–74.

  5. Böhm C, Berchtold S, Keim DA. Searching in high-dimensional spaces—index structures for improving the performance of multimedia databases. ACM Comput Surv. 2001;33(3):322–73.

    Article  Google Scholar 

  6. Chen H-L, Chang Y-I. Neighbor-finding based on space-filling curves. Inf Syst. 2005;30(3):205–26.

    Article  Google Scholar 

  7. Dai HK, Su HC. Approximation and analytical studies of inter-clustering performances of space-filling curves. In: Proceedings of the international conference on discrete random walks (Discrete mathematics and theoretical computer science, vol. AC (2003)). Strasbourg, France: Discrete Mathematics and Theoretical Computer; 2003. p. 53–68.

  8. Dai HK, Su HC. On the locality properties of space-filling curves. In: Ibaraki T, Katoh N, Ono H, editors. Lecture notes in computer science (2906): algorithms and computation: 14th international symposium. ISAAC 2003 proceedings. Berlin: Springer; 2003. p. 385–94.

  9. Dai HK, Su HC. Norm-based locality measures of two-dimensional Hilbert curves. In: Dondi R, Fertin G, Mauri G, editors. Algorithmic aspects in information and management—11th international conference. AAIM 2016, Bergamo, Italy, July 18–20, 2016, Proceedings, volume 9778 of Lecture Notes in Computer Science. Berlin: Springer; 2016. p. 14–25.

  10. Dai HK, Su HC. On norm-based locality measures of 2-dimensional discrete Hilbert curves. In: Dang TK, Küng J, Takizawa M, Chung TM, editors. Lecture notes in computer science (12466): future data and security engineering. 7th International conference, FDSE 2020, Quy Nhon, Vietnam, November 25–27, 2020, proceedings. Berlin: Springer; 2020. p. 169–84.

  11. Gaede V, Günther O. Multidimensional access methods. ACM Comput Surv. 1998;30(2):170–231.

    Article  Google Scholar 

  12. Gotsman C, Lindenbaum M. On the metric properties of discrete space-filling curves. IEEE Trans Image Process. 1996;5(5):794–7.

    Article  Google Scholar 

  13. He Z, Owen AB. Extensible grids: uniform sampling on a space filling curve. J R Stat Soc Ser B. 2016;78(4):917–31.

    Article  MathSciNet  MATH  Google Scholar 

  14. Jagadish HV. Analysis of the Hilbert curve for representing two-dimensional space. Inf Process Lett. 1997;62(1):17–22.

    Article  MathSciNet  MATH  Google Scholar 

  15. Kaddoura M, Ou C-W, Ranka S. Partitioning unstructured computational graphs for non-uniform and adaptive environments. IEEE Parallel Distrib Technol. 1995;3(3):63–9.

    Article  Google Scholar 

  16. Kinney N, Hickman M, Anandakrishnan R, Garner HR. Crossing complexity of space-filling curves reveals entanglement of S-phase DNA. Public Libr Sci One. 2020;15(8):1–20.

  17. Lawder JK. The application of space-filling curves to the storage and retrieval of multi-dimensional data. PhD thesis, Birkbeck College, University of London, December 1999.

  18. Lempel A, Ziv J. Compression of two-dimensional images. In: Apostolico A, Galil Z, editors. Combinatorial algorithms on words, vol. F12. ASI series. Berlin: Springer; 1984. p. 141–56.

    Google Scholar 

  19. Mitchison G, Durbin R. Optimal numberings of an \({N} \times {N}\) array. SIAM J Algebraic Discrete Methods. 1986;7(4):571–82.

    Article  MathSciNet  MATH  Google Scholar 

  20. Moon B, Jagadish HV, Faloutsos C, Saltz JH. Analysis of the clustering properties of the Hilbert space-filling curve. IEEE Trans Knowl Data Eng. 2001;13(1):124–41.

    Article  Google Scholar 

  21. Pérez A, Kamata S, Kawaguchi E. Peano scanning of arbitrary size images. In: Proceedings of the international conference on pattern recognition. New York: IEEE Computer Society; 1992. p. 565–8.

  22. Platzman LK, Bartholdi JJ III. Spacefilling curves and the planar travelling salesman problem. J ACM. 1989;36(4):719–37.

    Article  MathSciNet  MATH  Google Scholar 

  23. Sagan H. Space-filling curves. New York: Springer; 1994.

    Book  MATH  Google Scholar 

  24. Wang C, Jiang H, Dong Y. Connectivity-based space filling curve construction algorithms in high genus 3D surface WSNs. ACM Trans Sens Netw. 2016;12(3):22:1-22:29.

    Article  Google Scholar 

  25. Xu P, Tirthapura S. On the optimality of clustering through a space filling curve. In: PODS ’12 proceedings of the 31st symposium on principles of database systems. New York: Association for Computing Machinery; 2012. p. 215–24.

  26. Xu P, Tirthapura S. Optimality of clustering properties of space-filling curves. ACM Trans Database Syst. 2014;39(2):1–27.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Funding

This study was not supported by any funding.

Author information

Authors and Affiliations

  1. Computer Science Department, Oklahoma State University, Stillwater, OK, 74078, USA

    H. K. Dai

  2. Department of Computer Science, Arkansas State University, Jonesboro, AR, 72401, USA

    H. C. Su

Authors
  1. H. K. Dai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. H. C. Su
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to H. K. Dai.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is part of the topical collection “Future Data and Security Engineering 2021” guest edited by Tran Khanh Dang.

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dai, H.K., Su, H.C. Clustering Analyses of Two-Dimensional Space-Filling Curves: Hilbert and z-Order Curves. SN COMPUT. SCI. 4, 8 (2023). https://doi.org/10.1007/s42979-022-01320-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s42979-022-01320-9

Keywords

Search

Navigation