Information extraction from a database

• US 8,332,371 B1
• Filed: 09/23/2011
• Issued: 12/11/2012
• Est. Priority Date: 03/10/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Brin, Sergey
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US13/243,133
• Time in Patent Office: 445 Days
• Field of Search: 707/696, 707/644, 707/641, 707/648, 707/640
• US Class Current: 707/696
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Techniques for extracting information from a database are provided. A database such as the Web is searched for occurrences of tuples of information. The occurrences of the tuples of information that were found in the database are analyzed to identify a pattern in which the tuples of information were stored. Additional tuples of information can then be extracted from the database utilizing the pattern. This process can be repeated with the additional tuples of information, if desired.

Claims

1. A method performed by one or more server devices, the method comprising:

searching, by the one or more server devices, a plurality of documents to identify a plurality of occurrences of a first tuple in text of the plurality of documents and a respective context for each occurrence of the first tuple in the text of the plurality of documents;

analyzing, by the one or more server devices, the identified plurality of occurrences and the respective context for each occurrence to identify a data pattern that corresponds to the first tuple;

extracting, by the one or more server devices, a second tuple from the text of the plurality of documents, using the data pattern, where the second tuple is different from the first tuple; and

storing, by the one or more server devices, the first tuple and the second tuple in a data storage.

7. The method of claim 1, where the first tuple includes a plurality of fields that each represent a character string, and

where searching the plurality of documents to identify the plurality of occurrences of the first tuple in the text of the plurality of documents includes identifying occurrences of text in the plurality of documents that match the character strings of the first tuple.

8. The method of claim 1, where the data pattern includes an order and a plurality of character strings, the method further comprising:

determining a specificity of the data pattern with respect to a product of lengths of the plurality of character strings.

9. The method of claim 1, further comprising:

determining a specificity of the data pattern, based on a quantity of occurrences of the first tuple in the text of the plurality of documents, with respect to a threshold.

10. The method of claim 1, further comprising:

determining that a specificity of the data pattern exceeds a threshold, and

where extracting the second tuple is performed after determining that the specificity of the data pattern exceeds the threshold.

23. The method of claim 9, where extracting the second tuple is performed when the determined specificity of the data pattern exceeds the threshold.

2. A computer-readable memory device comprising:

one or more instructions that, when executed by one or more processors, cause the one or more processors to;

search a plurality of documents to identify a plurality of occurrences of a first tuple in text of the plurality of documents and a respective context for each occurrence of the first tuple in the text of the plurality of documents;

analyze the identified plurality of occurrences and the respective context for each occurrence to identify a data pattern that corresponds to the first tuple;

extract a second tuple from the text of the plurality of documents, using the data pattern, where the second tuple is different from the first tuple; and

store the first tuple and the second tuple in a data storage.

11. The computer-readable memory device of claim 2, where the first tuple includes a plurality of fields that each represent a character string, and

where the one or more instructions to search the plurality of documents to identify the plurality of occurrences of the first tuple in the text of the plurality of documents include one or more instructions to identify occurrences of text in the documents that match the character strings of the first tuple.

12. The computer-readable memory device of claim 2, further comprising:

one or more instructions to determine that a specificity of the data pattern exceeds a threshold, and

where the one or more instructions to extract the second tuple include one or more instructions to extract the second tuple after determining that the specificity of the data pattern exceeds the threshold.

3. A system, comprising:

one or more memory devices to store computer-executable instructions; and

one or more processors to execute the computer-executable instructions, to;

search a plurality of documents to identify a plurality of occurrences of a first tuple in text of the plurality of documents and a respective context for each occurrence of the first tuple in the text of the plurality of documents;

analyze the identified plurality of occurrences and the respective context for each occurrence to identify a data pattern that corresponds to the first tuple;

extract a second tuple from the text of the plurality of documents, using the data pattern, where the second tuple is different from the first tuple; and

store the first tuple and the second tuple in a data storage.

13. The system of claim 3, where the first tuple includes a plurality of fields that each represent a character string, and

where when searching the plurality of documents to identify the plurality of occurrences of the first tuple in the text of the plurality of documents, the one or more processors are to identify occurrences of text in the documents that match the character strings of the first tuple.

14. The system of claim 3, where the one or more processors are further to:

determine that a specificity of the data pattern exceeds a threshold, and

where when extracting the second tuple, the one or more processors are to extract the second tuple after determining that the specificity of the data pattern exceeds the threshold.

4. A method performed by one or more server devices, the method comprising:

searching a plurality of documents to identify a plurality of occurrences of a first tuple;

identifying, using the identified plurality of occurrences, a pattern that corresponds to the first tuple;

searching the plurality of documents to identify an occurrence of a second tuple that matches the identified pattern and that is different from the first tuple; and

storing the first and second tuples in a data storage.

15. The method of claim 4, where the first tuple includes a plurality of fields that each represent a character string, and

where searching the plurality of documents to identify the plurality of occurrences of the first tuple includes identifying occurrences of text in the plurality of documents that match the character strings of the first tuple.

16. The method of claim 4, where the pattern includes an order and a plurality of character strings, the method further comprising:

determining a specificity of the pattern with respect to a product of lengths of the character strings.

17. The method of claim 4, further comprising:

determining a specificity of the pattern, based on a quantity of occurrences of the first tuple in the text of the plurality of documents, with respect to a threshold.

18. The method of claim 4, further comprising:

determining that a specificity of the pattern exceeds a threshold, and

where searching the plurality of documents to identify the occurrence of the second tuple is performed after determining that the specificity of the pattern exceeds the threshold.

24. The method of claim 17, where searching the plurality of documents to identify the occurrence of the second tuple is performed when the determined specificity of the pattern exceeds the threshold.

5. A computer-readable memory device comprising:

one or more instructions that, when executed by one or more processors, cause the one or more processors to ;

search a plurality of documents to identify a plurality of occurrences of a first tuple;

identify, using the identified plurality of occurrences, a pattern that corresponds to the first tuple;

identify an occurrence of a second tuple in the plurality of documents that matches the identified pattern and that is different from the first tuple; and

store the first and second tuples in a data storage.

19. The computer-readable memory device of claim 5, where the first tuple includes a plurality of fields that each represent a character string, and

where the one or more instructions to search the plurality of documents to identify the plurality of occurrences of the first tuple in the text of the plurality of documents include one or more instructions to identify occurrences of text in the documents that match the character strings of the first tuple.

20. The computer-readable memory device of claim 5, further comprising:

one or more instructions to determine that a specificity of the pattern exceeds a threshold, and

where the one or more instructions to identify the occurrence of the second tuple include one or more instructions to extract the second tuple after determining that the specificity of the pattern exceeds the threshold.

6. A system, comprising:

one or more memory devices to store computer-executable instructions; and

one or more processors to execute the computer-executable instructions, to;

search a plurality of documents to identify a plurality of occurrences of a first tuple;

identify, using the identified plurality of occurrences, a pattern that corresponds to the first tuple;

identify an occurrence of a second tuple in the plurality of documents that matches the identified pattern and that is different from the first tuple; and

store the first and second tuples in a data storage.

21. The system of claim 6, where the first tuple includes a plurality of fields that each represent a character string, and

where when searching the plurality of documents to identify the plurality of occurrences of the first tuple in the text of the plurality of documents, the one or more processors are to identify occurrences of text in the documents that match the character strings of the first tuple.

22. The system of claim 6, where the one or more processors are further to:

determine that a specificity of the pattern exceeds a threshold, and

where when identify the occurrence of the second tuple, the one or more processors are to extract the second tuple after determining that the specificity of the pattern exceeds the threshold.