Abstract
The efficiency of many algorithms in parallel processing, computational geometry, image processing, and several other fields relies on “locality-preserving” indexing schemes for meshes. We concentrate on the case where the maximum distance between two mesh nodes indexed i and j shall be a slow-growing function of i — j (using the Euclidean, the maximum, and the Manhattan metric). In this respect, space-filling, self-similar curves like the Hilbert curve are superior to simple indexing schemes like “row-major.” We present new tight results on 2-D and 3-D Hilbert indexings which are easy to generalize to a quite large class of curves. We then present a new indexing scheme we call H- indexing, which has superior locality. For example, with respect to the Euclidean metric the H-indexing provides locality approximately 50% better than the usually used Hilbert indexing. This answers an open question of Gotsman and Lindenbaum. In addition, H-indexings have the useful property to form a Hamiltonian cycle and they are optimally locality-preserving among all cyclic indexings.
Generalizations are straightforward.
Preview
Unable to display preview. Download preview PDF.
References
T. Asano, D. Ranjan, T. Roos, E. WeIzI, and P. Widmayer. Space filling curves and their use in the design of geometric data structures. In LATIN '95: theoretical informatics: second Latin American Symposium, number 911 in LNCS, page 36ff, Valparaiso, Chile, April 1995.
G. Chochia and M. Cole. Recursive 3D mesh indexings with improved locality. Technical report, University of Edinburgh, 1997. short version to be published in HPCN'97.
G. Chochia, M. Cole, and T. Heywood. Implementing the hierarchical PRAM on the 2D mesh: Analyses and experiments. In Symposium on Parallel and Distributed Processing, pages 587–595, Los Alamitos, Ca., USA, Oct. 1995. IEEE Computer Society Press.
C. Gotsman and M. Lindenbaum. On the metric properties of discrete space-filling curves. IEEE Transactions on Image Processing, 5(5):794–797, May 1996.
C. Kaklamanis and G. Persiano. Branch-and-bound and backtrack search on mesh-connected arrays of processors. Mathematical Systems Theory, 27:471–489, 1994.
R. Miller and Q. F. Stout. Mesh computer algorithms for computational geometry. IEEE Transactions on Computers, 38(3):321–340, March 1989.
G. Mitchison and R. Durbin. Optimal numberings of an N x N array. SIAM J. Alg. Disc. Meth., 7(4):571–582, October 1986.
R. Niedermeier, K. Reinhard, and P. Sanders. Towards optimal locality in mesh-indexings. Technical Report IB 12/97, University of Karlsruhe, 1997.
H. Sagan. Space-Filling Curves. Universitext. Springer-Verlag, 1994.
P. Sanders and T. Hansch. On the efficient implementation of massively parallel quicksort. In 4th International Symposium on Solving Irregularly Structured Problems in Parallel, LNCS. Springer, 1997. to appear. *** DIRECT SUPPORT *** A0008123 00010
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Niedermeier, R., Reinhardt, K., Sanders, P. (1997). Towards optimal locality in mesh-indexings. In: Chlebus, B.S., Czaja, L. (eds) Fundamentals of Computation Theory. FCT 1997. Lecture Notes in Computer Science, vol 1279. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0036198
Download citation
DOI: https://doi.org/10.1007/BFb0036198
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63386-0
Online ISBN: 978-3-540-69529-5
eBook Packages: Springer Book Archive