×

Index and query serving for low latency search of large graphs

  • US 9,576,007 B1
  • Filed: 12/10/2013
  • Issued: 02/21/2017
  • Est. Priority Date: 12/21/2012
  • Status: Active Grant
First Claim
Patent Images

1. A system comprising:

  • a graph-based datastore representing entities connected by predicates; and

    a query serving system including;

    at least one processor, andmemory storing;

    an index of the graph-based datastore, the index including predicate posting lists, each predicate posting list having a plurality of intersection identifiers and, for each intersection identifier, at least one result identifier, the at least one result identifier identifying an entity connected by the predicate to an entity identified by the respective intersection identifier; and

    instructions that, when executed by the at least one processor cause the query serving system to;

    receive a query that executes in at least two stages, each stage associated with a different predicate posting list from the index,execute a forward query path on the stages to generate first query results, wherein executing the forward query path includes;



    applying an expand operator on a predicate posting list for a first stage to generate intersection identifier-result identifier pairs, 

    generating a list of result identifiers as first stage query results, and 

    providing the first stage query results to a downstream stage as incident identifiers, andexecute a reverse query path on the stages to generate second query results, where the first query results include different entities than the second query results.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×