Verification of data stream computations using third-party-supplied annotations
AssigneesAT&T Intellectual Property I, L.P., Trustees of Dartmouth College
InventorsGraham Robert Cormode, Amit Chakrabarti, Andrew McGregor
Life of this patent
Estimating the term…
Abstract
A third party that performs data stream computation is requested to return not only the solution to the computation, but also “annotations” to the original data stream. The annotations are then used by the data owner (in actuality, a “verifier” associated with the data owner) to check the results of the third party's computations. As implemented, the verifier combines the annotations with the original data, performs some computations, and is then assured of the correctness of the provided solution. The cost of verification is significantly lower to the data owner than the cost of fully processing the data “in house”.
Claims18
A method for verifying third party annotation of data stream processing, the method comprising:
- receiving a data stream at a computer;
- outsourcing the data stream to a third party computer to perform a computation by a third party;
- receiving a result of the computation from the third party computer;
- receiving an annotated version of the data stream from the third party computer;
- defining a help cost H from the annotated version of the data stream;
- defining a number V of bits in memory;
- and
- multiplying the help cost H by the number V of bits to verify the result of the data stream.
A computer-readable memory storing instructions that when executed by a processor cause the processor to perform operations, the operations comprising:
- receiving a data stream;
- outsourcing the data stream to a third party computer to perform a computation by a third party;
- receiving a result of the computation from the third party computer;
- receiving an annotated version of the data stream from the third party computer;
- defining a help cost H from the annotated version of the data stream;
- defining a number V of bits in memory;
- and
- multiplying the help cost H by the number V of bits to verify the result of the data stream.
A system, comprising:
- a processor;
- and
- memory storing code that when executed causes the processor to perform operations, the operations comprising:
- receiving a data stream;
- outsourcing the data stream to a third party computer to perform a computation by a third party;
- receiving a result of the computation from the third party computer;
- receiving an annotated version of the data stream from the third party computer;
- defining a help cost H from the annotated version of the data stream;
- defining a number V of bits in memory;
- and
- multiplying the help cost H by the number V of bits to verify the result of the data stream.
Dependencies are inferred from the claim text.