# US 2010/0169360 A1 · Method and apparatus for processing of top-k queries from samples

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0169360 A1
- Document ID: US20100169360A1
- Status: Published application
- Kind: A1
- Application number: 12/347,474
- Filed: 2008-12-31
- Published: 2010-07-01
- Earliest claimed: 2008-12-31
- Assignees: AT&T Intellectual Property I, L.P.
- Inventors: Edith Cohen; Nadav Grossaug; Haim Kaplan
- Web page: https://patentgrep.com/patent/US20100169360A1

## CPC

- G06F 16/24578: {using ranking}
- G06F 16/2462: {Approximate or statistical queries}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method and apparatus for processing top-k queries are disclosed. For example, the method receives a top-k query with a value for a number of samples and a value of a confidence parameter. The method samples in accordance to the number of samples, and determines a top-k weight of a sample top-k set. The method bounds the top-k weight in an interval having an upper bound and a lower bound such that the top-k weight is in the interval with a probability equal to one minus the value of the confidence parameter, and provides a response to the top-k query in accordance with the upper and lower bounds.

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
receiving one or more selections for determining said upper bound and said lower bound for said interval, and one or more parameter values for determining said upper bound and said lower bound based on said one or more selections; and
determining said upper bound and said lower bound on the top-k weight in accordance with said selection for determining said upper bound and said lower bound.

### Claim 3 (depends on 1)

The method of claim 1, wherein said upper bound and said lower bound are based on Naïve bounds.

### Claim 4 (depends on 1)

The method of claim 1, wherein said upper bound and said lower bound are based on Cumulative Upper Bounds (CUB).

### Claim 5 (depends on 1)

The method of claim 1, wherein said upper bound and said lower bound are based on a cross-validation bound.

### Claim 6 (depends on 5)

The method of claim 5, wherein said cross-validation bound is a split-sample cross-validation bound.

### Claim 7 (depends on 5)

The method of claim 5, wherein said cross-validation bound is a r-fold cross validation bound.

### Claim 8 (depends on 5)

The method of claim 5, wherein said cross-validation bound is a leave-out cross validation bound.

### Claim 9

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.

### Claim 10 (depends on 9)

The computer-readable medium of claim 9, further comprising:
receiving one or more selections for determining said upper bound and said lower bound for said interval, and one or more parameter values for determining said upper bound and said lower bound based on said one or more selections; and
determining said upper bound and said lower bound on the top-k weight in accordance with said selection for determining said upper bound and said lower bound.

### Claim 11 (depends on 9)

The computer-readable medium of claim 9, wherein said upper bound and said lower bound are based on Naïve bounds.

### Claim 12 (depends on 9)

The computer-readable medium of claim 9, wherein said upper bound and said lower bound are based on Cumulative Upper Bounds (CUB).

### Claim 13 (depends on 9)

The computer-readable medium of claim 9, wherein said upper bound and said lower bound are based on a cross-validation bound.

### Claim 14 (depends on 13)

The computer-readable medium of claim 13, wherein said cross-validation bound is a split-sample cross-validation bound.

### Claim 15 (depends on 13)

The computer-readable medium of claim 13, wherein said cross-validation bound is a r-fold cross validation bound.

### Claim 16 (depends on 13)

The computer-readable medium of claim 13, wherein said cross-validation bound is a leave-out cross validation bound.

### Claim 17

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.

### Claim 18 (depends on 17)

The apparatus of claim 17, further comprising:
means for receiving one or more selections for determining said upper bound and said lower bound for said interval, and one or more parameter values for determining said upper bound and said lower bound based on said one or more selections; and
means for determining said upper bound and said lower bound on the top-k weight in accordance with said selection for determining said upper bound and said lower bound.

### Claim 19 (depends on 17)

The apparatus of claim 17, wherein said upper bound and said lower bound are based on Naive bounds, Cumulative Upper Bounds (CUB) or a cross-validation bound.

### Claim 20 (depends on 19)

The apparatus of claim 19, wherein said cross-validation bound is a split-sample cross-validation bound, a r-fold cross validation bound, or a leave-out cross validation bound.
