Мәліметтердің жақын орналасуын сақтайтын функциялар

Mapping function that preserves data point locality

In mathematical analysis and computer science, functions which are Z order, Lebesgue curve, Morton space filling curve, Morton order or Morton code map multidimensional data to one dimension while preserving locality of the data points. It is named in France after Henri Lebesgue, who studied it in 1904, and named in the United States after Guy Macdonald Morton, who first applied the order to file sequencing in 1966. The z value of a point in multidimensions is simply calculated by interleaving the binary representations of its coordinate values. Once the data are sorted into this ordering, any one dimensional data structure can be used, such as simple one dimensional arrays, binary search trees, B trees, skip lists or (with low significant bits truncated) hash tables. The resulting ordering can equivalently be described as the order one would get from a depth first traversal of a quadtree or octree.

By bit interleaving, the database records are converted to a (possibly very long) sequence of bits. The bit sequences are interpreted as binary numbers and the data are sorted or indexed by the binary values, using any one dimensional data structure, as mentioned in the introduction. However, when querying a multidimensional search range in these data, using binary search is not really efficient. Although Z order is preserving locality well, for efficient range searches an algorithm is necessary for calculating, from a point encountered in the data structure, the next possible Z value which is in the multidimensional search range:

In this example, the range being queried (x = 2,  , 3, y = 2,  , 6) is indicated by the dotted rectangle. Its highest Z value (MAX) is 45. In this example, the value F = 19 is encountered when searching a data structure in increasing Z value direction, so we would have to search in the interval between F and MAX (hatched area). To speed up the search, one would calculate the next Z value which is in the search range, called BIGMIN (36 in the example) and only search in the interval between BIGMIN and MAX (bold values), thus skipping most of the hatched area. Searching in decreasing direction is analogous with LITMAX which is the highest Z value in the query range lower than F. The BIGMIN problem has first been stated and its solution shown in Tropf and Herzog. An extensive explanation of the LITMAX/BIGMIN calculation algorithm, together with Pascal Source Code (3D, easy to adapt to nD) and hints on how to handle floating point data and possibly negative data, is provided 2021 by Tropf: Here, bit interleaving is not done explicitly; the data structure has just pointers to the original (unsorted) database records. With a general record comparison function (greater less equal, in the sense of z value), complications with bit sequences length exceeding the computer word length are avoided, and the code can easily be adapted to any number of dimensions and any record key word length. As the approach does not depend on the one dimensional data structure chosen, there is still free choice of structuring the data, so well known methods such as balanced trees can be used to cope with dynamic data, and keeping the tree balance when inserting or deleting takes O(log n) time. The method is also used in UB trees (balanced), with the name "GetNextZ address" for BIGMIN. The Free choice makes it easier to incorporate the method into existing databases. This is in contrast for example to R trees where special considerations are necessary. Applying the method hierarchically (according to the data structure at hand), optionally in both increasing and decreasing direction, yields highly efficient multidimensional range search which is important in both commercial and technical applications, e. g. as a procedure underlying nearest neighbour searches. Z order is one of the few multidimensional access methods that has found its way into commercial database systems. The method is used in various technical applications of different fields and in commercial database systems. As long ago as 1966, G. M. Morton proposed Z order for file sequencing of a static two dimensional geographical database. Areal data units are contained in one or a few quadratic frames represented by their sizes and lower right corner Z values, the sizes complying with the Z order hierarchy at the corner position. With high probability, changing to an adjacent frame is done with one or a few relatively small scanning steps.

The Strassen algorithm for matrix multiplication is based on splitting the matrices in four blocks, and then recursively splitting each of these blocks in four smaller blocks, until the blocks are single elements (or more practically: until reaching matrices so small that the Moser–de Bruijn sequence trivial algorithm is faster). Arranging the matrix elements in Z order then improves locality, and has the additional advantage (compared to row or column major ordering) that the subroutine for multiplying two blocks does not need to know the total size of the matrix, but only the size of the blocks and their location in memory. Effective use of Strassen multiplication
with Z order has been demonstrated, see Valsalam and Skjellum's 2002 paper. Buluç et al. present a sparse matrix data structure that Z orders its non zero elements to enable parallel matrix vector multiplication. Matrices in linear algebra can also be traversed using a space filling curve. Conventional loops traverse a matrix row by row. Traversing with the Z curve allows efficient access to the memory hierarchy.

Some GPUs store texture maps in Z order to increase spatial locality of reference during texture mapped rasterization. This allows cache lines to represent rectangular tiles, increasing the probability that nearby accesses are in the cache. At a larger scale, it also decreases the probability of costly, so called, "page breaks" (i. e., the cost of changing rows) in SDRAM/DDRAM. This is important because 3D rendering involves arbitrary transformations (rotations, scaling, perspective, and distortion by animated surfaces). These formats are often referred to as swizzled textures or twiddled textures. Other tiled formats may also be used.

The Barnes–Hut algorithm requires construction of an octree. Storing the data as a pointer based tree requires many sequential pointer dereferences to iterate over the octree in depth first order (expensive on a distributed memory machine). Instead, if one stores the data in a hashtable, using octree hashing, the Z order curve naturally iterates the octree in depth first order.