SP-GiST implementation of 8-dimensional quad-tree over temporal points. More...
Data Fields | |
| STBox | left |
| STBox | right |
Detailed Description
SP-GiST implementation of 8-dimensional quad-tree over temporal points.
This module provides SP-GiST implementation for boxes using an oct-tree analogy in 8-dimensional space. SP-GiST doesn't allow indexing of overlapping objects. We are making 4D objects never-overlapping in 8D space. This technique has some benefits compared to traditional R-Tree which is implemented as GiST. The performance tests reveal that this technique especially beneficial with too much overlapping objects, so called "spaghetti data".
Unlike the original oct-tree, we are splitting the tree into 256 quadrants in 8D space. It is easier to imagine it as splitting space four times into four:
We are using STBox data type as the prefix, but we are treating them as points in 8-dimensional space, because 4D boxes are not enough to represent the quadrant boundaries in 8D space. They however are sufficient to point out the additional boundaries of the next quadrant.
We are using traversal values provided by SP-GiST to calculate and to store the bounds of the quadrants, while traversing into the tree. Traversal value has all the boundaries in the 8D space, and is is capable of transferring the required boundaries to the following traversal values. In conclusion, three things are necessary to calculate the next traversal value:
- the traversal value of the parent
- the quadrant of the current node
- the prefix of the current node
If we visualize them on our simplified drawing (see the drawing above); transferred boundaries of (1) would be the outer axis, relevant part of (2) would be the up range_y part of the other axis, and (3) would be the inner axis.
For example, consider the case of overlapping. When recursion descends deeper and deeper down the tree, all quadrants in the current node will be checked for overlapping. The boundaries will be re-calculated for all quadrants. Overlap check answers the question: can any box from this quadrant overlap with the given box? If yes, then this quadrant will be walked. If no, then this quadrant will be skipped.
This method provides restrictions for minimum and maximum values of every dimension of every corner of the box on every level of the tree except the root. For the root node, we are setting the boundaries that we don't yet have as infinity.
Structure to represent the bounding box of a temporal point as a 6- or 8-dimensional point depending on whether the temporal point is in 2D+T or 3D+T.
The documentation for this struct was generated from the following file:
- /home/esteban/src/MobilityDB/mobilitydb/src/point/tpoint_spgist.c
