Method and System for High Performance Data Metatagging and Data Indexing Using Coprocessors

• US 20080114725A1
• Filed: 11/12/2007
• Published: 05/15/2008
• Est. Priority Date: 11/13/2006
• Status: Active Grant

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Exegy Incorporated
• Inventors: Taylor, David E., Singla, Naveen, Indeck, Ronald S.
• Granted Patent: US 8,326,819 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Disclosed herein is a method and system for hardware-accelerating the generation of metadata for a data stream using a coprocessor. Using these techniques, data can be richly indexed, classified, and clustered at high speeds. Reconfigurable logic such a field programmable gate arrays (FPGAs) can be used by the coprocessor for this hardware acceleration. Techniques such as exact matching, approximate matching, and regular expression pattern matching can be employed by the coprocessor to generate desired metadata for the data stream.

Claims

1. An indexing method comprising:

streaming data through a coprocessor;

generating metadata for the streaming data using the coprocessor; and

generating an index for the streaming data based on the generated metadata.

2. The method of claim 1 wherein the coprocessor comprises a reconfigurable logic device.

3. The method of claim 2 wherein the reconfigurable logic device has firmware deployed thereon, wherein the firmware is configured to perform the metadata generating step.

4. The method of claim 3 wherein the firmware is further configured to perform the index generating step.

5. The method of claim 4 wherein the index generating step comprises generating a plurality of indexes based on the generated metadata.

6. The method of claim 5 wherein the metadata generating step comprises performing an exact matching operation on the streaming data that is keyed by a plurality of words in a plurality of dictionaries, wherein each dictionary corresponds to a different one of the generated indexes.

7. The method of claim 6 wherein the metadata generating step further comprises performing a regular expression pattern matching operation on the streaming data that is keyed by a plurality of pre-defined patterns, wherein each pre-defined pattern corresponds to a different one of the generated indexes such that a plurality of the generated indexes correspond to a plurality of the dictionaries and another plurality of the generated indexes correspond to a plurality of the pre-defined patterns.

8. The method of claim 5 wherein the metadata generating step comprises performing an approximate matching operation on the streaming data that is keyed by a plurality of words in a plurality of dictionaries, wherein each dictionary corresponds to a different one of the generated indexes.

9. The method of claim 8 wherein the metadata generating step further comprises performing a regular expression pattern matching operation on the streaming data that is keyed by a plurality of pre-defined patterns, wherein each pre-defined pattern corresponds to a different one of the generated indexes such that a plurality of the generated indexes correspond to a plurality of the dictionaries and another plurality of the generated indexes correspond to a plurality of the pre-defined patterns.

10. The method of claim 5 wherein the metadata generating step further comprises performing a regular expression pattern matching operation on the streaming data that is keyed by a plurality of pre-defined patterns, wherein each pre-defined pattern corresponds to a different one of the generated indexes.

11. The method of claim 5 wherein the metadata generating step comprises performing a classification operation on the streaming data.

12. The method of claim 5 wherein the metadata generating step comprises performing a histogram generation operation on the streaming data.

13. The method of claim 12 further comprising performing a clustering operation on the streaming data based on the generated histogram.

14. The method of claim 5 further comprising performing feature vector extraction on the streaming data using the firmware.

15. The method of claim 14 wherein the feature vector extraction operation comprises performing a word parsing operation on the streaming data.

16. The method of claim 15 wherein the feature vector extraction operation further comprises performing a stop list filter operation on the streaming parsed data.

17. The method of claim 16 wherein the feature vector extraction operation further comprises performing a stemming operation on the streaming parsed filtered data.

18. The method of claim 5 wherein the streaming data comprises unstructured data.

19. The method of claim 18 wherein the unstructured data comprises a plurality of documents.

20. The method of claim 5 further comprising merging the generated indexes with a plurality of operational indexes stored by a relational database.

21. A method of generating metadata for data, the method comprising:

receiving data;

streaming the received data through a processing device other than a main processor for the system; and

performing a metadata generation operation on the streaming data using the processing device to thereby generate metadata for the streaming data.

22. The method of claim 21 wherein the processing device comprises a coprocessor.

23. The method of claim 22 wherein the coprocessor comprises a reconfigurable logic device.

24. The method of claim 23 wherein the reconfigurable logic device has firmware deployed thereon, the firmware being configured to perform the metadata generation operation.

25. The method of claim 22 wherein the step of performing the metadata generation operation comprises generating an index for the streaming data based on the generated metadata.

26. The method of claim 25 wherein the index generating step comprises concurrently generating a plurality of indexes for the streaming data based on the generated metadata.

27. The method of claim 25 wherein the data stream comprises a plurality of data words, and wherein the step of performing the metadata generation operation comprises:

performing an exact match operation between the streaming data words and a plurality of words in a dictionary; and

in response to finding an exact match between a streaming word and a word in the dictionary, updating an entry in the generated index corresponding to that dictionary word with a pointer to the data word within the streaming data that is an exact match to that dictionary word.

28. The method of claim 27 wherein the step of performing the metadata generation operation comprises concurrently generating a plurality of indexes for the streaming data based on the generated metadata, wherein the exact match operation performing step comprises performing the exact match operation between the streaming data words a plurality of words in a plurality of dictionaries, and wherein each of the dictionaries corresponds to a different one of the generated indexes.

29. The method of claim 28 wherein the index generating step further comprises generating a general index for words within the streaming data that are not exact matches to any of the words within any of the dictionaries.

30. The method of claim 28 wherein at least one of the dictionaries comprises a full English language dictionary.

31. The method of claim 28 wherein at least one of the dictionaries comprises a full foreign language dictionary.

32. The method of claim 28 wherein at least one of the dictionaries comprises a technical dictionary.

33. The method of claim 28 wherein at least one of the dictionaries comprises a medical dictionary.

34. The method of claim 27 wherein the dictionary comprises a list of pre-defined words.

35. The method of claim 34 further comprising changing the content of the dictionary.

36. The method of claim 25 wherein the data stream comprises a plurality of data words, and wherein the step of performing the metadata generation operation comprises:

performing an approximate match operation between the streaming data words and a plurality of words in a dictionary; and

in response to finding an exact match between a streaming word and a word in the dictionary, updating an entry in the generated index corresponding to that dictionary word with a pointer to the data word within the streaming data that is an approximate match to that dictionary word.

37. The method of claim 36 wherein the step of performing the metadata generation operation comprises concurrently generating a plurality of indexes for the streaming data based on the generated metadata, wherein the approximate match operation performing step comprises performing the approximate match operation between the streaming data words and a plurality of words in a plurality of dictionaries, and wherein each of the dictionaries corresponds to a different one of the generated indexes.

38. The method of claim 37 wherein the index generating step further comprises generating a general index for words within the streaming data that are not approximate matches to any of the words within any of the dictionaries.

39. The method of claim 37 wherein at least one of the dictionaries comprises a full English language dictionary.

40. The method of claim 37 wherein at least one of the dictionaries comprises a full foreign language dictionary.

41. The method of claim 37 wherein at least one of the dictionaries comprises a technical dictionary.

42. The method of claim 37 wherein at least one of the dictionaries comprises a medical dictionary.

43. The method of claim 36 wherein the dictionary comprises a list of pre-defined words.

44. The method of claim 43 further comprising changing the content of the dictionary.

45. The method of claim 25 wherein the data stream comprises a plurality of data words, and wherein the step of performing the metadata generation operation comprises:

performing a regular expression pattern matching operation between the streaming data words and a plurality of pre-defined patterns;

concurrently generating a plurality of indexes for the streaming data based on the generated metadata, wherein each of the pre-defined patterns corresponds to a different one of the generated indexes; and

in response to finding an pattern match between a streaming word and a predefined pattern, updating an entry in the generated index corresponding to that predefined pattern with a pointer to the data within the streaming data that is a pattern match to that pre-defined pattern.

46. The method of claim 45 wherein the index generating step further comprises generating a general index for data within the streaming data that is not a pattern match to any of the pre-defined patterns.

47. The method of claim 45 wherein at least one of the pre-defined patterns comprises a credit card number.

48. The method of claim 45 wherein at least one of the pre-defined patterns comprises a social security number.

49. The method of claim 45 wherein at least one of the pre-defined patterns comprises an email address.

50. The method of claim 45 wherein at least one of the pre-defined patterns comprises a telephone number.

51. The method of claim 45 wherein at least one of the pre-defined patterns comprises an Internet uniform resource locator (URL).

52. The method of claim 45 further comprising changing at least one of pre-defined patterns.

53. The method of claim 22 wherein the step of performing the metadata generation operation comprises performing a classification operation on the streaming data.

54. The method of claim 53 wherein the classification operation performing step comprises determining whether portions of the streaming data belong to any of a plurality of predefined classes.

55. The method of claim 54 further comprising generating a plurality of data class indexes for the streaming data based on the classification operation.

56. The method of claim 54 wherein at least one of the pre-defined classes comprises a legal classification.

57. The method of claim 54 wherein at least one of the pre-defined classes comprises a medical classification.

58. The method of claim 54 wherein at least one of the pre-defined classes comprises a news classification.

59. The method of claim 54 wherein at least one of the pre-defined classes comprises a sports classification.

60. The method of claim 54 wherein at least one of the pre-defined classes comprises a classification as to whether a data stream portion contains a pre-defined pattern.

61. The method of claim 54 wherein the pre-defined pattern comprises a pattern for a credit card number.

62. The method of claim 22 wherein the step of performing the metadata generation operation comprises generating a histogram for the streaming data.

63. The method of claim 62 further comprising performing a clustering operation for the data within the streaming data based on the generated histogram.

64. The method of claim 63 further comprising generating an index for the data within the streaming data based on the clustering operation.

65. The method of claim 25 further comprising:

merging the generated index with an existing operational index maintained by a relational database.

66. The method of claim 25 wherein the streaming data comprises unstructured data.

67. The method of claim 66 wherein the unstructured data comprises a plurality of documents.

68. The method of claim 25 wherein the streaming data comprises structured data.

69. The method of claim 25 further comprising pre-processing the streaming data with the coprocessor to generate a plurality of feature vectors for the streaming data and using the generated feature vectors when generating the index.

70. A system for generating metadata for data, the system comprising:

a main processor;

a processing device other than the main processor;

wherein the main processor is configured to direct a stream of data to the processing device; and

wherein the processing device is configured to receive the data stream and perform a metadata generation operation on the data stream to thereby generate metadata for the data stream.

71. The system of claim 70 wherein the processing device comprises a coprocessor.

72. The system of claim 71 wherein the coprocessor comprises a reconfigurable logic device.

73. The system of claim 72 wherein the reconfigurable logic device has firmware deployed thereon, the firmware being configured to perform the metadata generation operation.

74. The system of claim 71 wherein the coprocessor is further configured to generate an index for the data stream based on the generated metadata.

75. The system of claim 74 wherein the coprocessor is further configured to concurrently generate a plurality of indexes for the data stream based on the generated metadata.

76. The system of claim 74 wherein the data stream comprises a plurality of data words, and wherein the coprocessor is configured with an exact matching module, the exact matching module having a dictionary loaded thereon, and wherein the exact matching module is configured to detect any exact matches that exist between the words in the data stream and a plurality of words in the dictionary, and wherein the coprocessor is further configured to, in response to the detection of an exact match between a word in the data stream and a word in the dictionary, update an entry in the generated index corresponding to that dictionary word with a pointer to the data word within the data stream that is an exact match to that dictionary word.

77. The system of claim 76 wherein the coprocessor is further configured to concurrently generate a plurality of indexes for the data stream based on the generated metadata, wherein the exact matching module is further configured to detect any exact matches that exist between the words of the data stream and a plurality of words in a plurality of dictionaries, and wherein each of the dictionaries corresponds to a different one of the generated indexes.

78. The system of claim 77 wherein the coprocessor is further configured to generate a general index for words within the data stream that are not exact matches to any of the words within any of the dictionaries.

79. The system of claim 74 wherein the data stream comprises a plurality of data words, and wherein the coprocessor is configured with an approximate matching module, the approximate matching module having a dictionary loaded thereon, and wherein the approximate matching module is configured to detect any approximate matches that exist between the words in the data stream and a plurality of words in the dictionary, and wherein the coprocessor is further configured to, in response to the detection of an approximate match between a word in the data stream and a word in the dictionary, update an entry in the generated index corresponding to that dictionary word with a pointer to the data word within the data stream that is an approximate match to that dictionary word.

80. The system of claim 79 wherein the coprocessor is further configured to concurrently generate a plurality of indexes for the data stream based on the generated metadata, wherein the approximate matching module is further configured to detect any approximate matches that exist between the words of the data stream and a plurality of words in a plurality of dictionaries, and wherein each of the dictionaries corresponds to a different one of the generated indexes.

81. The system of claim 80 wherein the coprocessor is further configured to generate a general index for words within the data stream that are not approximate matches to any of the words within any of the dictionaries.

82. The system of claim 74 wherein the data stream comprises a plurality of data words, wherein the coprocessor is further configured to concurrently generate a plurality of indexes for the data stream based on the generated metadata, wherein the coprocessor is configured with a regular expression pattern matching module, the regular expression pattern matching module having a plurality of pre-defined patterns loaded thereon, and wherein the regular expression pattern matching module is configured to detect any pattern matches that exist between the words in the data stream and the pre-defined patterns, and wherein the coprocessor is further configured to, in response to the detection of a pattern match between data in the data stream and a pre-defined pattern, update an entry in the generated index corresponding to that pre-defined pattern with a pointer to the data within the data stream that is a pattern match to that pre-defined pattern.

83. The system of claim 82 wherein the coprocessor is further configured to generate a general index for data within the data stream that is not a pattern match to any of the pre-defined patterns.

84. The system of claim 71 wherein the coprocessor is further configured to perform a classification operation on the data stream based on the generated metadata.

85. The system of claim 84 wherein the coprocessor is further configured to determine whether portions of the data stream belong to any of a plurality of predefined classes.

86. The system of claim 85 wherein the coprocessor is further configured to generate a plurality of data class indexes for the data stream based on the classification operation.

87. The system of claim 71 wherein the coprocessor is further configured to generate a histogram for the data stream.

88. The system of claim 87 wherein the processor is further configured to perform a clustering operation for the data within the data stream based on the generated histogram.

89. The system of claim 74 wherein the processor is further configured to merge the generated index with an existing operational index maintained by a relational database.

90. A method of indexing a plurality of web pages, the method comprising:

streaming data for a plurality of web pages through a coprocessor;

generating metadata for the streaming data using the coprocessor; and

generating an index for the web pages based on the generated metadata.

91. The method of claim 90 wherein the coprocessor comprises a reconfigurable logic device.

92. The method of claim 91 wherein the reconfigurable logic device has firmware deployed thereon, wherein the firmware is configured to perform the metadata generating step.

93. The method of claim 92 wherein the firmware is further configured to perform the index generating step.

94. The method of claim 93 wherein the index generating step comprises generating a plurality of indexes based on the generated metadata.

95. The method of claim 94 wherein the metadata generating step comprises performing an exact matching operation on the streaming data that is keyed by a plurality of words in a plurality of dictionaries, wherein each dictionary corresponds to a different one of the generated indexes.

96. The method of claim 95 wherein the metadata generating step further comprises performing a regular expression pattern matching operation on the streaming data that is keyed by a plurality of pre-defined patterns, wherein each pre-defined pattern corresponds to a different one of the generated indexes such that a plurality of the generated indexes correspond to a plurality of the dictionaries and another plurality of the generated indexes correspond to a plurality of the pre-defined patterns.

97. The method of claim 94 wherein the metadata generating step comprises performing an approximate matching operation on the streaming data that is keyed by a plurality of words in a plurality of dictionaries, wherein each dictionary corresponds to a different one of the generated indexes.

98. The method of claim 97 wherein the metadata generating step further comprises performing a regular expression pattern matching operation on the streaming data that is keyed by a plurality of pre-defined patterns, wherein each pre-defined pattern corresponds to a different one of the generated indexes such that a plurality of the generated indexes correspond to a plurality of the dictionaries and another plurality of the generated indexes correspond to a plurality of the pre-defined patterns.

99. The method of claim 94 wherein the metadata generating step further comprises performing a regular expression pattern matching operation on the streaming data that is keyed by a plurality of pre-defined patterns, wherein each pre-defined pattern corresponds to a different one of the generated indexes.

100. The method of claim 94 wherein the metadata generating step comprises performing a classification operation on the streaming data.

101. The method of claim 94 wherein the metadata generating step comprises performing a histogram generation operation on the streaming data.

102. The method of claim 101 further comprising performing a clustering operation on the streaming data based on the generated histogram.

103. The method of claim 94 further comprising performing feature vector extraction on the streaming data using the firmware.

104. The method of claim 103 wherein the feature vector extraction operation comprises performing a word parsing operation on the streaming data.

105. The method of claim 104 wherein the feature vector extraction operation further comprises performing a stop list filter operation on the streaming parsed data.

106. The method of claim 105 wherein the feature vector extraction operation further comprises performing a stemming operation on the streaming parsed filtered data.

107. The method of claim 94 further comprising merging the generated indexes with a plurality of operational indexes stored by a relational database.

108. A method on enriching a bit stream with metadata, the method comprising:

receiving a bit stream corresponding to a data object;

generating metadata for the bit stream using a coprocessor; and

modifying the bit stream based on the generated metadata using the coprocessor.

109. The method of claim 108 further comprising:

classifying the data object based on the generated metadata using the coprocessor; and

wherein the modifying step comprises modifying the bit stream based on the classifying step using the coprocessor.

110. The method of claim 109 wherein the classifying step comprises assigning a classification to the data object, wherein the modifying step comprises adding at least one bit to the bit stream that is indicative of the data object'"'"'s assigned classification.

111. The method of claim 110 wherein the coprocessor comprises a reconfigurable logic device.

112. The method of claim 111 wherein the metadata generating step comprises performing an exact matching operation on the bit stream that is keyed by a plurality of words in a plurality of dictionaries.

113. The method of claim 111 wherein the metadata generating step comprises performing a regular expression pattern matching operation on the bit stream that is keyed by a plurality of pre-defined patterns.

114. The method of claim 111 wherein the metadata generating step comprises performing an approximate matching operation on the bit stream that is keyed by a plurality of words in a plurality of dictionaries.

115. Within a system comprising a main processor and a coprocessor, a method for building a metadata index for unstructured data, the method comprising:

streaming unstructured data through the coprocessor; and

performing a metadata generation operation on the streaming unstructured data using the coprocessor to thereby generate metadata about the unstructured data.

116. The method of claim 115 further comprising:

storing the unstructured data in a data store of unstructured data after it has streamed through the coprocessor; and

storing the generated metadata in a database of structured data.

117. The method of claim 116 wherein the coprocessor comprises a reconfigurable logic device.

118. The method of claim 117 wherein the reconfigurable logic device has firmware deployed thereon, the firmware configured to perform the metadata generation operation.

119. The method of claim 118 wherein the metadata includes an identification of where the unstructured data is stored in the data store of unstructured data.

120. The method of claim 119 wherein the metadata storing step comprises storing the metadata in a RDBMS.

121. The method of claim 119 wherein the streaming step comprises:

streaming all of an enterprise'"'"'s unstructured data through the firmware to thereby generate metadata about that unstructured data.

122. A system for building a metadata index for unstructured data, the system comprising:

a main processor; and

a coprocessor configured to receive a stream of unstructured data and perform a metadata generation operation on the unstructured data stream to thereby generate metadata about the unstructured data.

123. The system of claim 122 wherein the coprocessor comprises a reconfigurable logic device.

124. The system of claim 123 wherein the reconfigurable logic device has firmware deployed thereon, the firmware configured to perform the metadata generation operation.

125. A method for building a metadata index for unstructured data, the method comprising:

streaming unstructured data through firmware deployed on a reconfigurable logic device, wherein the firmware is configured to perform a metadata generation operation on the unstructured data streamed therethrough to thereby generate metadata about the unstructured data;

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

storing the metadata about the unstructured data in a database of structured data.

126. An indexing apparatus comprising:

a reconfigurable logic device configured to receive a stream of data, wherein the reconfigurable logic device comprises a firmware pipeline, wherein the firmware pipeline is configured to index the data stream at hardware speeds.

127. The apparatus of claim 126 wherein the firmware pipeline comprises an exact matching module that operates on the data stream, wherein the exact matching module is keyed with a plurality of dictionaries to thereby generate indexing information for a plurality of indexes.

128. The apparatus of claim 126 wherein the firmware pipeline comprises an approximate matching module that operates on the data stream, wherein the approximate matching module is keyed with a plurality of dictionaries to thereby generate indexing information for a plurality of indexes.

129. The apparatus of claim 126 wherein the firmware pipeline comprises an regular expression pattern matching module that operates on the data stream, wherein the regular expression pattern module is keyed with a plurality of pre-defined patterns to thereby generate indexing information for a plurality of indexes.

130. The apparatus of claim 129 wherein the firmware pipeline further comprises a matching module that operates on the data stream, wherein the matching module is keyed with a plurality of dictionaries to thereby generate indexing information for another plurality of indexes.