OPEN ACCESS
Space-filling curves are widely used in many fields of computer science in which the locality preserving is often seen as the criterion to select the curve type working in an application. This is why the Hilbert curve, as the best locality preserving curve, is mainly used. However, are there other curves who preserve the locality as well as to the Hilbert curve ? In this paper, we propose a flexible method for constructing a family of multidimensional spacefilling curves whose locality preserving level is comparable or better than that of the Hilbert curve. Comparative experimental tests tend to confirm these results. Note that the evidence on the validity of our proposal is advanced, its implementation is illustrated through numerous examples.
RÉSUMÉ
Les courbes remplissant l’espace sont largement utilisées dans plusieurs domaines de l’informatique où la conservation de la localité est souvent considérée comme le critère pour choisir le type de courbe opérant dans une application. C’est pourquoi, la courbe de Hilbert, en qualité de courbe préservant au mieux la localité, reste majoritairement employée. Cependant, existe-t-il d’autres courbes vérifiant un niveau de localité comparable à la courbe de Hilbert ? Dans cet article, nous proposons une méthode flexible permettant de construire une famille de courbes - remplissant un espace multidimensionnel - de niveau de localité comparable à la courbe de Hilbert et parfois meilleur. Des tests expérimentaux comparatifs tendent à confirmer ces résultats. Notons que des éléments de preuve sur la validité de notre proposition sont avancés, sa mise en œuvre est illustrée à travers de nombreux exemples.
space-filling curve, fractal, Hilbert curve, locality, primitive pattern, generalization
MOTS-CLÉS
courbe remplissant l’espace, fractal, courbe de Hilbert, localité, motif primitif, gé-néralisation
Angiulli F., Pizzuti C. (2005). An approximate algorithm for top-k closest pairs join query in large high dimensional data. Data & Knowledge Engineering, vol. 53, no 3, p. 263–281.
Asano T., Ranjan D., Roos T., Welzl E., Widmayer P. (1997). Space-filling curves and their use in the design of geometric data structures. Theoretical Computer Science, vol. 181, no 1, p. 3–15.
Bially T. (1969, novembre). Space-filling curves: Their generation and their application to bandwidth reduction. Information Theory, IEEE Transactions on, vol. 15, no 6, p. 658 - 664.
Bitner J., Ehrlich G., Reingold E. (1976). Efficient generation of the binary reflected gray code and its applications. Communications of the ACM, vol. 19, no 9, p. 517–521.
Butz A. (1969). Convergence with hilbert’s space filling curve. Journal of Computer and System Sciences, vol. 3, no 2, p. 128–146.
Butz A. (1971). Alternative algorithm for hilbert’s space-filling curve. IEEE Transactions on Computers, vol. 20, no 4, p. 424–426.
Chen H., Chang Y. (2011). All-nearest-neighbors finding based on the hilbert curve. Expert Systems with Applications.
Ebrahim Y., Ahmed M., Abdelsalam W., Chau S. (2009). Shape representation and description using the hilbert curve. Pattern Recognition Letters, vol. 30, no 4, p. 348–358.
Faloutsos C., Roseman S. (1989). Fractals for secondary key retrieval. In Proceedings of the eighth acm sigact-sigmod-sigart symposium on principles of database systems, p. 247–252. New York, NY, USA, ACM. Consulté sur http://doi.acm.org/10.1145/73721.73746
Franco P., Nguyen G., Mullot R., Ogier J. (2012). Space-filling curve for image dynamical indexing. In 27th international symposium on computer and information sciences, p. 311–319. Paris, France, Springer.
Gotsman C., Lindenbaum M. (1996). On the metric properties of discrete space-filling curves. IEEE Transactions on Image Processing, vol. 5, no 5, p. 794–797.
Hilbert D. (1891). Über die stetige abbildung einer linie auf ein flächenstück. Mathematische Annalen, vol. 38, no 3, p. 459–460.
Lawder J. (2000). The application of space-filling curves to the storage and retrieval of multidimensional data. Thèse de doctorat non publiée, University of London.
Lawder J., King P. (2000). Using space-filling curves for multi-dimensional indexing. Advances in Databases, p. 20–35.
Lawder J., King P. (2001). Using state diagrams for hilbert curve mappings. International Journal of Computer Mathematics, vol. 78, no 3, p. 327–342.
Lera D., Sergeyev Y. (2010). Lipschitz and hölder global optimization using space-filling curves. Applied numerical mathematics, vol. 60, no 1-2, p. 115–129.
Liang J., Chen C., Huang C., Liu L. (2008). Lossless compression of medical images using hilbert space-filling curves abstract. Computerized Medical Imaging and Graphics, vol. 32, no 3, p. 174–182.
Liu X. (2004). Four alternative patterns of the hilbert curve. Applied mathematics and computation, vol. 147, no 3, p. 741–752.
Mitchison G., Durbin R. (1986). Optimal numberings of an n x n array. SIAM Journal on Algebraic and Discrete Methods, vol. 7, no 4, p. 571–582.
Moon B., Jagadish H., Faloutsos C., Saltz J. (2001). Analysis of the clustering properties of the hilbert space-filling curve. IEEE Transactions on Knowledge and Data Engineering, vol. 13, no 1.
Muelder C., Ma K. (2008). Rapid graph layout using space filling curves. IEEE Transactions on Visualization and Computer Graphics, p. 1301–1308.
Nguyen G., Franco P., Mullot R., Ogier J. (2012). Mapping high dimensional features onto hilbert curve: Applying to fast image retrieval. In 21th international conference on pattern recognition, p. 425–428. Tsukuba, Japan, IEEE.
Oliveira H. e, Petraglia A. (2011). Global optimization using space-filling curves and measurepreserving transformations. Soft Computing in Industrial Applications, p. 121–130.
Peano G. (1890). Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen, vol. 36, no 1, p. 157–160.
Perez A., Kamata S., Kawaguchi E. (1992). Peano scanning of arbitrary size images. In Pattern recognition, 1992. vol. iii. conference c: Image, speech and signal analysis, proceedings., 11th iapr international conference on, p. 565–568. The Hague, Netherlands, IEEE.
Sagan H. (1994). Space-filling curves (vol. 2). New York, NY, USA, Springer-Verlag.
Voorhies D. (1991). Space-filling curves and a measure of coherence. Graphic Gems II, p. 26-30.
Yiu M., Tao Y., Mamoulis N. (2008). The b dual-tree: indexing moving objects by space filling curves in the dual space. The VLDB Journal, vol. 17, no 3, p. 379–400.