US 8,412,714 B2Granted

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

AssigneeAT&T Intellectual Property II, L.P.

InventorsSihem Amer-Yahia, Nikolaos Koudas, Amélie Marian-Guerrier, Divesh Srivastava

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method of adaptively evaluating a top-k query involves (1204) forming a servers having respective server queues storing candidate answers, processing (1322) the candidate answers, and (1232) providing a top-k set as a query evaluation. Processing includes (1402) adaptively choosing a winning server to whose queue a current candidate answer should be sent; (1404) sending the current candidate answer to the winning server's queue; (1334) adaptively choosing a next candidate answer to process from the winning server's queue; (1336) 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 (1338) 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. A method of calculating scores for candidate answers is also provided.

Claims8

Dependent claims

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.

9 more elements

A method of adaptively evaluating a query with respect to a document that is expressed in a nested-structure, document-specific markup language, the method 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.

7 more elements

Dependencies are inferred from the claim text.