Information extraction from a database

• US 7,650,330 B1
• Filed: 12/15/2003
• Issued: 01/19/2010
• Est. Priority Date: 03/10/1999
• Status: Active Grant

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Brin, Sergey
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US10/734,111
• Time in Patent Office: 2,227 Days
• Field of Search: 707 3- 7
• US Class Current: 1/1
• 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 computer-implemented method comprising:

receiving, from a user, a first example of target information, where the first example includes a first tuple that corresponds to the target information in documents stored in a database, the first tuple including a plurality of fields;

finding ones of the documents in the database that contain the first tuple;

analyzing the ones of the documents in the database to recognize a pattern, in the ones of the documents, that includes the first tuple and at least one of text that precedes the plurality of fields of the first tuple, text that occurs between at least two of the plurality of fields of the first tuple, or text that follows the plurality of fields of the first tuple; and

automatically searching the database for at least a second tuple that matches the pattern, where the at least a second tuple is a second example of the target information and differs from the first tuple and the pattern.

2. The method of claim 1, where the pattern is defined as text that matches a regular expression.

3. The method of claim 2, where the text includes hyper-text markup language (HTML).

4. The method of claim 1, where the pattern includes the text that occurs between two of the fields of the first tuple.

5. The method of claim 4, where the pattern includes the text that precedes the plurality of fields in the first tuple and the text that follows the plurality of fields in the first tuple.

6. The method of claim 1, further comprising:

recognizing a plurality of different patterns based on the at least a second tuple.

7. The method of claim 1, where the pattern matches the fields of the first tuple.

8. The method of claim 1, where the pattern is defined by a regular expression, context free grammar, or computable function.

9. The method of claim 1, where the database includes documents retrievable via the World Wide Web.

10. A computer-readable storage device including instructions for execution by a processor, the instructions comprising:

instructions to receive, from a user, a first example of target information, where the target information includes a tuple that corresponds to the target information in documents stored in a database, the tuple including a plurality of fields;

instructions to find ones of the documents in the database that contain the tuple;

instructions to analyze the ones of the documents to recognize a pattern, in the ones of the documents, that includes the tuple and at least one of text that precedes the plurality of fields of the tuple, text that occurs between two fields of the tuple, or text that follows the plurality of fields of the tuple; and

instructions to automatically search the database for one or more other tuples that match the pattern, where the one or more other tuples are other examples of the target information and differ from each other, the tuple, and the pattern.

11. The computer-readable storage device of claim 10, further comprising:

instructions to match the plurality of fields of the identified tuple to the determined pattern.

12. The computer-readable storage device of claim 10, where the recognized pattern is defined as text that matches a regular expression.

13. The computer-readable storage device of claim 10, further comprising:

instructions to recognize a plurality of different patterns based on the other examples of the target information.

14. A computing device comprising:

a memory to store instructions; and

a processor to execute the instructions to;

receive, from a user, a set of examples of a first type of information, where the set of the examples includes one or more tuples that correspond to the first type of information in documents stored in a database, each of the one or more tuples including a plurality of fields;

find the documents in the database that contain the one or more tuples;

analyze the documents to identify a plurality of patterns of at least one of text that precedes the plurality of fields of the one or more tuples, text that occurs between two fields of the one or more tuples, or text that follows the plurality of fields of the one or more tuples; and

automatically search the database for at least one other tuple that matches one of the patterns, where the at least one other tuple is another example of the first type of information and the at least one other tuple differs from the set of examples and the patterns.

15. The computing device of claim 14, where at least one pattern of the plurality of patterns includes the text that occurs between two fields of the one or more tuples.

16. The computing device of claim 14, where at least one pattern of the plurality of patterns includes the text precedes the plurality of fields of the one or more tuples and the text that follows the plurality of fields of the one or more tuples.

17. A computer-implemented method comprising:

receiving, from a user, a first example of target information, where the first example includes a first tuple that corresponds to the target information in documents stored in a database, the first tuple including a plurality of fields;

finding ones of the documents in the database that contain the first tuple;

extracting occurrences of the first tuple from the ones of the documents, each occurrence including the first tuple and at least one of text preceding the plurality of fields of the first tuple, text occurring between two of the plurality of fields of the first tuple, or text following the plurality of fields of the first tuple;

analyzing the extracted occurrences to recognize a pattern, in the ones of the documents, of the first tuple and the at least one of the text preceding the plurality of fields of the first tuple, the text occurring between two fields of the first tuple, or the text following the plurality of fields of the first tuple; and

automatically searching the database for at least a second tuple that matches the pattern, where the at least a second tuple is a second example of the target information and differs from the first tuple and the pattern.

18. The method of claim 17, where each occurrence includes the first tuple, the text preceding the plurality of fields of the first tuple, the text occurring between two fields of the first tuple, and the text following the plurality of fields of the first tuple.

19. The method of claim 17, further comprising:

recognizing a plurality of different patterns based on the at least a second tuple.