Methods and systems for estimating the number of points in two-dimensional data

1. A computer-implemented method of optimizing execution of a query that accesses data by a computer, the method comprising:

representing a given set of multidimensional data including a plurality of data points having a value by a hierarchical tree data structure including nodes, each node representing a distribution of a subset of the points in the data set and being partitioned into tiles;

calculating a bounding rectangle of the data points in each node;

entering all non-empty tiles into a queue;

processing of the queue can continue until a computational memory space limit is reached or until a desired estimation resolution is met;

encoding the resulting tree structure;

determining compression scales for the hierarchical tree data structure, the compression scale including a compression factor and a decompression factor;

persisting a record of the compression scales; and

during the processing of the queue, compressing and decompressing the nodes using the compression scales.

2. The method of claim 1 , further comprising determining a classification for each of the nodes, the determined classification being selected from a plurality of possible classifications.

3. The method of claim 2 , wherein the classification is based on a size of the tiles comprising each node.

4. The method of claim 2 , further comprising configuring the queue based on the classification of the tiles.

5. The method of claim 4 , wherein tiles are processed based on an order thereof in the queue.

6. The method of claim 3 , further comprising:

storing nodes of a same classification in a same array;

indexing a child node by a child base index containing an index of a first child node within the array, wherein the children of each node are stored consecutively; and

indexing the children nodes other than the first child node within a sub-array of the array of the children nodes.

7. The method of claim 1 , wherein the compression scales vary depending on a number of bits used to represent the range of values of the node.

8. The method of claim 1 , further comprising:

determining whether a query rectangle is fully contained within a bounding rectangle for all the data points;

in response to the determination that the query rectangle is fully contained within the bounding rectangle, store the number of data points as an estimate for the query; and

in response to the determination that the query rectangle is not fully contained within the bounding rectangle, a total frequency of all tiles that are fully contained by the query tile can be summed and a fraction of the frequency of a tile according to the area covered by the query tile is added.

9. A non-transitory, computer-readable medium storing program instructions thereon, the medium comprising:

instructions to represent a given set of multidimensional data including a plurality of data points having a value by a hierarchical tree data structure including nodes, each node representing a distribution of a subset of the points in the data set and being partitioned into tiles;

instructions to calculate a bounding rectangle of the data points in each node;

instructions to enter all non-empty tiles into a queue;

instructions to process of the queue can continue until a computational memory space limit is reached or until a desired estimation resolution is met; and

instructions to encode the resulting tree structure;

instructions to determine compression scales for the hierarchical tree data structure, the compression scale including a compression factor and a decompression factor;

instructions to persist a record of the compression scales; and

instructions to, during the processing of the queue, compress and decompress the nodes using the compression scales.

10. The medium of claim 9 , further comprising instructions to determine a classification for each of the nodes, the determined classification being selected from a plurality of possible classifications.

11. The medium of claim 10 , wherein the classification is based on a size of the tiles comprising each node.

12. The medium of claim 10 , further comprising instructions to configure the queue based on the classification of the tiles.

13. The medium of claim 12 , wherein tiles are processed based on an order thereof in the queue.

14. The medium of claim 11 , further comprising:

instructions to store nodes of a same classification in a same array;

instructions to index a child node by a child base index containing an index of a first child node within the array, wherein the children of each node are stored consecutively; and

instructions to index the children nodes other than the first child node within a sub-array of the array of the children nodes.

15. The medium of claim 9 , wherein the compression scales vary depending on a number of bits used to represent the range of values of the node.

16. The medium of claim 9 , further comprising:

instructions to determine whether a query rectangle is fully contained within a bounding rectangle for all the data points;

instructions to, in response to the determination that the query rectangle is fully contained within the bounding rectangle, store the number of data points as an estimate for the query; and

instructions to, in response to the determination that the query rectangle is not fully contained within the bounding rectangle, a total frequency of all tiles that are fully contained by the query tile can be summed and a fraction of the frequency of a tile according to the area covered by the query tile is added.

17. A system, comprising:

a memory storing processor-executable program instructions, and

a processor to execute the processor-executable program instructions in order to:

represent a given set of multidimensional data including a plurality of data points having a value by a hierarchical tree data structure including nodes, each node representing a distribution of a subset of the points in the data set and being partitioned into tiles;

calculate a bounding rectangle of the data points in each node;

enter all non-empty tiles into a queue;

process of the queue can continue until a computational memory space limit is reached or until a desired estimation resolution is met;

encode the resulting tree structure;

determine compression scales for the hierarchical tree data structure, the compression scale including a compression factor and a decompression factor;

persist a record of the compression scales; and

during the processing of the queue, compress and decompress the nodes using the compression scales.

18. The system of claim 17 , including execution of the processor-executable program instructions causing the processor to:

determine a classification for each of the nodes, the determined classification being selected from a plurality of possible classifications, the classification is based on a size of the tiles comprising each node;

store nodes of a same classification in a same array;

index a child node by a child base index containing an index of a first child node within the array, the children of each node are stored consecutively; and

index the children nodes other than the first child node within a sub-array of the array of the children nodes.

19. The system of claim 17 , including execution of the processor-executable program instructions causing the processor to vary the compression scales depending on a number of bits used to represent the range of values of the node.

20. The system of claim 17 , including execution of the processor-executable program instructions causing the processor to:

determine whether a query rectangle is fully contained within a bounding rectangle for all the data points;

in response to the determination that the query rectangle is fully contained within the bounding rectangle, store the number of data points as an estimate for the query; and

in response to the determination that the query rectangle is not fully contained within the bounding rectangle, sum a total frequency of all tiles that are fully contained by the query tile, and add a fraction of the frequency of a tile according to the area covered by the query tile.