This paper defines the Arrwwid number of a recursive tiling (or space-filling curve) as the smallest number w such that any ball Q can be covered by w tiles (or curve sections) with total volume O(vol(Q)). Recursive tilings and space-filling curves with low Arrwwid numbers can be applied to optimise disk, memory or server access patterns when processing sets of points in d-dimensional space. This paper presents recursive tilings and space-filling curves with optimal Arrwwid numbers. For d >= 3, we see that regular cube tilings and space-filling curves cannot have optimal Arrwwid number, and we see how to construct alternatives with better Arrwwid numbers.
Jagadish, Kumar and studied how well space-filling curves succeed in keeping the number of fragments needed to cover a query range low @cite_3 @cite_8 @cite_2 @cite_20 . The curve quality measures in their work are based on the number of fragments needed to cover a query range, averaged over a selection of query ranges that depends on the underlying tiling. As a result their results can only be used to analyse space-filling curves with the same underlying tiling; in particular they assume a tiling that subdivides squares into smaller squares, expanded down to a fixed level of recursion. This class of curves includes well-known curves such as the Hilbert curve @cite_15 and Z-order, also known as Morton order or Lebesgue order @cite_16 . However, it does not include, for example, Peano's curve @cite_11 , which is based on subdividing squares into squares and seems to be the curve of choice in certain applications @cite_9 @cite_1 . The work by Jagadish, Kumar and does not enable a comparison between, for example, Hilbert's curve and Peano's curve.
@cite_8 @cite_9 @cite_1 @cite_3 @cite_2 @cite_15 @cite_16 @cite_20 @cite_11
2063378448 2150486346 2015190123 1493714695 2072605585 2040879131
Abstract We give closed-form expressions for the average number of runs to cover an arbitrary square region in two dimensions using a Hilbert curve. The practical use of the derived formula is that it allows the estimation of the quality of the linearization obtained by using the Hilbert curve to map from a two-dimensional space to a one-dimensional space. Hilbert curves are used extensively as a basis for multi-dimensional indexing structures, and for declustering multi-dimensional data. One of the keys to tap the full performance potential of current hardware is the optimal utilization of cache memory. Cache oblivious algorithms are designed to inherently benefit from any underlying hierarchy of caches, but do not need to know about the exact structure of the cache. In this paper, we present a cache oblivious algorithm for matrix multiplication. The algorithm uses a block recursive structure and an element ordering that is based on Peano curves. In the resulting code, index jumps can be totally avoided, which leads to an asymptotically optimal spatial and temporal locality of the data access. There is often a need to map a multi-dimensional space on to a one-dimensional space. For example, this kind of mapping has been proposed to permit the use of one-dimensional indexing techniques to a multi-dimensional index space such as in a spatial database. This kind of mapping is also of value in assigning physical storage, such as assigning buckets to records that have been indexed on multiple attributes, to minimize the disk access effort. In this paper, we discuss what the desired properties of such a mapping are, and evaluate, through analysis and simulation, several mappings that have been proposed in the past. We present a mapping based on Hilbert's space-filling curve, which out-performs previously proposed mappings on average over a variety of different operating conditions. This paper proposes a new interleaving-based method for spatial clustering developed by combining gray codes with a new ordering technique called nu-ordering. This method is compared with two existing interleaving-based techniques and another technique called hilbert-ordering. The performance comparison is done by means of a simulation study. The results show that the choice of the technique affects the clustering performance dramatically. Among the four techniques considered, both nu-ordering and hilbert method outperformed the other two methods by more than 35 ; however, with minor exceptions, the hilbert technique was the best among the four techniques evaluated. Dans cette Note on determine deux fonctions x et y, uniformes et continues d’une variable (reelle) t, qui, lorsque t varie dans l’intervalle (0, 1), prennent toutes les couples de valeurs telles que 0≤x≤1, 0≤y≤1. Si l’on appelle, suivant l’usage, courbe continue le lieu des points dont les coordonnees sont des fonctions continues d’une variable, on a ainsi un arc de courbe qui passe par tous les points d’un carre. Donc, etant donne un arc de courbe continue, sans faire d’autres hypotheses, il n’est pas toujours possible de le renfermer dans une aire arbitrairement petite.