Pre-Grant Publication Number: 20070244891
Please help the USPTO examine the application by evaluating the relevance of the publicly submitted prior art to the patent application.
Peer-to-Patent forwards the Top 10 most relevant prior art submissions and their annotations to the United States Patent and Trademark Office.
Review this prior art and click on the thumbs up (or down) to indicate whether this submission should be forwarded to the USPTO.
If you login then you can add an annotation by typing in the box at the bottom of the screen to comment on the relevance of the prior art to the claims of the patent application.
Review this prior art and click on the thumbs up (or down) to indicate whether this submission should be forwarded to the USPTO.
If you login then you can add an annotation by typing in the box at the bottom of the screen to comment on the relevance of the prior art to the claims of the patent application.
Prior Art Detail
Summary / Description
| Summary / Description | Review article as of 2002. Provides gentle introduction and describes state of the art as of a few years ago. |
Basic Information
| Type of Prior Art | Online Publication |
| URL | http://portal.acm.org/citation.... |
| Author/Creator | Brian Babcock et. al. |
| Title | Models and issues in data stream systems |
| Publication Date | 2002 |
| Publisher | Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems |
| Directions to Document Location | |
| Additional Information | |
Notes / To Do
| Notes | |
Excerpt
Excerpt A more ambitious approach to handling ad hoc queries that reference past data is to maintain summaries of data streams ... that can be used to give approximate answers to future ad hoc queries. Taking this approach requires making a decision in advance about the best way to use memory resources to give good approximate answers to a broad range of possible future queries. |
Relevance
Claims
1
A method of evaluating elements in a data stream, said method comprising:
scanning said elements in one pass;
as said elements are scanned, randomly selecting a predetermined number of scanned elements for storage in a data bucket;
storing said predetermined number of said scanned elements in said data bucket; and
at multiple selected times during said scanning, selecting a sample of said scanned elements from said data bucket such that multiple samples are obtained and such that said multiple samples comprise uniform samples for specified intervals immediately prior to said selected times.
Relevance
Random selection of elements is prior art. Assigning said elements to buckets is also prior art, more commonly termed "Histograms".
Random selection of elements is prior art. Assigning said elements to buckets is also prior art, more commonly termed "Histograms".
Claim Chart
All
3
The method of Claim 1, wherein later scanned elements are selected for storage in said data bucket with a greater probability than earlier scanned elements and wherein later scanned elements are selected from said data bucket with a lesser probability than earlier scanned elements.
Relevance
This technique implements a form of "sliding window" so that old data does not influence later calculations. Sliding window is a common technique in data stream analysis, though there are many ways to implement it. This claim does not appear to specify the implementation.
This technique implements a form of "sliding window" so that old data does not influence later calculations. Sliding window is a common technique in data stream analysis, though there are many ways to implement it. This claim does not appear to specify the implementation.
Claim Chart
All
6
The method of Claim 5, wherein said estimating comprises:
identifying a right-most element in each of said multiple samples;
for each sample, determining if a majority of other elements in said sample have a greater value than said right-most element;
if so, placing said right-most element in a set of right most-elements; and
estimating said number as being between half and twice a size of said set.
Relevance
Reviewer should consider whether this method of evaluating the samples is novel, or a straightforward implementation of V-Optimal Histograms.
Reviewer should consider whether this method of evaluating the samples is novel, or a straightforward implementation of V-Optimal Histograms.
Claim Chart
All
