SP-GiST implementation of 8-dimensional quad-tree over temporal spatial values. More...

#include <assert.h>
#include <float.h>
#include <math.h>
#include <postgres.h>
#include <access/spgist.h>
#include <utils/timestamp.h>
#include <meos.h>
#include <meos_internal.h>
#include <meos_internal_geo.h>
#include "temporal/span.h"
#include "temporal/stratnum.h"
#include "temporal/temporal.h"
#include "temporal/type_util.h"
#include "geo/stbox.h"
#include "geo/stbox_index.h"
#include "pg_temporal/meos_catalog.h"
#include "pg_temporal/temporal.h"
#include "pg_temporal/tnumber_spgist.h"

Data Structures
struct	SortedSTbox
	Structure to sort the temporal boxes of an inner node. More...

struct	STboxNode
	Structure to represent the bounding box of a spatiotemporal value as a 6- or 8-dimensional point depending on whether the spatiotemporal value is in 2D+T or 3D+T. More...

Typedefs
typedef struct SortedSTbox	SortedSTbox
	Structure to sort the temporal boxes of an inner node. More...

Functions
static bool	above8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox be above a query? More...

static bool	after8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox be after a query? More...

static bool	back8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox be back to a query? More...

static bool	before8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox be before a query? More...

static bool	below8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox be below a query? More...

static bool	contain8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox contain a query? More...

static bool	containKD (const STboxNode nodebox, const STBox query, int level)
	Can any box from a nodebox contain a query? More...

static double	distance_stbox_nodebox (const STBox query, const STboxNode nodebox)
	Return the lower bound for the distance between a query and a nodebox. More...

static bool	front8D (STboxNode nodebox, STBox query)
	Can any box from a nodebox be in front of a query? More...

static uint8	getQuadrant8D (const STBox centroid, const STBox inBox)
	Calculate the quadrant. More...

static bool	left8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox be to the left of a query? More...

static bool	overAbove8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox does not extend below a query? More...

static bool	overAfter8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox be before a query? More...

static bool	overBack8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox does not extend to the front of a query? More...

static bool	overBefore8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox be after a query? More...

static bool	overBelow8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox does not extend above a query? More...

static bool	overFront8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox does not extend to the back of a query? More...

static bool	overlap8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox overlap with a query? More...

static bool	overlapKD (const STboxNode nodebox, const STBox query, int level)
	Can any box from a nodebox overlap with a query? More...

static bool	overLeft8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox does not extend to the right of a query? More...

static bool	overRight8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox does not extend to the left of a query? More...

static bool	right8D (const STboxNode nodebox, const STBox query)
	Can any box from a nodebox be to the right of a query? More...

Datum	Stbox_kdtree_choose (PG_FUNCTION_ARGS)
	K-d tree choose function for spatiotemporal values. More...

Datum	Stbox_kdtree_inner_consistent (PG_FUNCTION_ARGS)
	Kd-tree inner consistent function for spatiotemporal values. More...

Datum	Stbox_kdtree_picksplit (PG_FUNCTION_ARGS)
	K-d tree pick-split function for spatiotemporal boxes. More...

static int	stbox_level_cmp (STBox centroid, STBox query, int level)

Datum	Stbox_quadtree_choose (PG_FUNCTION_ARGS)
	SP-GiST choose function for spatiotemporal values. More...

Datum	Stbox_quadtree_inner_consistent (PG_FUNCTION_ARGS)
	Quad-tree inner consistent function for spatiotemporal values. More...

Datum	Stbox_quadtree_picksplit (PG_FUNCTION_ARGS)
	SP-GiST pick-split function for spatiotemporal values. More...

Datum	Stbox_spgist_config (PG_FUNCTION_ARGS)
	SP-GiST config function for spatiotemporal values. More...

Datum	stbox_spgist_inner_consistent (FunctionCallInfo fcinfo, SPGistIndexType idxtype)

Datum	Stbox_spgist_leaf_consistent (PG_FUNCTION_ARGS)
	SP-GiST leaf consistency function for spatiotemporal values. More...

static int	stbox_tmax_cmp (const STBox box1, const STBox box2)
	Comparator of temporal boxes based on their tmax value. More...

static int	stbox_tmin_cmp (const STBox box1, const STBox box2)
	Comparator of temporal boxes based on their tmin value. More...

static int	stbox_xmax_cmp (const STBox box1, const STBox box2)
	Comparator of temporal boxes based on their xmax value. More...

static int	stbox_xmin_cmp (const STBox box1, const STBox box2)
	Determine which half a 4D-mapped temporal box falls into, relative to the centroid and the level number. More...

static int	stbox_ymax_cmp (const STBox box1, const STBox box2)
	Comparator of temporal boxes based on their ymax value. More...

static int	stbox_ymin_cmp (const STBox box1, const STBox box2)
	Comparator of temporal boxes based on their ymin value. More...

static int	stbox_zmax_cmp (const STBox box1, const STBox box2)
	Comparator of temporal boxes based on their zmax value. More...

static int	stbox_zmin_cmp (const STBox box1, const STBox box2)
	Comparator of temporal boxes based on their zmin value. More...

STboxNode *	stboxnode_copy (const STboxNode *box)
	Copy an `STboxNode`. More...

static void	stboxnode_init (const STBox centroid, STboxNode nodebox)
	Initialize the traversal value. More...

static void	stboxnode_kdtree_next (const STboxNode nodebox, const STBox centroid, uint8 node, int level, STboxNode *next_nodebox)
	Compute the next traversal value for a k-d tree given the bounding box and the centroid of the current node, and the level. More...

static void	stboxnode_quadtree_next (const STboxNode nodebox, const STBox centroid, uint8 quadrant, STboxNode *next_nodebox)
	Calculate the next traversal value for an oct-tree. More...

Datum	Tspatial_spgist_compress (PG_FUNCTION_ARGS)
	SP-GiST compress functions for spatiotemporal values. More...

static bool	tspatial_spgist_get_stbox (const ScanKeyData scankey, STBox result)
	Return in the last argument a spatiotemporal box obtained from a query. More...

Detailed Description

SP-GiST implementation of 8-dimensional quad-tree over temporal spatial values.

This module provides SP-GiST implementation for boxes using an oct-tree analogy in 8-dimensional space. SP-GiST does not 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:

             |      |                        |      |
             |      |                        |      |
             | -----+-----                   | -----+-----
             |      |                        |      |
             |      |                        |      |
-------------+------------- -+- -------------+-------------
             |                               |
             |                               |
             |                               |
             |                               |
             |                               |
           FRONT                           BACK

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.

Data Structures

Typedefs

Functions

Detailed Description