Query expansion and query-document matching using path-constrained random walks

摘要

Various technologies described herein pertain to use of path-constrained random walks for query expansion and/or query document matching. Clickthrough data from search logs is represented as a labeled and directed graph. Path-constrained random walks are executed over the graph based upon an input query. The graph includes a first set of nodes that represent queries included in the clickthrough data from search logs, a second set of nodes that represent documents included in the clickthrough data from the search logs, a third set of nodes that represent words from the queries and the documents, and edges between nodes that represent relationships between queries, documents, and words. The path-constrained random walks include traversals over edges of the graph between nodes. Further, a score for a relationship between a target node and a source node representative of the input query is computed based at least in part upon the path-constrained random walks.

主权项

1. A method comprising the following computer-executable acts:
receiving an input query; executing path-constrained random walks over a computer-implemented labeled and directed graph based upon the input query, wherein the labeled and directed graph comprises:
a first set of nodes that are representative of queries comprised in clickthrough data from search logs;a second set of nodes that are representative of documents comprised in the clickthrough data from the search logs;a third set of nodes that are representative of words from the queries and the documents; andedges between nodes that are representative of relationships between the queries, the documents, and the words;wherein the path-constrained random walks comprise traversals over edges of the graph between nodes, the path-constrained random walks traverse the edges of the graph between the nodes in accordance with predefined path types, an each of the predefined path types comprises a respective sequence of relations between the nodes in the graph for traversing as part of a corresponding path-constrained random walk from the path-constrained random walks; and computing a score for a relationship between a target node and a source node representative of the input query based at least in part upon the path-constrained random walks.