COLLECTING, ORGANIZING, AND SEARCHING KNOWLEDGE ABOUT A DATASET

• US 20160132572A1
• Filed: 11/11/2014
• Published: 05/12/2016
• Est. Priority Date: 11/11/2014
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Digiuseppe, Nicholas, Chang, Walter
• Granted Patent: US 11,080,295 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/116 Details of conversion of file system types or formats
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/90332 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Techniques for organizing knowledge about a dataset storing data from or about multiple sources may be provided. For example, the data can be accessed from the multiple sources and categorized based on the data type. For each data type, a triple extraction technique specific to that data type may be invoked. One set of techniques can allow the extraction of triples from the data based on natural language-based rules. Another set of techniques can allow a similar extraction based on logical or structural-based rules. A triple may store a relationship between elements of the data. The extracted triples can be stored with corresponding identifiers in a list. Further, dictionaries storing associations between elements of the data and the triples can be updated. The list and the dictionaries can be used to return triples in response to a query that specifies one or more elements.

Claims

1. A computer-implemented method for creating a dataset to facilitate natural language searching of data from a plurality of different source files, the computer-implemented method comprising:

identifying, by a processor, different triple extraction techniques corresponding to source files of different types;

extracting, by the processor, triples from each of the source files using a triple extraction technique corresponding to a type of the respective source file, each of the triples extracted by identifying, from the respective source file, a first natural language phrase as a subject, a second natural language phrase as an object, and an association between the first natural language phrase and the second natural language phrase as a predicate; and

storing, by the processor, the triples in the dataset.

2. The computer-implemented method of claim 1 further comprising:

using a first technique to identify associations between natural language phrases for source files storing data in a structured format; and

using a second technique, different from the first technique, to identify associations between natural language phrases for source files storing data in an unstructured format.

3. The computer-implemented method of claim 1, wherein extracting the triple from the respective source file comprises:

detecting that the source file stores data in one or more of;

a structured data format, a semi-structured data format, or an unstructured data format;

if the data is stored in the structured data format or the semi-structured data format, identifying a structure storing natural language phrases and determining a first association to be stored as the predicate of the triple based on the structure; and

if the data is stored in the unstructured data format, identifying one or more words from the natural language phrases and determining a second association to be stored as the predicate of the triple by applying a set of rules specifying relationships between the natural language phrases based on word type.

4. The computer-implemented method of claim 1, further comprising:

parsing a user query to identify a natural language phrase of the query;

identifying a first triple of the dataset by matching the natural language phrase of the query with the identified first triple'"'"'s subject or object; and

returning a query result comprising data from the source files based on the identified first triple.

5. The computer-implemented method of claim 1, further comprising:

parsing a user query to identify a natural language phrase of the query;

identifying a first triple of the dataset by matching the natural language phrase of the query with the identified first triple'"'"'s subject or object;

identifying a second triple of the dataset based on the identified first triple'"'"'s subject or object matching the identified second triple'"'"'s subject or object; and

returning a query result comprising data from the source files based on the identified first triple and the identified second triple.

6. The computer-implemented method of claim 1, wherein a type of a source file indicates that the source file comprises unstructured data, and wherein a triple extraction technique specific to the unstructured data comprises:

generating a string, identifying words and word types from the string, generating natural language phrases from the words, applying a set of rules specifying relationships between the natural language phrases based on the word types, and generating triples based on the applied rules.

7. The computer-implemented method of claim 1, wherein a source file comprises a text string, wherein extracting the triples comprises:

identifying words and corresponding word types from the text string;

generating natural language phrases based on proximities between the words; and

applying one or more rules to the first natural language phrase and the second natural language phrase to generate a triple, the one or more rules associated with one or more patterns and being applied based on matching the one or more patterns to the word types, the one or more rules specifying relationships between two or more natural language phrases.

8. The computer-implemented method of claim 1, further comprising updating an entity dictionary based on the first natural language phrase, wherein the entity dictionary associates subjects and objects with natural language phrases in which each respective subject and object participates, wherein the updating comprises:

identifying a word from the subject of the triple;

updating a key from a key-value pair of the entity dictionary with the word; and

updating a value of the key-value pair with the first natural language phrase.

9. The computer-implemented method of claim 1, further comprising updating a mention dictionary based on the first natural language phrase, wherein the mention dictionary associates natural language phrases with triples in which each natural language phrase participates, wherein the updating comprises:

updating a key from a key-value pair of the mention dictionary with the first natural language phrase; and

updating a value of the key-value pair with an identifier of a corresponding triple.

10. The computer-implemented method of claim 1, wherein a source file comprises text defined in a hierarchical structure, wherein extracting the triples comprises:

extracting words from the text;

identifying types of the words, the types comprising a noun, a verb, an adjective, an adverb, and a preposition;

generating a first triple based on the words and the types;

generating a second triple based on the hierarchical structure, wherein a subject and an object of the second triple correspond to edges of the hierarchical structure, and wherein a predicate of the second triple corresponds to a relationship between the two edges.

11. A system comprising:

a processor;

a memory communicatively coupled to the processor and bearing instructions that, upon execution by the processor, cause the system to at least perform operations comprising;

accessing words from a source file, the words to be organized based on associations between the words;

extracting a triple from a subset of the words based on a set of rules, the triple comprising a subject, a predicate, and an object corresponding to the subset of the words, the set of rules applicable to the subset of the words based on a pattern of word types;

generating a structure configured to store an association between an entity and a phrase associated with the subject or the object, the entity comprising one or more words from the subject or the object, the phrase comprising the subject or the object; and

generating another structure configured to store another association between the phrase and the triple.

12. The system of claim 11, wherein accessing words from the source file comprises:

receiving the source file, the source file comprising one or more of;

an image, a video, an audio, or a text; and

generating the words from content of the source file.

13. The system of claim 11, wherein the source file comprises natural language utterances.

14. The system of claim 11, wherein extracting the triple comprises:

annotating each word with a corresponding word type;

identifying phrase expressions formed by proximate words; and

applying the set of rules to the words and the phrase expressions based on the pattern of the word types.

15. The system of claim 11, wherein extracting triples from the subset of the words comprises:

detecting the pattern of the word types based on annotations of the subset of the words, the annotations comprising the word types;

matching the pattern to one or more rules from the set of rules, the one or more rules specifying an association between two or more words based on the pattern; and

applying the one or more rules to the subset of the words to generate the triple based on the specified association.

16. The system of claim 11, wherein accessing the words from the source file comprises identifying a string of the words and a structure associated with the source file, and wherein extracting the triple comprises:

extracting a first triple from the string of the words based on a first subset of the rules applicable to the string of words, and

extracting a second triple from the structure based on a second subset of the rules applicable to structure.

17. A computer-readable storage medium storing instructions that, when executed on a computing device, configure the computing device to perform operations comprising:

detecting words and corresponding word types from a source;

generating a triple based on applying a set of rules to the words, the set of rules applied based on a pattern of the word types and providing an association between at least two words, the triple comprising the at least two words;

generating a first structure configured to store a first association between a word from the triple and a phrase, the phrase formed based on a proximity of the word with another word; and

generating a second structure configured to store a second association between the phrase and the triple.

18. The computer-readable storage medium of claim 17, wherein the first structure is further configured to store first associations between words from triples and phrases, wherein the second structure is further configured to store second associations between the phrases and the triples, wherein the triples, the first structure, and the second structure are stored in a dataset, wherein the dataset is configured to facilitate querying the triples, wherein querying the triples comprises:

receiving a query comprising a keyword;

identifying a subset of the phrases based on matching the keyword to the words from the first structure;

identifying a subset of the triples from the second structure based on the second associations between the subset of phrases and the subset of triples;

replacing the keyword with one or more of a synonym, a hypernym, or a thesaurus equivalent word;

identifying additional subsets of the phrases from the first structure and additional subsets of the triples from the second structure based on the replacing; and

scoring the subset of the triples and the additional subsets of the triples based on whether the keyword was used or whether the keyword was replaced to identify the triples.

19. The computer-readable storage medium of claim 17, wherein the first structure is further configured to store first associations between words from triples and phrases, wherein the second structure is further configured to store second associations between the phrases and the triples, wherein the triples, the first structure, and the second structure are stored in a dataset, wherein the dataset is configured to facilitate querying the triples, wherein querying the triples comprises:

receiving a query comprising a plurality of keywords;

identifying, for each keyword, a subset of the phrases and a subset of the triples based on the first structure and the second structure;

determining, for each triple from the identified subsets of the triples, a frequency of identifying the triple based the plurality of keywords; and

scoring the identified triples based on corresponding frequencies.

20. The computer-readable storage medium of claim 17, wherein the triple comprises a subject, a predicate, and an object, wherein the triple, the first structure, and the second structure are stored in a dataset, wherein the dataset is configured to facilitate querying triples, wherein querying the triples comprises:

receiving a query comprising a keyword;

identifying the phrase and the triple from the first structure and the second structure based on matching the keyword; and

identifying another triple from the triples based on matching the subject of the triple with another object of the other triple or based on matching the object of the triple with another subject of the other triple.