Speculative Stream Scanning

• US 20090287725A1
• Filed: 05/19/2008
• Published: 11/19/2009
• Est. Priority Date: 05/19/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: von Praun, Christoph
• Granted Patent: US 8,001,329 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data

Abstract

A system and method for partitioning a data stream into tokens includes steps or acts of: receiving the data stream; setting a partition scanner to a beginning point in the data stream; identifying likely token boundaries in the data stream using the partition scanner; partitioning the data stream according to the likely token boundaries as determined by the partition scanner, wherein each partition of the partitioned data stream bounded by the likely token boundaries comprises a chunk; and passing the chunk to a next available token scanner, one chunk per token scanner, for identifying at least one actual token within each chunk.

Claims

1. A method for partitioning a data stream into tokens, the method comprising steps of:

receiving the data stream;

setting a partition scanner to a beginning point in the data stream;

identifying likely token boundaries in the data stream using the partition scanner;

partitioning the data stream according to the likely token boundaries as determined by the partition scanner, wherein each partition of the partitioned data stream bounded by the likely token boundaries comprises a chunk; and

passing the chunk to a next available token scanner, one chunk per token scanner, for;

identifying at least one actual token within each chunk.

2. The method of claim 1, further comprising a step of:

reporting the actual token to a client for downstream processing.

3. The method of claim 1 wherein an order of the chunks is defined by the order of their occurrence in the data stream.

4. The method of claim 1 wherein the operation of the partitioning scanner further comprises:

a restart operation that is invoked if a previously identified likely token boundary turns out not to be an actual token boundary;

the restart operation that positions the partitioning scanner to the end of the last actual token boundary in the data stream.

5. The method of claim 1, wherein the step of reporting further comprises identifying the token but not reporting it until the token scanner is determined to be non-speculative.

6. The method of claim 5 wherein the token scanner becomes non-speculative when a preceding token scanner has finished processing its chunk and confirmed that the likely token boundary identified by the partition scanner was an actual token boundary.

7. The method of claim 4, further comprising:

squashing results of token scanners; and

restarting the partition scanner at the actual token boundary.

8. The method of claim 1 wherein the token scanner operating on the chunk at a head of the data stream is a non-speculative token scanner.

9. The method of claim 6 wherein a speculative token scanner is rolled back, the roll back operation undoing the effects of the computation of the token scanner.

10. The method of claim 9 wherein the speculative token scanner transitions from speculative to non-speculative mode when all preceding token scanners have completed such that said speculative token scanner operates at a head of the stream.

11. The method of claim 1 further comprising a step of buffering data from the data stream.

12. A data scanner system comprising:

an input/output interface that receives input comprising a data stream and generates output comprising tokens;

a partition scanner that receives as input the data stream;

identifies likely token boundaries in the data stream; and

partitions the input data stream into a plurality of chunks according to the likely token boundaries; and

a plurality of token scanners for concurrently processing the plurality of chunks to determine whether the likely token boundaries are non-speculative token boundaries and to provide a stream of tokens representing non-speculative token boundaries.

13. The system of claim 12 wherein the data stream comprises a data format selected from a group consisting of:

text, audio, image, and video.

14. The system of claim 12 wherein the token scanners are either speculative or non-speculative, wherein all token scanners can recognize tokens but only non-speculative token scanners can report tokens to a client.

15. The system of claim 12 further comprising a data buffer.

16. A computer program product embodied on a computer readable storage medium and comprising code that, when executed, causes a computer to perform the following receive a data stream;

set a partition scanner to a beginning point in the data stream;

identify likely token boundaries in the data stream using the partition scanner;

partition the data stream according to the likely token boundaries as determined by the partition scanner, wherein each partition of the partitioned data stream bounded by the likely token boundaries comprises a chunk; and

pass the chunk to a next available token scanner, one chunk per token scanner, to identify at least one actual token within each chunk.

17. The computer program product of claim 16 wherein the code further causes the computer to report the actual token to a client for downstream processing.