Patent Document ID: 8412714
Application ID: 11073966

Base Claim:
1. A method of adaptively evaluating a top-k query with respect to a document, the method comprising: relaxing an original query to form a relaxed query, the original query comprising a tree structure having a plurality of query nodes; based on the relaxed query, forming a plurality of servers, each server corresponding to a respective query node in the tree structure and having a respective server queue configured to store candidate answers that constitute one of partial answers and final answers; processing the candidate answers in the server queues by steps including: adaptively choosing a winning server, from the plurality of servers, that is likely to produce fewest candidate answers after pruning against a top-k set and to whose queue a current candidate answer should be sent; sending the current candidate answer to the winning server's queue; adaptively choosing a next candidate answer to process from among candidate answers in the winning server's queue by selecting an answer with a maximum possible next score, the maximum possible next score determined by adding a current score of the answer to a maximum possible score the answer could receive from its current server; computing a join between the current candidate answer and next candidate answers at the winning server, so as to produce a new current candidate answer; and updating the top-k set with the new current candidate answer only if a score of the new current candidate answer exceeds a score of a top-k answer in a top-k set; and providing the top-k set as an evaluation of the top-k query; wherein the candidate answers include fragments of the document that are less than the entire document and the score of each candidate answer is calculated by calculating scores of progressively smaller fragments of the query that are matched by each candidate answer to be correspondingly smaller scores, the candidate answers including a complete answer to the relaxed query and satisfying all requirements of the relaxed query but satisfying less than all requirements of the original query.

---

Claim 2:
2. The method of claim 1 , wherein: the document is expressed in a nested-structure, document-specific markup language; and the query further comprises: links that are associated with join conditions that define relationships among the query nodes as being children, parents, ancestors or descendants of each other; and a query root node that represents answers to be returned.