Multi-column statistic generation of a multi-dimensional tree

Patent metadata

Field	Value
Publication number	US-10545939-B2
Application number	US-201415114363-A
Country	US
Kind code	B2
Filing date	Jan 29, 2014
Priority date	Jan 29, 2014
Publication date	Jan 28, 2020
Grant date	Jan 28, 2020

Abstract

In one implementation, a system for multi-column statistic generation of a multi-dimensional tree includes a sampling engine to generate a sample of values from a set of data values, wherein the data values include multi-dimensional inputs. In addition, the system includes generating engine to generate a multi-dimensional tree utilizing the sample values. In addition, the system includes a filtering engine to determine a number of unique values at each node of the multi-dimensional tree utilizing a filter for the set of data values. Furthermore, the system includes an implementing engine to implement the multi-dimensional tree for a query of the set of data values.

First claim

What is claimed is:

1. A system for multi-column statistic generation of a multi-dimensional tree in a computing device, comprising:
a sampling engine to:
obtain a portion of data values from a set of data values, the portion representing a sample set; and
identify multi-dimensional inputs for each data value in the sample set, each multi-dimensional input corresponding to a feature of the each data value, wherein the multi-dimensional inputs for each data value in the sample set include a first feature representing a dimension for an X-axis for the multi-dimensional tree and a second feature representing a dimension for a Y-axis for the multi-dimensional tree;

a generating engine to:
select a root value from the sample set;
compare a first multi-dimensional input value for a first data value from the sample set to a root multi-dimensional input value for the root value, the first and root multi-dimensional input values corresponding based on a same feature;
compare a second multi-dimensional input value for a second data value from the sample set to the first multi-dimensional input value and the root multi-dimensional input value, the second multi-dimensional input value corresponding to the same feature;
determine locations for nodes of the first data value and the second data value to generate the multi-dimensional tree utilizing relative positioning of the nodes based on compared multi-dimensional input values;
repeat comparison for multi-dimensional inputs associated with all remaining values from the sample set; and
determine locations for each remaining value to generate the multi-dimensional tree utilizing relative positioning based on compared multi-dimensional input values;

a filtering engine to determine a number of unique data values at each of the nodes of the multi-dimensional tree utilizing the filter for the sample set; and
an implementing engine to implement the generated multi-dimensional tree to generate a first graphical representation to be utilized for a future query of the set of data values on the computing device.

2. The system of claim 1 , including the generating engine to generate the multi-dimensional tree by placing each data value from the sample set in a location of an associated node in the multi-dimensional tree, the association of the each data value to the location based on a comparison with other multi-dimensional input values used to generate the multi-dimensional tree.

3. The system of claim 1 , including the filtering engine to determine the number of unique data values at each of the nodes of the multi-dimensional tree from a first direction of a respective node and the number of unique data values from a second direction of the respective node within the multi-dimensional tree.

4. The system of claim 1 , comprising a graphical engine to generate a second graphical representation indicating the number of unique data values from the sample set.

5. The system of claim 4 , wherein the second graphical representation includes a number of polygons that are defined by a traversal of the multi-dimensional tree from the root value.

6. A non-transitory computer readable medium storing instructions executable by a processing resource to cause a computer to:
obtain a portion of data values from a set of data values, the portion representing a sample set;
identify multi-dimensional inputs for each data value in the sample set, each multi-dimensional input corresponding to a feature of the each data value, wherein the multi-dimensional inputs for each data value in the sample set include a first feature representing a dimension for an X-axis for the multi-dimensional tree and a second feature representing a dimension for a Y-axis for the multi-dimensional tree;
assign a first value from the sample set as a root value;
compare a first multi-dimensional input value to a root multi-dimensional input value for the root value, the first and root multi-dimensional input values corresponding based on a same feature;
compare a second multi-dimensional input value for a second data value from the sample set to the first multi-dimensional input value and the root multi-dimensional input value, the second multi-dimensional input value corresponding to the same feature;
determine relative locations for each node of the multi-dimensional tree utilizing comparisons of corresponding multi-dimensional input values for each respective node;
generate the multi-dimensional tree utilizing the determined relative locations;
repeat comparison for multi-dimensional inputs associated with all remaining values from the sample set;
determine locations for each remaining value to generate the multi-dimensional tree utilizing relative positioning based on compared multi-dimensional input values; and
implement the generated multi-dimensional tree on a computing device by assigning a number of unique data values to nodes determined using associated multi-dimensional input values, the generated multi-dimensional tree for a future query of the set of data values.

7. The medium of claim 6 , wherein the instructions are executable to place the second data value as a child node of the first data value, the child node in a first direction if the compared multi-dimensional input for the second value is less than or equal to the multi-dimensional input of the first value used for comparison.

8. The medium of claim 7 , wherein the instructions are executable to place the second data value as a child node of the first data value in a second direction opposite the first direction if the compared multi-dimensional input for the second value is greater than the multi-dimensional input of the first value used for comparison.

9. The medium of claim 6 , wherein the instructions are executable to cause a computing device to generate a number of hard counters and soft counters into the multi-dimensional tree.

10. A method for multi-column statistic generation of a multi-dimensional tree, comprising:
obtaining a portion of data values from a set of data values, the portion representing a sample set; and
identifying multi-dimensional inputs for each data value in the sample set, each multi-dimensional input corresponding to a feature of the each data value, wherein the multi-dimensional inputs for each data value in the sample set include a first feature representing a dimension for an X-axis for the multi-dimensional tree and a second feature representing a dimension for a Y-axis for the multi-dimensional tree;
assigning a first value from the sample set as a root value, wherein the first value includes a median multi-dimensional input value relative to multi-dimensional input values across the sample set;
comparing a first multi-dimensional input value to the median multi-dimensional input value for the root value, the first and root multi-dimensional input values corresponding based on a same feature;
comparing a second multi-dimensional input value for a second data value from the sample set to the first multi-dimensional input value and the root multi-dimensional input value, the second multi-dimensional input value corresponding to the same feature;
determining relative locations for each node of the multi-dimensional tree utilizing comparisons of corresponding multi-dimensional input values for each respective node;
generating the multi-dimensional tree utilizing the determined relative locations;
repeating comparison for multi-dimensional inputs associated with all remaining values from the sample set;
determining locations for each remaining value to generate the multi-dimensional tree utilizing relative positioning based on compared multi-dimensional input values; and
implementing the generated m

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Kosuru Ramakumar
• Sati Kailash

Classifications

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F16/28

  Databases characterised by their database models, e.g. relational or object models · CPC title