Vector analysis of histograms for units of a concept network in search query processing

• US 7,340,460 B1
• Filed: 03/09/2004
• Issued: 03/04/2008
• Est. Priority Date: 04/04/2003
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Joshi, Deepa, Kapur, Shyam
• Primary Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US10/797,586
• Time in Patent Office: 1,456 Days
• Field of Search: 707 2- 5, 707/10, 707/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/337 Profile generation, learning or modification
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A set of concept networks is generated, with each concept network based on a different group of queries. From these concept networks, histogram vectors are defined for various units, where a unit'"'"'s histogram vector reflects the frequency of occurrence of that unit in the different concept networks. Analysis of histogram vectors for different units across the same set of concept networks can enable detection of patterns of user behavior that can be used in responding to a subsequently received query.

Claims

1. A computer-implemented method for analyzing user search queries, the method comprising the acts of:

grouping a set of previous queries into a plurality of subsets along a dimension;

for each of the subsets of the previous queries, generating a concept network, each concept network including a plurality of units and a plurality of relationships defined between the units, wherein each unit of each concept network has a frequency weight;

selecting one of the units;

constructing a histogram vector for the selected unit, the histogram vector having an element corresponding to each of the concept networks, wherein each element of the histogram vector has a value representative of the frequency weight of the selected unit in the corresponding one of the concept networks; and

storing the histogram vector on a data store accessible by a processor.

2. The method of claim 1, wherein the dimension is a time dimension.

3. The method of claim 1, wherein the dimension is defined by reference to one or more demographic characteristics of users.

4. The method of claim 1, wherein the dimension is a geographic dimension.

5. The method of claim 1, wherein the dimension is a vertical dimension representing a user context of the query.

6. The method of claim 1, further comprising the act of storing the selected unit in a unit dictionary in association with the histogram vector.

7. The method of claim 6, further comprising the acts of:

receiving a subsequent query;

parsing the subsequent query into one or more constituent units;

obtaining the histogram vector for at least one of the constituent units from the unit dictionary; and

responding to the subsequent query based at least in part on the histogram vector.

8. The method of claim 7, wherein the act of responding further includes suggesting a related search based at least in part on the histogram vector.

9. The method of claim 7, wherein the act of responding further includes resolving an ambiguity of one of the constituent units based at least in part on the histogram vector.

10. The method of claim 6, further comprising the acts of:

identifying a group of units that have similar histogram vectors; and

storing group membership information for the units of the group in the unit dictionary.

11. The method of claim 6, further comprising the acts of:

selecting a base unit from the unit dictionary;

identifying a plurality of related units for the base unit in the unit dictionary;

determining a most common histogram vector among the related units; and

storing the most common histogram vector in the unit dictionary as a proxy histogram vector for the base unit.

12. The method of claim 11, wherein the related units include extensions of the base unit.

13. The method of claim 1, wherein each element of the histogram vector has a binary value indicating a presence or absence of the target unit in the corresponding concept network.

14. The method of claim 1, further comprising the act of normalizing each of the histogram vectors.

15. A system for processing queries, the system comprising:

a concept network builder module configured to receive a set of previous user queries and to generate a concept network therefrom, the concept network including a plurality of units and a plurality of relationships defined between the units, wherein each unit of the concept network has a frequency weight;

a histogram builder module configured to receive a plurality of concept networks generated by the concept network builder from different sets of previous user queries and further configured to select one of the units and to generate a histogram vector for the selected unit,

wherein the histogram vector has an element corresponding to each of the concept networks, wherein each element of the histogram vector has a value representative of the frequency weight of the unit in the corresponding one of the concept networks; and

storing the histogram vector on a data store accessible by a processor.

16. The system of claim 15, further comprising a unit dictionary configured to store the selected unit in association with the histogram vector generated from the selected unit by the histogram builder module.

17. The system of claim 16, further comprising a histogram analysis module configured to obtain units and histogram vectors for those units from the unit dictionary and to detect a pattern of the histogram vectors.

18. The system of claim 17, wherein the histogram analysis module is further configured to select a plurality of units from the unit dictionary, to sort the selected units based on the histogram vectors, and to define a group of units that have similar histogram vectors.

19. The system of claim 17, wherein the histogram analysis module is further configured to select a base unit from the unit dictionary, to identify a plurality of related units for the base unit in the unit dictionary, to determine a most common histogram vector among the related units, and to store the most common histogram vector in the unit dictionary as a proxy histogram vector for the base unit.

20. The system of claim 16, further comprising a query response module configured to receive a subsequent query including one or more constituent units and to respond to the subsequent query based at least in part on a histogram vector stored in the unit dictionary for at least one of the constituent units.

21. A computer program product comprising a computer readable medium encoded with program code, the program code being executable by a processor, the program code including:

program code for grouping a set of previous queries into a plurality of subsets along a dimension;

program code for generating a concept network for each of the subsets of the previous queries, each concept network including a plurality of units and a plurality of relationships defined between the units, wherein each unit of each concept network has a frequency weight;

program code for selecting one of the units;

program code for constructing a histogram vector for the selected unit, the histogram vector having an element corresponding to each of the concept networks, wherein each element of the histogram vector has a value representative of the frequency weight of the selected unit in the corresponding one of the concept networks; and

program code for storing the histogram vector on a data store accessible by the processor.

22. The computer program product of claim 21, wherein the program code further includes program code for storing the selected unit in a unit dictionary in association with the histogram vector.

23. The computer program product of claim 21, wherein the program code further includes:

program code for receiving a subsequent query;

program code for parsing the subsequent query into one or more constituent units;

program code for obtaining the histogram vector for at least one of the constituent units from the unit dictionary; and

program code for responding to the subsequent query based at least in part on the histogram vector.