Optimization by Approximation-based Filtering and Indexing (cont.)
To explain the query and the underlying structures, consider all 4D segments that appear in any trajectory. Further, consider the set of all xy-segments, i.e., 2D projections of the 4D segments on the xy-plane. Also, consider a 2D minimum bounded rectangle (MBR) for each such xy-segment. The indexed approximation grouping in our example maintains a spatial index on all such MBR's, using, say an R-tree index. For each MBR, the indexed approximation grouping stores all xy-segments corresponding to it (in this example it is typically just one xy-segment). This is graphically depicted in the right hand part of Figure . In general, the indexed approximation grouping is a structure that is comprised of a ``regular'' index structure, possibly based on appriximation (in our example - MBR), and the inverse structure pointing the objects being approximated (in our example - xy-segments).
Now, for each xy-segment S, the CCUBE inverse grouping stores all trajectories that have at least one 4D segment whose xy-projection is S. This is graphically depicted in the left hand part of the following figure:
