Indexing and querying semi-structured data

• US 9,507,848 B1
• Filed: 09/23/2010
• Issued: 11/29/2016
• Est. Priority Date: 09/25/2009
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Huang, Chengdu, Zhu, Qingbo, Li, Zhenmin, Xanthos, Spiros, Zhou, Yuanyuan
• Primary Examiner(s): Shmatov, Alexey
• Application Number:
  US12/888,749
• Time in Patent Office: 2,259 Days
• Field of Search: 707/711, 707/742, 707/E17.002, 707/E17.057, 707/E17.083, 707/E17.123, 707/999, 707/999.001, 707/999.003, 707/755
• US Class Current: 1/1
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures

Abstract

Generating an inverted index is disclosed. Semi-structured data from a plurality of sources is parsed to extract structure from at least a portion of the semi-structured data. The inverted index is generated using the extracted structure. The inverted index includes a location identifier and a data type identifier for one or more entries of the inverted index.

Claims

1. A method for generating an inverted index comprising:

receiving a file comprising data, wherein at least a portion of the data is unstructured or semi-structured data;

parsing the data to extract structure from at least a portion of the data, wherein the parsing comprises (i) dividing the data into logical groupings, (ii) determining whether each of the logical groupings matches any of a plurality of stored parsing expressions, (iii) applying each of the matching parsing expressions to a corresponding one of the logical groupings to produce elements of data;

(iv) applying a general parser to any of the logical groupings that do not match any of the stored parsing expressions to produce elements of data, and (v) identifying a data type associated with each of the elements of data produced in (iii) and (iv);

generating the inverted index using the extracted structure, wherein each item in the inverted index includes one of the elements of data produced in (iii) and (iv), a location identifier, a position identifier, and a data type identifier for one or more entries of the inverted index,

wherein the location identifier specifies an identifier of the file that contains the element of data, the position identifier specifies a position of the element of data within the file, and the data type identifier specifies the data type of the element of data, and the inverted index is utilized to respond to queries to identify patterns within the data.

2. The method as recited in claim 1, wherein the data includes at least a portion of one or more of the following:

a support artifact, a log, a configuration file, a script, a program code, and a system status.

3. The method as recited in claim 1, wherein the extracted structure is associated with one or more of the following:

a tag, a data type, a metadata, a marker, and a hierarchy of a field of the semi-structured data.

4. The method as recited in claim 1, further comprising receiving additional data from a plurality of data sources, parsing the additional data, and associating the data sources with corresponding entries of the inverted index.

5. The method as recited in claim 4, wherein parsing the additional data from the plurality of data sources is performed in a distributed processing environment, each of a plurality of worker processes parses at least a portion of the additional data, and a master process manages processing results of the worker processes.

6. The method as recited in claim 1, wherein parsing the data further includes determining whether at least a portion of the data is associated with a preconfigured parser.

7. The method as recited in claim 6, wherein the step of determining whether at least a portion of the data is associated with a preconfigured parser comprises identifying at least one of a name of the file, a type of the file, a location of the file, a rule associated with the file, header information in the file, a configuration file associated with the file, a scheme associated with the file, or a label associated with the file that specified the preconfigured parser.

8. The method as recited in claim 1,

wherein the data of the file is organized into groups of content, wherein first elements of the groupings are aligned on fixed boundaries and within the file, the fixed boundaries having a pre-determined fixed boundary size;

and

wherein the position identifier is associated with the fixed boundary size used to determine a grouping of content within the data.

9. The method as recited in claim 8, further comprising:

determining a message comprised of a plurality of terms exists within the received file based on position identifiers for the plurality of terms being within a range of the fixed boundary size.

10. The method as recited in claim 1, wherein the inverted index associates for at least one entry, an instance identifier for each of a plurality of locations where the element of data corresponding to the entry appears in the file.

11. The method as recited in claim 10, further comprising sorting the instance identifiers associated with the element.

12. The method as recited in claim 1, further comprising receiving a search query, and processing the received search query.

13. The method as recited in claim 12, wherein the processing the received search query includes translating the received search query to a different query form used to search the inverted index.

14. The method as recited in claim 1, further comprising automatically generating a report at least in part by querying the inverted index.

15. The method as recited in claim 1, wherein at least one of the logical groupings is parsed by multiple parsers.

16. A system for generating an inverted index, comprising:

a processor configured to;

receive a file comprising data, wherein at least a portion of the data is unstructured or semi-structured data;

parse the data to extract structure from at least a portion of the data, wherein the parsing comprises (i) dividing the data into logical groupings, (ii) determining whether each of the logical groupings matches any of a plurality of stored parsing expressions, (iii) applying each of the matching parsing expressions to a corresponding one of the logical groupings to produce elements of data;

(iv) applying a general parser to any of the logical groupings that do not match any of the stored parsing expressions to produce elements of data, and (v) identifying a data type associated with each of the elements of data produced in (iii) and (iv); and

generate the inverted index using the extracted structure, wherein each item in the inverted index includes one of the elements of data produced in (iii) and (iv), a location identifier, a position identifier, and a data type identifier for one or more entries of the inverted index,

wherein the location identifier specifies an identifier of the file that contains the element of data, the position identifier specifies a position of the element of data within the file, and the data type identifier specifies the data type of the element of data, and the inverted index is utilized to respond to queries to identify patterns within the data; and

a memory coupled to the processor and configured to provide the processor with instructions.

17. The system recited in claim 16, wherein the processor is further configured to receive a search query and process the received search query.

18. The system recited in claim 17, wherein the processor is configured to process the received search query by translating the received search query to a different query form used to search the inverted index.

19. A computer program product for generating an inverted index, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions which, when executed on a processor, perform the steps of:

receiving a file comprising data, wherein at least a portion of the data is unstructured or semi-structured data;

parsing the data to extract structure from at least a portion of the data, wherein the parsing comprises (i) dividing the data into logical groupings, (ii) determining whether each of the logical groupings matches any of a plurality of stored parsing expressions, (iii) applying each of the matching parsing expressions to a corresponding one of the logical groupings to produce elements of data;

(iv) applying a general parser to any of the logical groupings that do not match any of the stored parsing expressions to produce elements of data, and (v) identifying a data type associated with each of the elements of data produced in (iii) and (iv);

generating the inverted index using the extracted structure, wherein each item in the inverted index includes one of the elements of data produced in (iii) and (iv), a location identifier, a position identifier, and a data type identifier for one or more entries of the inverted index,

wherein the location identifier specifies an identifier of the file that contains the element of data, the position identifier specifies a position of the element of data within the file, and the data type identifier specifies the data type of the element of data, and the inverted index is utilized to respond to queries to identify patterns within the data.

20. The computer program product recited in claim 19, further comprising computer instructions for:

receiving a search query and processing the received search query.