Searching backward to speed up query

Abstract

A method, computing device, and a non-transitory computer-readable medium are provided for performing a context-aware search by finding a set of nodes that are mapped to a given text or other value and, for each node in the set of nodes, performing a reverse path lookup to determine whether the node satisfies a given context. The query processor performs the reverse path lookup for a node by traversing up a node tree away from the node, using a stored mapping from the node to a parent of the node. Using mappings from nodes to parent nodes, the node tree is traversed backwards from the node up to distant ancestor nodes through parent nodes. An optimizer instructs the query processor to perform a value-based portion of the search before a path-based portion of the search based on value distribution statistics and path distribution statistics.