SP-GiST implementation of 4-dimensional quad-tree and kd-tree over temporal integers and temporal floats. More...
Data Fields | |
| TBox | left |
| TBox | right |
Detailed Description
SP-GiST implementation of 4-dimensional quad-tree and kd-tree over temporal integers and temporal floats.
These functions are based on those in the file `geo_spgist.c. from PostgreSQL. This module provides SP-GiST implementation for temporal number types using a quad tree analogy in 4-dimensional space. Notice that SP-GiST doesn't allow indexing of overlapping objects. We are making 2D objects never-overlapping in 4D 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 quad tree, we are splitting the tree into 16 quadrants in 4D space. It is easier to imagine it as splitting space two times into 4:
We are using a temporal box datatype as the prefix, but we are treating them as points in 4-dimensional space, because 2D boxes are not enough to represent the quadrant boundaries in 4D 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 4D 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 after); transferred boundaries of (1) would be the outer axis, relevant part of (2) would be the up right 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 an inner node containing a set of temporal boxes
The documentation for this struct was generated from the following file:
- /home/esteban/src/MobilityDB/mobilitydb/src/general/tnumber_spgist.c
