Adaptive processing of top-k queries in nested-structure arbitrary markup language such as xml

An apparatus for adaptively evaluating a top-k query with respect to a document, the apparatus comprising:

• a processor;
• a memory to store computer program instructions, the computer program instructions when executed on the processor cause the processor to perform operations 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 operations 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.

A tangible computer readable medium storing computer program instructions for adaptively evaluating a query with respect to a document that is expressed in a nested-structure, document-specific markup language, which when executed on a processor, cause the processor to perform operations 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 operations 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.

An apparatus for adaptively evaluating a query with respect to a document that is expressed in a nested-structure, document-specific markup language, the apparatus comprising:

• a processor;
• a memory to store computer program instructions, the computer program instructions when executed on the processor cause the processor to perform operations comprising:
• receiving an original query that is expressed as a tree having a degree d≧3, the tree including query nodes and links that define relationships among the query nodes as being parents, children, ancestors or descendants of each other;
• relaxing the original query to form a relaxed query;
• calculating scores for respective candidate answers that include one of partial answers and final answers, 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, a score including:
• a first portion determined by how many children or descendants a first node has, that are at a given level beneath the first node and that satisfy a first query requirement for that given level;
• and
• a second portion determined by what fraction of all a second node's children or descendants at a predetermined level, satisfy a second query requirement for that second node;
• and
• applying the scores to govern a processing order of the candidate answers to arrive at an evaluation of the query wherein the score is directly proportional to a mathematical product of the first portion and the second portion, the candidate answers include fragments of the document that are less than the entire document, and a next candidate answer to process from among the candidate answers is chosen 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;
• the calculating further comprising:
• calculating scores for respective candidate answers comprises calculating scores of progressively smaller fragments of the query that are matched by a candidate answer to be correspondingly smaller scores.