Ranking enterprise graph queries

Patent metadata

Field	Value
Publication number	US-11645289-B2
Application number	US-201414296747-A
Country	US
Kind code	B2
Filing date	Jun 5, 2014
Priority date	Feb 4, 2014
Publication date	May 9, 2023
Grant date	May 9, 2023

Abstract

A graph query is executed against a graph index that connects actors with objects through edges. A graph ranking model is obtained and results of the graph query are ranked, using the graph ranking model, based upon edge data available from edges in the graph that match the query.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
receiving a query identifying a graph ranking model and comprising a graph query portion for execution against a graph index and a content query portion for execution against a content index, the graph index storing edge structures that each identify an actor connected to an object by a corresponding edge that includes edge information indicating a type of relationship between the actor and the object, wherein the type of relationship comprises a type of action performed by the actor relative to the object and the edge information includes weight information that weights actions of a same type relative to one another;
executing the graph query portion against the edge structures in the graph index to obtain matching edge structures as graph search results;
ranking the graph search results using the graph ranking model identified in the query to produce ranked graph search results, wherein each of the ranked graph search results represents a document and comprises a graph search result identifier and a graph search result score, wherein generating the graph search result score comprises:
generating an edge score for each edge in a graph search result based on the weight information for a corresponding edge; and
generating an actor score for the graph search result based on an actor weight for each actor;

executing the content query portion against the content index to obtain matching content search results, wherein each of the content search results represents a document and comprises a content search result identifier and a content search result score;
combining graph search result scores of the ranked graph search results with content search result scores of the content search results to obtain a combined set of results, wherein the combining comprises adding the graph search result scores to the content search result scores to calculate combined search result scores; and
returning the combined set of results as a response to the query, wherein the combined set of results:
comprises a search result identifier and a combined search result score for each document in the combined set of results;
is ordered based on the combined search result scores; and
incudes only documents that appeared in the content search results and the graph search results.

2. The computer-implemented method of claim 1 wherein the graph ranking model ranks the graph search results by:
generating the graph search result score for each graph search result based on the edge information; and
ranking the graph search result based on the graph search result score.

3. The computer-implemented method of claim 2 wherein generating the graph search result score comprises:
generating an edge score for each edge in a selected graph search result;
combining the edge scores to obtain an actor score for each actor in the selected graph search result; and
combining the actor scores to obtain an object score for the object in the selected graph search result.

4. The computer-implemented method of claim 1 wherein:
the edge information includes a timestamp indicative of a time when an action was last performed; and
generating the edge score comprises generating the edge score based on the timestamp.

5. The computer-implemented method of claim 4 wherein generating the edge score based on the timestamp comprises generating the edge score based on a time decay function that reduces the edge score as the timestamp ages.

6. The computer-implemented method of claim 3 wherein combining the edge scores and combining the actor scores are performed using different combination functions.

7. The computer-implemented method of claim 1 wherein receiving the query comprises receiving a graph ranking model identifier that identifies a location of the graph ranking model.

8. The computer-implemented method of claim 1 wherein the graph ranking model comprises a set of features, each feature of the set of features:
corresponding to an action type;
having a feature weight; and
specifying how edge scores of the action type are both calculated and combined.

9. The computer-implemented method of claim 1 wherein:
ranking the graph search results comprises producing an object score for each graph search result based on the edge information;
executing the content query portion comprises generating a score for each of the matching content search results to produce ranked content search results; and
combining the graph search result scores with the content search result scores comprises combining object scores for ranked graph search results with scores for ranked content search results.

10. A search system, comprising:
at least one processor; and
one or more memories storing instructions, that when executed by the at least one processor, cause operations to be performed, the operations comprising:
receiving a set of graph search results related to a graph query portion of a received query, the received query identifying a graph ranking model and comprising the graph query portion for execution against a graph index and a content query portion for execution against a context index, the graph index storing edge structures that each identify an actor connected to an object by a corresponding edge that includes edge information indicating a type of relationship between the actor and the object, wherein the type of relationship comprises a type of action performed by the actor relative to the object and the edge information includes weight information that weights actions of a same type relative to one another;
generating a graph search result score for each graph search result in the set of graph search results according to the graph ranking model identified in the received query, wherein generating the graph search result score comprises:
generating an edge score for each edge in a graph search result based on the weight information for a corresponding edge; and
generating an actor score for the graph search result based on an actor weight for each actor;

ranking, by a graph ranking mechanism, each graph search result in the set of graph search results based on the graph search result score generated for that graph search result to produce ranked graph search results, wherein each ranked graph search result comprises a graph search result identifier and a corresponding graph search result score;
receiving a set of content search results related to the content query portion of the received query;
generating a content search result score for each content search result in the set of content search results;
ranking, by a content ranking mechanism, each content search result in the set of content search results based on the content search result score for that content search result to produce ranked content search results, wherein each ranked content search result comprises a content search result identifier and a corresponding content search result score;
combining the ranked graph search results with the content search results to obtain a combined set of results formed with search results that are in both the ranked graph search results and the ranked set of content search results, wherein the combining comprises combining the graph search result scores of the ranked graph search results with content search result scores of the content search results to calculate combined search result scores; and
providing the combined set of results as a response to the received query, wherein the combined set of results:
comprises a search result identifier and a combined search result score for each document in the combined set of results;
is ordered based on the combined search result sc

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Helvik Torbjorn
• Xing Chen
• Wang Oivind
• Kvalheim Bard
• Bodd Nicolai

Classifications

• G06F16/24578 Primary

  using ranking · CPC title