Method and apparatus for implementing a learning model for facilitating answering a query on a database

• US 8,874,615 B2
• Filed: 01/13/2012
• Issued: 10/28/2014
• Est. Priority Date: 01/13/2012
• Status: Active Grant

• Current Assignee: NeuStar IP Intelligence, Inc. (Neustar Incorporated)
• Original Assignee: Quova Inc. (Neustar Incorporated)
• Inventors: Prieditis, Armand Erik
• Primary Examiner(s): DANG, THANH HA T
• Application Number:
  US13/349,987
• Publication Number:
  US 20130185335A1
• Time in Patent Office: 1,019 Days
• Field of Search: 707/793, 707/791, 707/797, 707/802, 707/803
• US Class Current: 707/793
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

A method and apparatus for implementing a learning model for facilitating answering a query on a database. Example embodiments include processing logic to: receive access to a database having a plurality of rows; determine for each row in the plurality of rows which of a plurality of child nodes to associate with a row based on the row and current parameters, where the current parameters correspond to parameters of a probability distribution for the plurality of child nodes; determine new parameters for the plurality of child nodes based on associated rows of the plurality of rows; determine whether or not to return a result which indicates the new parameters based on the current parameters, the new parameters, and the plurality of rows; and return a result which indicates the new parameters.

Claims

1. A method comprising:

receiving access to a database having a plurality of rows;

determining, by use of a processor, for each row in the plurality of rows that is associated with a selected parent node, which of a plurality of child nodes to associate with a selected row of the plurality of rows based on the row and current parameters, where the current parameters correspond to parameters of a multivariate normal distribution of a multivariate normal model for the plurality of child nodes, the multivariate normal model comprising a mean vector and a covariance matrix, the mean vector comprising one or more mean values of data of a corresponding node and the covariance matrix comprising a deviation value for each of a plurality of pairs of the mean values;

associating each row in the plurality of rows that is associated with the selected parent node with the corresponding determined child node;

determining new parameters for the plurality of child nodes based on associated rows of the plurality of rows;

determining whether or not to return a result which indicates the new parameters based on the current parameters, the new parameters, and the plurality of rows; and

returning a result which indicates the new parameters.

2. The method of claim 1 wherein the plurality of rows are vectors or matrices.

3. The method of claim 1 wherein the current parameters correspond to parameters of a multivariate normal distribution for the plurality of child nodes.

4. The method of claim 1 including setting the current parameters to the new parameters.

5. The method of claim 1 including inferring missing values in each row of the plurality of rows after associating each row with the plurality of child nodes.

6. The method of claim 1 including determining the new parameters based on the current parameters.

7. The method of claim 1 including producing a probabilistic tree with relationships between a parent node and the plurality of child nodes.

8. The method of claim 7 including terminating the production of the probabilistic tree when termination criteria are satisfied.

9. A system comprising:

a processor; and

a database processor, in data communication with the processor, to;

receive access to a database having a plurality of rows;

determine for each row in the plurality of rows that is associated with a selected parent node, which of a plurality of child nodes to associate with a selected row of the plurality of rows based on the row and current parameters, where the current parameters correspond to parameters of a multivariate normal distribution of a multivariate normal model for the plurality of child nodes, the multivariate normal model comprising a mean vector and a covariance matrix, the mean vector comprising one or more mean values of data of a corresponding node and the covariance matrix comprising a deviation value for each of a plurality of pairs of the mean values;

associate each row in the plurality of rows that is associated with the selected parent node with the corresponding determined child node;

determine new parameters for the plurality of child nodes based on associated rows of the plurality of rows;

determine whether or not to return a result which indicates the new parameters based on the current parameters, the new parameters, and the plurality of rows; and

return a result which indicates the new parameters.

10. The system of claim 9 wherein the plurality of rows are vectors or matrices.

11. The system of claim 9 wherein the current parameters correspond to parameters of a multivariate normal distribution for the plurality of child nodes.

12. The system of claim 9 being further configured to set the current parameters to the new parameters.

13. The system of claim 9 being further configured to infer missing values in each row of the plurality of rows after associating each row with the plurality of child nodes.

14. The system of claim 9 being further configured to determine the new parameters based on the current parameters.

15. The system of claim 9 being further configured to produce a probabilistic tree with relationships between a parent node and the plurality of child nodes.

16. The system of claim 15 being further configured to terminate the production of the probabilistic tree when termination criteria are satisfied.

17. An article of manufacture comprising a non-transitory machine-readable storage medium having machine executable instructions embedded thereon, which when executed by a machine, cause the machine to:

receive access to a database having a plurality of rows;

determine for each row in the plurality of rows that is associated with a selected parent node, which of a plurality of child nodes to associate with a selected row of the plurality of rows based on the row and current parameters, where the current parameters correspond to parameters of a multivariate normal distribution of a multivariate normal model for the plurality of child nodes, the multivariate normal model comprising a mean vector and a covariance matrix, the mean vector comprising one or more mean values of data of a corresponding node and the covariance matrix comprising a deviation value for each of a plurality of pairs of the mean values;

associate each row in the plurality of rows that is associated with the selected parent node with the corresponding determined child node;

determine new parameters for the plurality of child nodes based on associated rows of the plurality of rows;

determine whether or not to return a result which indicates the new parameters based on the current parameters, the new parameters, and the plurality of rows; and

return a result which indicates the new parameters.

18. The article of manufacture of claim 17 wherein the plurality of rows are vectors or matrices.

19. The article of manufacture of claim 17 wherein the current parameters correspond to parameters of a multivariate normal distribution for the plurality of child nodes.

20. The article of manufacture of claim 17 being further configured to infer missing values in each row of the plurality of rows after associating each row with the plurality of child nodes.