Extracting semantic relations from query logs

• US 7,895,235 B2
• Filed: 12/19/2007
• Issued: 02/22/2011
• Est. Priority Date: 12/19/2007
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Tiberi, Alessandro, Baeza-Yates, Ricardo
• Primary Examiner(s): Channavajjala; Srirama
• Assistant Examiner(s): Le; Jessica N
• Application Number:
  US11/960,353
• Publication Number:
  US 20090164895A1
• Time in Patent Office: 1,161 Days
• Field of Search: None
• US Class Current: 707/791
• CPC Class Codes: G06F 16/3349 Reuse of stored results of previous queries
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Methods, systems, and apparatuses for associating queries of a query log are provided. The query log lists a plurality of queries and a set of clicked URLs for each query. Each query is designated to be a node of a plurality of nodes. A plurality of edges is determined. A URL is designated to be an edge for a pair of queries if the URL is indicated as clicked in the sets of clicked URLs for both queries of the pair. The nodes and edges are displayed in a graph. Each edge may be displayed in the graph as a line connected between a pair of nodes that correspond to the pair of queries of the pair of nodes. The edges may be classified. Furthermore, the edges and/or the nodes may be weighted. Edges and/or nodes may be filtered from display based on their weights and/or on other criteria.

Claims

1. A method of associating queries of a query log that lists a plurality of queries and a plurality of clicked uniform resource locators (URL), the plurality of clicked URLs including a set of one or more clicked URLs for each query of the plurality of queries, comprising:

designating each query of the plurality of queries to be a node of a plurality of nodes using at least one processor;

determining a plurality of edges, including designating a URL to be an edge for a pair of queries if the URL is indicated as clicked in a set of clicked URLs for a first query of the pair and in a set of clicked URLs for a second query of the pair; and

displaying the plurality of nodes and the plurality of edges in a graph.

2. The method of claim 1, wherein said displaying the plurality of nodes and the plurality of edges in a graph comprises:

displaying each edge in the graph as a line connected between a pair of nodes displayed in the graph that correspond to the pair of queries having sets of clicked URLs that both indicate the URL of the edge as clicked.

3. The method of claim 2, further comprising:

classifying each edge;

wherein said displaying each edge in the graph as a line connected between a pair of nodes displayed in the graph that correspond to the pair of queries having sets of clicked URLs that both indicate the URL of the edge as clicked further comprises

displaying the line to graphically indicate the classification of the edge.

4. The method of claim 3, wherein said classifying each edge comprises:

classifying an edge as having a first classification if a first query and a second query of the pair of queries that both indicate the URL of the edge as clicked have substantially equivalent sets of clicked URLs;

classifying the edge as having a second classification if the set of clicked URLs of the first query is lesser in size than and substantially included in the set of clicked URLs of the second query; and

classifying the edge as having a third classification if the set of clicked URLs of the first query is overlapping with the set of clicked URLs of the second query and the edge is not classifiable according to the first or second classifications.

5. The method of claim 1, further comprising:

calculating a weight for each edge of the plurality of edges.

6. The method of claim 5, wherein said displaying the plurality of nodes and the plurality of edges in a graph comprises:

only displaying edges in the graph that have calculated weights greater than a predetermined weight threshold.

7. The method of claim 1, wherein said displaying the plurality of nodes and the plurality of edges in a graph comprises:

only displaying nodes in the graph for queries having sets of one or more clicked URLs that include numbers of clicked URLs greater than a predetermined threshold number of clicked URLs.

8. A query log analyzing system, comprising:

at least one server that includes at least one processor;

a query log parser constructor implemented at least partially by the at least one processor that is configured to receive a query log that lists a plurality of queries and a plurality of clicked uniform resource locators (URL), the plurality of clicked URLs including a set of one or more clicked URLs for each query of the plurality of queries, wherein the query log parser is configured to designate each query of the plurality of queries to be a node of a plurality of nodes; and

an edge determiner configured to determine a plurality of edges for the plurality of URLs of the query log, wherein the edge determiner is configured to designate a URL to be an edge for a pair of queries if the URL is indicated as clicked in a set of clicked URLs for a first query of the pair and in a set of clicked URLs for a second query of the pair.

9. The system of claim 8, further comprising:

a display module configured to enable display the plurality of nodes and the plurality of edges in a graph.

10. The system of claim 9, wherein the display module is configured to enable display of each edge in the graph as a line connected between a pair of nodes displayed in the graph that correspond to the pair of queries having sets of clicked URLs that both indicate the URL of the edge as clicked.

11. The system of claim 10, further comprising:

an edge classifier configured to classify each edge;

wherein the display module is configured to display the line with a graphical indication of the classification of the edge corresponding to the line.

12. The system of claim 11, wherein the edge classifier is configured to classify an edge as having a first classification if a first query and a second query of the pair of queries that both indicate the URL of the edge as clicked have substantially equivalent sets of clicked URLs;

wherein the edge classifier is configured to classify the edge as having a second classification if the set of clicked URLs of the first query is lesser in size than and substantially included in the set of clicked URLs of the second query; and

wherein the edge classifier is configured to classify the edge as having a third classification if the set of clicked URLs of the first query is overlapping with the set of clicked URLs of the second query and the edge is not classifiable according to the first or second classifications.

13. The system of claim 9, further comprising:

an edge weight calculator configured to calculate a weight for each edge of the plurality of edges.

14. The system of claim 13, further comprising:

an edge filter configured to filter edges from display in the graph that have calculated weights greater than a predetermined weight threshold.

15. The system of claim 9, further comprising:

a node filter configured to filter nodes from display in the graph for queries having sets of one or more clicked URLs that include numbers of clicked URLs greater than a predetermined threshold number of clicked URLs.

16. A computer program product comprising a computer usable storage medium having computer readable program code means embodied in said medium for associating queries of a query log that lists a plurality of queries and a plurality of clicked uniform resource locators (URL), the plurality of clicked URLs including a set of one or more clicked URLs for each query of the plurality of queries, the computer program product comprising:

a first computer readable program code means for enabling a processor to designate each query of the plurality of queries to be a node of a plurality of nodes;

a second computer readable program code means for enabling a processor to determine a plurality of edges, including computer readable program code means for enabling a processor to designate a URL to be an edge for a pair of queries if the URL is indicated as clicked in a set of clicked URLs for a first query of the pair and in a set of clicked URLs for a second query of the pair; and

a third computer readable program code means for enabling a processor to cause display of the plurality of nodes and the plurality of edges in a graph.

17. The computer program product of claim 16, wherein said third computer readable program code means comprises:

a fourth computer readable program code means for enabling a processor to cause display of each edge in the graph as a line connected between a pair of nodes displayed in the graph that correspond to the pair of queries having sets of clicked URLs that both indicate the URL of the edge as clicked.

18. The computer program product of claim 17, further comprising:

a fifth computer readable program code means for enabling a processor to classify each edge;

wherein said fourth computer readable program code means further comprises

a sixth computer readable program code means for enabling a processor to cause display of the line to graphically indicate the classification of the edge.

19. The computer program product of claim 18, wherein said fifth computer readable program code means comprises:

a seventh computer readable program code means for enabling a processor to classify an edge as having a first classification if a first query and a second query of the pair of queries that both indicate the URL of the edge as clicked have substantially equivalent sets of clicked URLs;

a eighth computer readable program code means for enabling a processor to classify the edge as having a second classification if the set of clicked URLs of the first query is lesser in size than and substantially included in the set of clicked URLs of the second query; and

a ninth computer readable program code means for enabling a processor to classify the edge as having a third classification if the set of clicked URLs of the first query is overlapping with the set of clicked URLs of the second query and the edge is not classifiable according to the first or second classifications.

20. The computer program product of claim 16, further comprising:

a fifth computer readable program code means for enabling a processor to calculate a weight for each edge of the plurality of edges.

21. The computer program product of claim 20, wherein said fourth computer readable program code means comprises:

a sixth computer readable program code means for enabling a processor to filter edges from display in the graph that have calculated weights greater than a predetermined weight threshold.

22. The computer program product of claim 16, wherein said fourth computer readable program code means comprises:

a fifth computer readable program code means for enabling a processor to filter nodes from display in the graph for queries having sets of one or more clicked URLs that include numbers of clicked URLs greater than a predetermined threshold number of clicked URLs.