Method and system for high performance integration, processing and searching of structured and unstructured data

• US 10,191,974 B2
• Filed: 07/15/2016
• Issued: 01/29/2019
• Est. Priority Date: 11/13/2006
• Status: Active Grant

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Ip Reservoir, LLC
• Inventors: Indeck, Ronald S., Indeck, David Mark, Singla, Naveen, Taylor, David E.
• Primary Examiner(s): Le, Debbie M
• Application Number:
  US15/211,864
• Publication Number:
  US 20160328470A1
• Time in Patent Office: 928 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Disclosed herein are methods and systems for integrating an enterprise'"'"'s structured and unstructured data to provide users and enterprise applications with efficient and intelligent access to that data. In accordance with exemplary embodiments, the generation of classification information about unstructured data can be hardware-accelerated by processing streaming unstructured data through a reconfigurable logic device, a graphics processor unit (GPU), or chip multi-processor (CMP) to generate the classification metadata about the unstructured data.

Claims

1. A method for low latency stream indexing, the method comprising:

receiving streaming unstructured data into a member of the group consisting of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP), the streaming unstructured data comprising a plurality of data objects, wherein the member has a plurality of parallel processing engines deployed thereon;

the parallel processing engines analyzing the data objects while the data objects stream through the member to perform a classification operation that determines classification metadata about the data objects; and

creating an association that is physically represented in memory between the determined classification metadata and the data objects, wherein the creating step comprises generating a classification index about the streaming unstructured data from the classification metadata and the associations between the classification metadata and the corresponding data objects, the classification index for subsequent querying to locate data items of interest based on the associations between the classification metadata and the data objects.

2. The method of claim 1 further comprising storing the generated classification index in a database for subsequent querying.

3. The method of claim 2 wherein the classification index is stored as structured data in the database, the method further comprising:

storing the streaming unstructured data in a data store of unstructured data;

receiving a query that is directed toward a combination of structured data and unstructured data;

accessing structured data in the database according to the classification index in response to the query to identify a subset of the unstructured data that is to be analyzed against the query; and

performing a query-specified data analysis operation on the identified subset of unstructured data to thereby generate data for a response to the query;

wherein the accessing step is conducted by a processor; and

wherein the step of performing the query-specified data analysis operation is conducted by the member.

4. The method of claim 1 wherein the member comprises a reconfigurable logic device, and wherein the parallel processing engines are deployed as a firmware pipeline on the reconfigurable logic device.

5. The method of claim 4 wherein the firmware pipeline comprises matching logic, and wherein the analyzing step comprises the matching logic comparing a plurality of the streaming data objects against a plurality of defined terms to determine which of the defined terms are present in the data objects, each defined term having an association with a classification.

6. The method of claim 5 wherein the firmware pipeline further comprises scoring memory logic downstream from the matching logic, and wherein the analyzing step further comprises:

the scoring memory logic generating, for each of a plurality of the data objects, a count corresponding to the classification, the count indicating how prevalent the defined terms associated with the count'"'"'s corresponding classification are within that data object.

7. The method of claim 6 wherein the comparing step comprises the matching logic comparing a plurality of the data objects against a plurality of defined terms to determine which of the defined terms are present in the data objects, each defined term having an association with a classification from among a plurality of classifications;

and

wherein the count generating step comprises the scoring memory logic generating, for each of a plurality of the data objects, a plurality of counts corresponding to the classifications, each count corresponding to a classification and indicating how prevalent the defined terms associated with that count'"'"'s corresponding classification are within that data object.

8. The method of claim 7 wherein the firmware pipeline further comprises decision logic downstream from the scoring memory logic, and wherein the analyzing step further comprises:

the decision logic assigning a classification to each of a plurality of the data objects based on the counts generated by the scoring memory logic.

9. The method of claim 8 wherein the classification assigning step comprises the decision logic, for each of a plurality of the data objects, (1) comparing the counts for that data object to a threshold, and (2) for each count that exceeds the threshold, assigning the classification corresponding to that count to that data object.

10. The method of claim 9 wherein the classification assigning step results in a plurality of the data objects being assigned to a plurality of the classifications.

11. The method of claim 7 wherein the matching logic includes a plurality of dictionaries, each dictionary corresponding to a classification from among the classifications and comprising the defined terms associated with that classification, and wherein the comparing step comprises:

the matching logic comparing the streaming data objects against each dictionary in parallel.

12. The method of claim 5 wherein the comparing step comprises matching logic performing a plurality of exact matching operations on the streaming unstructured data with respect to a plurality of the defined terms.

13. The method of claim 12 wherein the performing step comprises the matching logic performing a plurality of the exact matching operations in parallel on the streaming data objects with respect to a plurality of the defined terms.

14. The method of claim 5 wherein the comparing step comprises matching logic performing a plurality of approximate matching operations on the streaming data objects with respect to a plurality of the defined terms.

15. The method of claim 14 wherein the performing step comprises the matching logic performing a plurality of the approximate matching operations in parallel on the streaming data objects with respect to a plurality of the defined terms.

16. The method of claim 5 wherein the comparing step comprises matching logic performing a plurality of regular expression pattern matching operations on the streaming data objects with respect to a plurality of the defined terms.

17. The method of claim 16 wherein the performing step comprises the matching logic performing a plurality of the regular expression pattern matching operations in parallel on the streaming data objects with respect to a plurality of the defined terms.

18. The method of claim 4 further comprising:

the firmware pipeline pre-processing the streaming unstructured data by (i) parsing the data objects into a plurality of words, (ii) generating a data object identifier that corresponds to each data object, wherein each data object identifier is indicative of its corresponding data object'"'"'s position within the streaming unstructured data, and (iii) generating a position identifier that corresponds to each parsed word, wherein each position identifier is indicative of its corresponding word'"'"'s position within the streaming unstructured data; and

wherein the analyzing step comprises the firmware pipeline performing the analyzing step on the parsed words.

19. The method of claim 4 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA), the FPGA having the firmware pipeline deployed thereon.

20. The method of claim 1 wherein the creating step further comprises tagging the streaming data objects with their associated classification metadata.

21. The method of claim 1 wherein the member comprises a GPU.

22. The method of claim 1 wherein the member comprises a CMP.

23. The method of claim 1 wherein the member is part of a coprocessor that offloads the classification operation from another processor.

24. An apparatus for low latency stream indexing, the apparatus comprising:

a member of the group consisting of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP), the member configured to receive streaming unstructured data, the streaming unstructured data comprising a plurality of data objects, wherein the member has a plurality of parallel processing engines arranged as a pipeline deployed thereon;

wherein the parallel processing engines are configured to (1) analyze the data objects while the data objects stream through the pipeline to perform a classification operation that determines classification metadata about the data objects, and (2) create an association that is physically represented in a memory between the determined classification metadata and the data objects; and

wherein the pipeline is configured to create the association through generation of a classification index about the streaming unstructured data from the classification metadata and the associations between the classification metadata and the corresponding data objects, the classification index for subsequent querying to locate data items of interest based on the associations between the classification metadata and the data objects.

25. The apparatus of claim 24 wherein the member comprises a reconfigurable logic device, and wherein the pipeline comprises a firmware pipeline on the reconfigurable logic device.

26. The apparatus of claim 25 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA), the FPGA having the firmware pipeline deployed thereon.

27. The apparatus of claim 24 wherein the member comprises a GPU.

28. The apparatus of claim 24 wherein the member comprises a CMP.

29. The apparatus of claim 24 wherein the member is part of a coprocessor that offloads the classification operation and the classification index generation from another processor.

41. The apparatus of claim 25 wherein the firmware pipeline is further configured to tag the streaming data objects with the classification metadata associated therewith.

42. The apparatus of claim 25 wherein the firmware pipeline is further configured to (1) pre-process the streaming unstructured data by (i) parsing the data objects into a plurality of words, (ii) generating a data object identifier that corresponds to each data object, wherein each data object identifier is indicative of its corresponding data object'"'"'s position within the streaming unstructured data, and (iii) generating a position identifier that corresponds to each parsed word, wherein each position identifier is indicative of its corresponding word'"'"'s position within the streaming unstructured data, and (2) perform the analysis operation on the parsed words.

30. An apparatus comprising:

a reconfigurable logic device configured to receive streaming unstructured data, the streaming unstructured data comprising a plurality of data objects, wherein the reconfigurable logic device has a plurality of parallel processing engines arranged as a firmware pipeline deployed thereon;

wherein the parallel processing engines are configured to (1) analyze the data objects while the data objects stream through the firmware pipeline to perform a classification operation that determines classification metadata about the data objects, and (2) create an association that is physically represented in a memory between the determined classification metadata and the data objects; and

wherein the firmware pipeline comprises matching logic, and wherein the matching logic is configured to compare a plurality of the streaming data objects against a plurality of defined terms to determine which of the defined terms are present in the data objects, each defined term having an association with a classification.

31. The apparatus of claim 30 wherein the firmware pipeline further comprises scoring memory logic downstream from the matching logic, wherein the scoring memory logic is configured to generate, for each of a plurality of the data objects, a count corresponding to the classification, the count indicating how prevalent the defined terms associated with the count'"'"'s corresponding classification are within that data object.

32. The apparatus of claim 31 wherein the matching logic is further configured to compare a plurality of the data objects against a plurality of defined terms to determine which of the defined terms are present in the data objects, each defined term having an association with a classification from among a plurality of classifications;

and

wherein the scoring memory logic is further configured to generate, for each of a plurality of the data objects, a plurality of counts corresponding to the classifications, each count corresponding to a classification and indicating how prevalent the defined terms associated with that count'"'"'s corresponding classification are within that data object.

33. The apparatus of claim 32 wherein the firmware pipeline further comprises decision logic downstream from the scoring memory logic, wherein the decision logic is configured to assign a classification to each of a plurality of the data objects based on the counts generated by the scoring memory logic.

34. The apparatus of claim 32 wherein the matching logic includes a plurality of dictionaries, each dictionary corresponding to a classification from among the classifications and comprising the defined terms associated with that classification;

and

wherein the matching logic is further configured to compare the streaming data objects against each dictionary in parallel.

35. The apparatus of claim 30 wherein the matching logic is further configured to perform a plurality of exact matching operations on the streaming unstructured data with respect to a plurality of the defined terms.

36. The apparatus of claim 35 wherein the matching logic is further configured to perform a plurality of the exact matching operations in parallel on the streaming data objects with respect to a plurality of the defined terms.

37. The apparatus of claim 30 wherein the matching logic is further configured to perform a plurality of approximate matching operations on the streaming data objects with respect to a plurality of the defined terms.

38. The apparatus of claim 37 wherein the matching logic is further configured to perform a plurality of the approximate matching operations in parallel on the streaming data objects with respect to a plurality of the defined terms.

39. The apparatus of claim 30 wherein the matching logic is further configured to perform a plurality of regular expression pattern matching operations on the streaming data objects with respect to a plurality of the defined terms.

40. The apparatus of claim 39 wherein the matching logic is further configured to perform a plurality of the regular expression pattern matching operations in parallel on the streaming data objects with respect to a plurality of the defined terms.