GPU-based parallel indexing for concurrent spatial query

1. A system comprising:

a graphics processing unit; and

a central processing unit communicably coupled to the graphics processing unit, the central processing unit configured to at least:

determine a number of nodes in a tree to be partitioned for a dataset comprising a plurality of data points;

iteratively initiate performance of a partition of the tree via the graphics processing unit;

initiate performance of a node creation on the graphics processing unit; and

initiate performance of a point insertion on the graphics processing unit;

the graphics processing unit configured to at least:

associate each of a plurality of threads with a respective data point of the plurality of data points;

(i) determine, for each thread, a child node in a current tree level to which the data point associated with the thread belongs;

(ii) update a counter associated with each child node of a plurality of child nodes, wherein the counter is configured to maintain a count of the number of data points associated with the child node;

(iii) subsequent to updating each of the plurality of counters, identify child nodes for which the count exceeds a predetermined threshold;

(iv) repeat (i) to (iii) for data points associated with child nodes having a count that exceeds the predetermined threshold until a stopping condition is reached;

subsequent to reaching the stopping condition, associate each of a second plurality of threads with a respective non-empty leaf node of a plurality of non-empty leaf nodes;

allocate, for each thread associated with a leaf node, memory for each data point associated with the leaf node; and

associate each data point with a memory allocated to the data point, such that each leaf node points to a beginning of memory allocated to points associated with the leaf node.

2. The system of claim 1 , wherein the graphics processing unit is further configured to at least perform a tree partition based at least in part on finding a position of an input in children of a node and performing a split of the input in the children of the node.

3. The system of claim 1 , wherein the graphics processing unit is further configured to perform a plurality of node creations in parallel using the plurality of threads.

4. The system of claim 1 , wherein the graphics processing unit is further configured to perform the node creation by allocating consecutive memory in an array.

5. The system of claim 1 , wherein the partition of the tree is iteratively performed for each level of the tree.

6. The system of claim 1 , wherein the node creation is performed by the graphics processing unit in response to a determination that the leaf node will represent a non-empty node.

7. The system of claim 1 , wherein each of the plurality of data points comprises a two-dimensional data point, and wherein the point insertion comprises:

inserting a value associated with a first dimension of each data point into a first array; and

inserting a value associated with a second dimension of each data point into a second array.

8. A method comprising:

determining, via a central processing unit, a number of nodes to be partitioned;

iteratively performing, via a graphics processing unit, a tree partition, wherein performing the tree partition comprises:

associating each of a plurality of threads with a respective data point of the plurality of data points;

(i) determining, for each thread, a child node in a current tree level to which the data point associated with the thread belongs;

(ii) updating a counter associated with each child node of a plurality of child nodes, wherein the counter is configured to maintain a count of the number of data points associated with the child node;

(iii) subsequent to updating each of the plurality of counters, identifying child nodes for which the count exceeds a predetermined threshold; and

(iv) repeating (i) to (iii) for data points associated with child nodes having a count that exceeds the predetermined threshold until a stopping condition is reached;

performing, via the graphics processing unit, a node creation, wherein performing node creation comprises:

subsequent to reaching the stopping condition, associating each of a second plurality of threads with a respective non-empty leaf node of a plurality of non-empty leaf nodes; and

allocating, for each thread associated with a leaf node, memory for each data point associated with the leaf node; and

performing point insertion on the graphics processing unit, wherein performing point insertion comprises associating each data point with a memory allocated to the data point, such that each leaf node points to a beginning of memory allocated to points associated with the leaf node.

9. The method of claim 8 , further comprising performing, via the graphics processing unit, a tree partition based at least in part on finding a position of an input in children of a node and performing a split of the input in the children of the node.

10. The method of claim 8 , further comprising performing, via the graphics processing unit, a plurality of node creations in parallel using the plurality of threads.

11. The method of claim 8 , further comprising performing, via the graphics processing unit, the node creation by allocating consecutive memory in an array.

12. The method of claim 8 , wherein the partition of the tree is iteratively performed for each level of the tree.

13. The method of claim 8 , wherein performing the node creation occurs in response to a determination that the leaf node will represent a non-empty node.

14. The method of claim 8 , wherein each of the plurality of data points comprises a two-dimensional data point, and wherein the point insertion comprises:

inserting a value associated with a first dimension of each data point into a first array; and

inserting a value associated with a second dimension of each data point into a second array.

15. A non-transitory, computer-readable medium comprising machine readable instructions that, when executed by at least one processor, cause a computing device to at least:

determine a number of nodes to be partitioned;

iteratively initiate performance of a tree partition via a graphics processing unit;

associate each of a plurality of threads with a respective data point of the plurality of data points;

(i) determine, for each thread, a child node in a current tree level to which the data point associated with the thread belongs;

(ii) update a counter associated with each child node of a plurality of child nodes, wherein the counter is configured to maintain a count of the number of data points associated with the child node;

(iii) subsequent to updating each of the plurality of counters, identify child nodes for which the count exceeds a predetermined threshold; and

(iv) repeat (i) to (iii) for data points associated with child nodes having a count that exceeds the predetermined threshold until a stopping condition is reached;

initiate performance of a node creation on the graphics processing unit;

associate each of a second plurality of threads with a respective non-empty leaf node of a plurality of non-empty leaf nodes; and

allocate, for each thread associated with a leaf node, memory for each data point associated with the leaf node;

initiate performance of a point insertion on the graphics processing unit; and

associate each data point with a memory allocated to the data point, such that each leaf node points to a beginning of memory allocated to points associated with the leaf node.

16. The non-transitory, computer-readable medium of claim 15 , wherein the graphics processing unit is configured to at least perform a tree partition based at least in part on finding a position of an input in children of a node and performing a split of the input in the children of the node.

17. The non-transitory, computer-readable medium of claim 15 , wherein the graphics processing unit is configured to perform a plurality of node creations in parallel using the plurality of threads.

18. The non-transitory, computer-readable medium of claim 15 , wherein the graphics processing unit is configured to perform the node creation by allocating consecutive memory in an array.

19. The non-transitory, computer-readable medium of claim 15 , wherein the partition of the tree is iteratively performed for each level of the tree.

20. The non-transitory, computer-readable medium of claim 15 , wherein the node creation is performed by the graphics processing unit in response to a determination that the leaf node will represent a non-empty node.