System and method for automatically and iteratively mining related terms in a document through relations and patterns of occurrences

• US 6,505,197 B1
• Filed: 11/15/1999
• Issued: 01/07/2003
• Est. Priority Date: 11/15/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sundaresan, Neelakantan, Yi, Jeonghee
• Primary Examiner(s): CHANNAVAJJALA, SRIRAMA T
• Application Number:
  US09/439,379
• Time in Patent Office: 1,149 Days
• Field of Search: 707/1-8, 707/10, 707/100-104, 707/501.1, 707/512-513, 707/500.1, 707/531, 709/203-224, 704/1-4, 704/8-10, 706/45-50, 382/219-220
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A computer program product is provided as an automatic mining system to identify a set of related terms on the World Wide Web that define a relationship, using the duality concept. Specifically, the mining system iteratively refines pairs of terms that are related in a specific way, and the patterns of their occurrences in web pages. The automatic mining system runs in an iterative fashion for continuously and incrementally refining the relates and their corresponding patterns. In one embodiment, the automatic mining system identifies relations in terms of the patterns of their occurrences in the web pages. The automatic mining system includes a relation identifier that derives new relations, and a pattern identifier that derives new patterns. The newly derived relations and patterns are stored in a database, which begins initially with small seed sets of relations and patterns that are continuously and iteratively broadened by the automatic mining system.

Claims

1. A system for automatically and iteratively mining related terms in a document d_i through relations and patterns of occurrences, comprising:

a database for storing a set of previously identified relations R<sub>i−

1</sub> and a set of previously identified patterns P<sub>i−

1</sub>;

a relation identifier that uses the document d_i and the set of patterns P<sub>i−

1</sub> to derive a new relation r_i;

a pattern identifier that uses the document d_i and the set of relations R<sub>i−

1</sub> and the relation r_i for deriving a new pattern p_i that has not been predetermined; and

wherein the set of patterns P<sub>i−

1</sub> includes individual patterns p_n and is expressed as follows;

2. The system according to claim 1, wherein the database stores the relation r_i and pattern p_i.

3. The system according to claim 1, wherein the set of patterns P_i−

1 defines a format according to which the relation r₁ occurs in document d_i.

4. A computer program product for automatically and iteratively mining related terms in a document d_i through relationships and patterns of occurrences, comprising:

a database for storing a set of previously identified relations R<sub>i−

1</sub> and a set of previously identified patterns P<sub>i−

1</sub>;

a relation identifier that uses the document d_i and the set of patterns P<sub>i−

1</sub> to derive a new relation r_i;

a pattern identifier that uses the document d_i and the set of relations R<sub>i−

1</sub> and the relation r_i for deriving a new pattern p_i that has not been predetermined; and

wherein the set of patterns P<sub>i−

1</sub> includes individual patterns p_n and is expressed as follows;

5. The computer program product according to claim 4, wherein the database stores the sets of relations R_i and pattern P_i.

6. The computer program product according to claim 5, wherein the set of patterns P_i−

1 defines a format according to which the relation r₁ occurs in document d_i.

7. A method for automatically and iteratively mining related terms in a document d_i through relationships and patterns of occurrences, comprising:

storing previously identified sets of relations R<sub>i−

1</sub> and patterns P<sub>i−

1</sub>;

using the document d_i and the set of relations R<sub>i−

1</sub> to derive a relation r_i;

using the document d_i and the set of patterns R_i to derive new pattern p_i that has not been predetermined; and

wherein defining the pattern P<sub>i−

1</sub> includes expressing the pattern P<sub>i−

1</sub> by a set of individual patterns p_n as follows;

8. The method according to claim 7, further including storing the relation r_i and pattern p_i in a database.

9. The method according to claim 7, further including defining the pattern p_i by a format according to which the relation r_i occurs in the document d_i.