Quote: the UB-Tree uses a space-filling curve to map multidimensions into one; the Z-curve is efficiently implemented as variable length bitstrings

Quotation

The basic idea of the UB-Tree [Bayer, R., WWCA '97, LNCS, 1997] is to use a space-filling curve to map a multidimensional universe to one-dimensional space. Using the Z-Curve ... for preserving multidimensional clustering as good as possible [sic] it is a variant of the zkd-B-Tree [ref]. ... All algorithms for the UB-Tree basically rely on Z-values in the format of variable length bitstrings ... The UBKEY function can be efficiently implemented, as it requires only reading the specified index attributes bitwise and writing the bits at the corresponding positions in the resulting Z-value.   Google-1   Google-2

By permission of the Very Large Database Endowment

Related Topics

Topic: computational geometry (20 items)
Topic: b-trees (16 items)