Storage Methods > Structures > 1-D Grid approx
One dimensional embedding: z-order or bit-interleaving
- Find a linear order for the cells of the grid while maintaining ėlocalityî (i.e., cells close to each other in space are also close to each other in the linear order)
- Define this order recursively for a grid that is obtained by hierarchical subdivision of space
- For each spatial object, we can obtain a set of ėspatial keysî
- Index: can be a B-tree of lexicographically ordered list of the union of these spatial keys
