Method and apparatus for processing streaming data using programmable logic

• US 9,020,928 B2
• Filed: 09/27/2013
• Issued: 04/28/2015
• Est. Priority Date: 04/07/2000
• Status: Expired due to Fees

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Ip Reservoir, LLC
• Inventors: Indeck, Ronald S., Cytron, Ron Kaplan, Franklin, Mark Allen
• Primary Examiner(s): Fleurantin, Jean B
• Application Number:
  US14/039,128
• Publication Number:
  US 20140025656A1
• Time in Patent Office: 578 Days
• Field of Search: 707/712, 707/752, 707/823, 707/825, 709/214, 711/103, 711/111, 711/112, 711/145
• US Class Current: 707/712
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/433 using audio data
• CPC Class Codes: G06F 16/434 using image data, e.g. images, photos, pictures taken by a user
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Methods and apparatuses for processing streaming data using programmable logic are disclosed. With an exemplary embodiment, a programmable logic device can be used to sort streaming data and provide a processor with access to the sorted data. With another exemplary embodiment, an Internet search engine can include a programmable logic device to perform match operations in response to search queries for web pages. With another exemplary embodiment, a programmable logic device is configured to perform match operations on streaming data while a processor is freed to perform other tasks.

Claims

1. An apparatus comprising:

a processor;

a memory;

a bus; and

a programmable logic device for communication with (1) the processor via the bus and (2) the memory, the programmable logic device configured to (1) receive a request from the processor, (2) receive streaming data from the memory, (3) sort the streaming data in response to the received request, wherein the sort operation includes a comparison being performed with respect to the streaming data, and (4) present the sorted data to the bus to thereby provide the processor with access to the sorted data;

wherein the processor is free to perform other tasks while the programmable logic device performs the sort operation;

wherein the sort operation further includes a match operation, the match operation including the comparison, wherein the request comprises a plurality of parameters for controlling the match operation, the parameters comprising data representative of a data key and data representative of an adjustable threshold;

wherein the programmable logic device is further configured to (1) store the data key, (2) store the adjustable threshold, (3) process the streaming data against the stored data key to generate data indicative of a similarity between the streaming data and the data key, and (4) compare the generated data with the stored adjustable threshold to thereby determine whether the streaming data is deemed a match to the data key; and

wherein the adjustable threshold is adjustable to control whether the programmable logic device performs an approximate match operation or an exact match operation, and further to control, for an approximate match operation, a degree of approximate matches returned by the approximate match operation.

2. The apparatus of claim 1 further comprising processor main memory, and wherein the programmable logic device is further configured to perform the sort operation and provide the processor with access to the sorted data without use of the processor main memory.

3. The apparatus of claim 1 wherein the streaming data comprises text data.

4. The apparatus of claim 3 wherein the parameters further comprise a starting location for the streaming data with respect to the match operation and a final location for the streaming data with respect to the match operation for terminating the match operation if no match is found.

5. The apparatus of claim 3 wherein the parameters further comprise data representative of information to be returned by the programmable logic device when a match is found.

6. The apparatus of claim 1 wherein the data key comprises a digital data key, and wherein the programmable logic device is further configured to process portions of the streaming data against the data key on a frame-by-frame basis.

7. The apparatus of claim 1 wherein the match operation comprises a pattern matching operation, and wherein the programmable logic device is further configured to perform the pattern matching operation by continuously comparing a sliding window of the streaming data with the data key to generate the data indicative of the similarity between the streaming data and the data key.

8. The apparatus of claim 1 wherein the memory comprises disk storage.

9. The apparatus of claim 1 wherein the programmable logic device is directly coupled to the memory.

10. An apparatus comprising:

a processor;

a memory;

a cache memory; and

a programmable logic device for communication with the processor and the memory, the programmable logic device configured to (1) receive a request from the processor, (2) receive streaming data from the memory, (3) sort the streaming data in response to the received request, wherein the sort operation includes a comparison being performed with respect to the streaming data, and (4) store the sorted data in the cache memory;

wherein the processor is configured to access the sorted data in the cache memory;

wherein the processor is free to perform other tasks while the programmable logic device performs the sort operation;

wherein the sort operation further includes a match operation, the match operation including the comparison, wherein the request comprises a plurality of parameters for controlling the match operation, the parameters comprising data representative of a data key and data representative of an adjustable threshold;

wherein the programmable logic device is further configured to (1) store the data key, (2) store the adjustable threshold, (3) process the streaming data against the stored data key to generate data indicative of a similarity between the streaming data and the data key, and (4) compare the generated data with the stored adjustable threshold to thereby determine whether the streaming data is deemed a match to the data key; and

wherein the adjustable threshold is adjustable to control whether the programmable logic device performs an approximate match operation or an exact match operation, and further to control, for an approximate match operation, a degree of approximate matches returned by the approximate match operation.

11. The apparatus of claim 10 wherein the streaming data comprises text data.

12. The apparatus of claim 11 wherein the parameters further comprise a starting location for the streaming data with respect to the match operation and a final location for the streaming data with respect to the match operation for terminating the match operation if no match is found.

13. The apparatus of claim 10 wherein the data key comprises a digital data key, and wherein the programmable logic device is further configured to process portions of the streaming data against the data key on a frame-by-frame basis.

14. The apparatus of claim 10 wherein the match operation comprises a pattern matching operation, and wherein the programmable logic device is further configured to perform the pattern matching operation by continuously comparing a sliding window of the streaming data with the data key to generate the data indicative of the similarity between the streaming data and the data key.

15. The apparatus of claim 10 wherein the memory comprises disk storage.

16. The apparatus of claim 10 wherein the programmable logic device is directly coupled to the memory.

17. An apparatus comprising:

a processor; and

a programmable logic device for communication with the processor and a memory, wherein the programmable logic device is directly coupled to the memory, the programmable logic device configured to (1) receive a request from the processor, (2) receive streaming data from the memory, (3) sort the streaming data in response to the received request, wherein the sort operation includes a comparison being performed with respect to the streaming data, and (4) provide the processor with access to the sorted data;

wherein the processor is free to perform other tasks while the programmable logic device performs the sort operation;

wherein the sort operation further includes a match operation, the match operation including the comparison, wherein the request comprises a plurality of parameters for controlling the match operation, the parameters comprising data representative of a data key and data representative of an adjustable threshold; and

wherein the programmable logic device is further configured to (1) store the data key, (2) store the adjustable threshold, (3) process the streaming data against the stored data key to generate data indicative of a similarity between the streaming data and the data key, and (4) compare the generated data with the stored adjustable threshold to thereby determine whether the streaming data is deemed a match to the data key; and

wherein the adjustable threshold is adjustable to control whether the programmable logic device performs an approximate match operation or an exact match operation, and further to control, for an approximate match operation, a degree of approximate matches returned by the approximate match operation.

18. The apparatus of claim 17 wherein the streaming data comprises text data.

19. The apparatus of claim 17 wherein the data key comprises a digital data key, and wherein the programmable logic device is further configured to process portions of the streaming data against the data key on a frame-by-frame basis.

20. The apparatus of claim 17 wherein the match operation comprises a pattern matching operation, and wherein the programmable logic device is further configured to perform the pattern matching operation by continuously comparing a sliding window of the streaming data with the data key to generate the data indicative of the similarity between the streaming data and the data key.

21. The apparatus of claim 17 wherein the memory comprises disk storage.

22. A method comprising:

receiving a request from a processor;

in response to the received request, (1) storing a data key, (2) storing an adjustable threshold, (3) receiving streaming data from a memory, (4) sorting the streaming data, wherein the sorting step includes performing a match operation by (i) processing the streaming data against the stored data key to generate data indicative of a similarity between the streaming data and the data key, and (ii) comparing the generated data with the stored adjustable threshold to thereby determine whether the streaming data is deemed a match to the data key, wherein the request comprises a plurality of parameters for controlling the match operation, the parameters comprising data representative of the data key and data representative of the adjustable threshold, and wherein the adjustable threshold is adjustable to control whether the programmable logic device performs an approximate match operation or an exact match operation, and further to control, for an approximate match operation, a degree of approximate matches returned by the approximate match operation, and (5) providing the processor with access to the sorted data; and

wherein the method steps are performed by a programmable logic device while the processor is free to perform other tasks.

23. An apparatus comprising:

an Internet search engine, the Internet search engine comprising a programmable logic device;

wherein the Internet search engine is configured to (1) receive a search query, the search query being a search query with respect to a plurality of web pages, (2) generate a data key and a threshold based on the search query;

wherein the programmable logic device is configured to (1) receive streaming data from a memory, wherein the streaming data is representative of the web pages, (2) process the streaming data against the data key to generate data indicative of a similarity between the streaming data and the data key, (3) compare the generated data with the threshold to thereby determine whether any of the web pages are deemed a match to the data key, and (4) return data indicative of a hit in response to a determination that a web page is deemed a match to the data key; and

wherein the Internet search engine is further configured to adjust the threshold to control whether the programmable logic device performs an approximate match operation or an exact match operation, and further to control, for an approximate match operation, a degree of approximate matches returned by the approximate match operation.

24. The apparatus of claim 23 wherein the data key comprises a digital data key, and wherein the programmable logic device is further configured to process portions of the streaming data against the data key on a frame-by-frame basis.

25. The apparatus of claim 23 wherein the match operation comprises a pattern matching operation, and wherein the programmable logic device is further configured to perform the pattern matching operation by continuously comparing a sliding window of the streaming data with the data key to generate the data indicative of the similarity between the streaming data and the data key.

26. The apparatus of claim 23 wherein the Internet search engine further comprises a memory, the memory configured to store data representative of the web pages;

and

wherein the programmable logic device is directly coupled to the memory.

27. The apparatus of claim 23 wherein the Internet search engine further comprises a processor, and wherein the processor is free to perform other tasks while the programmable logic device performs the programmable logic tasks.

28. The apparatus of claim 27 wherein the Internet search engine further comprises processor main memory, and wherein the programmable logic device is further configured to perform the programmable logic tasks without use of the processor main memory.

29. An apparatus comprising:

a processor; and

a programmable logic device;

wherein the processor is configured to (1) generate a data key and an adjustable threshold in response to a search request, and (2) communicate the data key and the adjustable threshold to the programmable logic device for controlling a match operation to be performed by the programmable logic device;

wherein the programmable logic device is configured to (1) receive streaming text data from a memory, (2) process the streaming text data against the data key to generate data indicative of a similarity between the streaming text data and the data key, and (3) compare the generated data with the adjustable threshold to thereby determine whether the streaming text data is deemed a match to the data key;

wherein the processor is further configured to adjust the adjustable threshold to control whether the match operation performed by programmable logic device is an approximate match operation or an exact match operation, and further to control, for an approximate match operation, a degree of approximate matches returned by the approximate match operation; and

wherein the processor is free to perform other tasks while the programmable logic device performs the programmable logic tasks.

30. The apparatus of claim 29 further comprising the memory, and wherein the programmable logic device is directly coupled to the memory.

31. The apparatus of claim 29 wherein the data key comprises a digital data key, and wherein the programmable logic device is further configured to process portions of the streaming data against the data key on a frame-by-frame basis.

32. The apparatus of claim 29 wherein the match operation comprises a pattern matching operation, and wherein the programmable logic device is further configured to perform the pattern matching operation by continuously comparing a sliding window of the streaming data with the data key to generate the data indicative of the similarity between the streaming data and the data key.

33. The apparatus of claim 29 wherein the processor comprises a CPU.

34. The apparatus of claim 33 further comprising CPU main memory, and wherein the programmable logic device is further configured to perform the programmable logic tasks without use of the CPU main memory.