Determining concepts associated with a query

• US 8,122,016 B1
• Filed: 04/24/2008
• Issued: 02/21/2012
• Est. Priority Date: 04/24/2007
• Status: Active Grant

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: Wal Mart Stores Inc (WalMart Inc.)
• Inventors: Lamba, Digvijay Singh, Lam, Wang Chee, Tourn, Michel A.
• Primary Examiner(s): Lu, Kuen
• Assistant Examiner(s): Pham, Tuan A
• Application Number:
  US12/150,311
• Time in Patent Office: 1,398 Days
• Field of Search: None
• US Class Current: 707/723
• CPC Class Codes: G06F 11/30 Monitoring
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/90332 Natural language query formulation or dialogue systems

Abstract

Determining one or more concepts associated with a query is disclosed. A query is received. A list of concepts and associated scores is received. The concepts fit within a concept hierarchy. A density function is used to evaluate the received concepts. One or more concepts are associated with the query based at least in part on the results of the density function.

Claims

1. A system for determining one or more concepts associated with a query, comprising:

a processor configured to;

receive a query;

receive a list of candidate concepts and associated scores, the concepts fitting within a concept hierarchy;

use a density function to evaluate the received concepts; and

associate one or more concepts with the query based at least in part on the results of the density function; and

a memory coupled to the processor and configured to provide the processor with instructions;

wherein the density function is a function that relates a node score and at least one of (1) a measure of a number of child concepts under a parent concept in the concept hierarchy and (2) a measure of a number of paths that are available to be taken from the parent concept to its children in the concept hierarchy.

2. The system of claim 1 wherein at least some of the concepts are subject type concepts.

3. The system of claim 1 wherein at least some of the concepts are information type concepts.

4. The system of claim 1 wherein the received scores comprise text match scores.

5. The system of claim 1 wherein the received scores comprise cooccurrence scores.

6. The system of claim 1 wherein the received scores are determined using a combination function.

7. The system of claim 1 wherein the processor is further configured to identify a surprise.

8. The system of claim 1 wherein the processor is further configured to identify an ambiguity.

9. The system of claim 1 wherein the processor is further configured to autodisambiguate an ambiguity.

10. The system of claim 1 wherein the processor is further configured to perform a grouping function.

11. The system of claim 1 wherein the processor is further configured to perform a naming function.

12. The system of claim 1 wherein the concept hierarchy is a tree.

13. The system of claim 1 wherein the concept hierarchy is a directed acyclic graph.

14. The system of claim 1 wherein the processor is further configured to output a portion of the concept hierarchy.

15. A method for determining one or more concepts associated with a query, comprising:

receiving a query;

receiving a list of concepts and associated scores, the concepts fitting within a concept hierarchy;

using a density function to evaluate, with a processor, the received concepts; and

associating one or more concepts with the query based at least in part on the results of the density function;

wherein the density function is a function that relates a node score and at least one of (1) a measure of a number of child concepts under a parent concept in the concept hierarchy and (2) a measure of a number of paths that are available to be taken from the parent concept to its children in the concept hierarchy.

16. The method of claim 15 wherein the concept hierarchy is a directed acyclic graph.

17. The method of claim 15 wherein the received scores are determined using a combination function.

18. The method of claim 15 further comprising identifying a surprise.

19. A computer program product for determining one or more concepts associated with a query, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

receiving a query;

receiving a list of concepts and associated scores, the concepts fitting within a concept hierarchy;

using a density function to evaluate the received concepts; and

associating one or more concepts with the query based at least in part on the results of the density function;

wherein the density function is a function that relates a node score and at least one of (1) a measure of a number of child concepts under a parent concept in the concept hierarchy and (2) a measure of a number of paths that are available to be taken from the parent concept to its children in the concept hierarchy.