Testing and spot-checking of data streams
Joan Feigenbaum, Sathya Kannan, Michael Strauss, Mahesh Viswanathan · 2000
We consider the tasks of testing and spot-checking for data streams. These testers and spotcheckers are potentially useful in real-time or near real-time applications that process huge datasets. Crucial aspects of the computational model include the space complexity of the testers and spotcheckers (ideally much lower than the size of the input stream) and the number of passes that the tester or spot-checker must make over the input stream (ideally one, because the original stream may be too large to store for a second pass). A sampling-tester [GGR98] for a property P samples some (but usually not all) of its input and, with high probability, outputs PASS if the input has property P and FAIL if the input is far from having P , for an appropriate sense of "far." A streaming-tester for a property P of one or more input streams takes as input one or more data streams and, with high probability, outputs PASS if the streams have property P and FAIL if the streams are far from havin...