Method and apparatus for processing of top-k queries from samples

A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform steps of a method for processing a query, comprising:

• receiving a top-k query with a value for a number of samples and a value of a confidence parameter;
• sampling in accordance to said number of samples;
• determining a top-k weight of a sample top-k set;
• bounding said top-k weight in an interval having an upper bound and a lower bound such that said top-k weight is in said interval with a probability equal to one minus the value of said confidence parameter;
• and
• providing a response to said top-k query in accordance with said upper and lower bounds.

An apparatus for processing a query, comprising:

• means for receiving a top-k query with a value for a number of samples and a value of a confidence parameter;
• means for sampling in accordance to said number of samples;
• means for determining a top-k weight of a sample top-k set;
• means for bounding said top-k weight in an interval having an upper bound and a lower bound such that said top-k weight is in said interval with a probability equal to one minus the value of said confidence parameter;
• and
• means for providing a response to said top-k query in accordance with said upper and lower bounds.