Classification of information sources using graphic structures

• US 6,772,148 B2
• Filed: 02/12/2003
• Issued: 08/03/2004
• Est. Priority Date: 10/04/1999
• Status: Expired due to Term

• Current Assignee: Jarg Corporation
• Original Assignee: Jarg Corporation
• Inventors: Baclawski, Kenneth P.
• Primary Examiner(s): KINDRED, ALFORD W
• Application Number:
  US10/365,276
• Publication Number:
  US 20030120681A1
• Time in Patent Office: 538 Days
• Field of Search: 707/5, 707/10, 707/100-102, 707/200, 707/205, 345/587, 345/530, 345/440.2, 345/853-854, 706/45, 706/47
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3332 Query translation
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

In a knowledge classification system, both the information sources and queries are processed to generate knowledge representation graph structures. The graph structures for both the query and the information sources are then converted to views and displayed to a searcher. By manipulating the graph structure views for each information source, the searcher can examine the source for relevance. A search can be performed by comparing the graph structure of the query to the graph structure of each information source by a graph matching computer algorithm. Information sources are classified by constructing hierarchies of knowledge representations. The simplest construction is obtained by using the knowledge representation of a query as the top of the hierarchy. The structures in the hierarchy are substructures of the query. The hierarchy of structures may also be constructed by using the knowledge representation of the query as the bottom of the hierarchy. Structures in the hierarchy, in this case, are structures that contain the query. The vertices of a graph structure view can be displayed on a computer screen next to the corresponding items, such as words, phrases and visual features, of an information source view. Selecting a vertex in the graph structure causes the selected vertex and vertices adjacent to the selected vertex to be “highlighted.” By selecting a succession of vertices in the graph structure, a searcher can perform knowledge navigation of the information source. By successively selecting items of the information source, a searcher can perform knowledge exploration of the information source.

Claims

1. A method for navigating and exploring an information source located by matching a query knowledge representation to knowledge representations in the information source, the method comprising:

(a) visually displaying the query knowledge representation as a graph structure having features comprising vertices connected by edges;

(b) visually displaying the content of the information source in the vicinity of the graph structure; and

(c) automatically highlighting items in the information source content that correspond to the vertices and edges of the graph structure.

2. The method according to claim 1 further comprising:

(d) highlighting a feature in the graph structure in response to a user selection; and

(e) in response to the highlighting of a feature in the graph structure, highlighting an item in the information source content, which item corresponds to the selected feature.

3. The method according to claim 2 further comprising:

(f) in response to the highlighting of a feature in the graph structure, highlighting related features in the graph structure which are adjacent to the selected feature; and

(g) in response to the highlighting of a feature in the graph structure, highlighting related items in the information source content, which related items correspond to the related features.

4. The method according to claim 1 further comprising:

(h) highlighting an item in the information source content in response to a user selection; and

(i) in response to the highlighting of an item in the information source content, highlighting a feature in the graph structure, which feature corresponds to the selected item.

5. The method according to claim 4 further comprising:

(j) in response to the highlighting of an item in the information source content, highlighting related items in the information source content which are adjacent to the selected item; and

(k) in response to the highlighting of an item in the information source content, highlighting related features in the graph structure, which related features correspond to the related items.

6. Apparatus for navigating and exploring an information source located by matching a query knowledge representation to knowledge representations in the information source, the apparatus comprising:

a visual display having an area for displaying the query knowledge representation as a graph structure having features comprising vertices connected by edges and an area for displaying the content of the information source in the vicinity of the graph structure; and

a mechanism that is responsive to the display of the query knowledge representation for highlighting items in the information source content that correspond to the vertices and edges of the graph structure.

7. The apparatus according to claim 6 further comprising:

a mechanism that highlights a feature in the graph structure in response to a user selection with the user selection device; and

a mechanism that is responsive to a user selection of a feature in the graph structure for highlighting an item in the information source content, which item corresponds to the selected feature.

8. The apparatus according to claim 7 further comprising:

a mechanism that is responsive to a user selection of a feature in the graph structure for highlighting related features in the graph structure which are adjacent to the selected feature; and

a mechanism that is responsive to a user selection of a feature in the graph structure for highlighting related items in the information source content, which related items correspond to the related features.

9. The apparatus according to claim 6 further comprising:

a mechanism that highlights an item in the information source content in response to a user selection with the user selection device; and

a mechanism that is responsive to a user selection of an item in the information source content for highlighting a feature in the graph structure, which feature corresponds to the selected item.

10. The apparatus according to claim 9 further comprising:

a mechanism that is responsive to a user selection of a feature in the graph structure for highlighting related items in the information source content which are adjacent to the selected item; and

a mechanism that is responsive to a user selection of a feature in the graph structure for highlighting related features in the graph structure, which related features correspond to the related items.

11. A computer program product for navigating and exploring an information source located by matching a query knowledge representation to knowledge representations in the information source, the computer program product comprising a computer usable medium having computer readable program code thereon, including:

program code for visually displaying the query knowledge representation as a graph structure having features comprising vertices connected by edges;

program code for visually displaying the content of the information source in the vicinity of the graph structure; and

program code for automatically highlighting items in the information source content that correspond to the vertices and edges of the graph structure.

12. A computer data signal embodied in a carrier wave for navigating and exploring an information source located by matching a query knowledge representation to knowledge representations in the information source, the computer data signal comprising:

program code for visually displaying the query knowledge representation as a graph structure having features comprising vertices connected by edges;

program code for visually displaying the content of the information source in the vicinity of the graph structure; and

program code for automatically highlighting items in the information source content that correspond to the vertices and edges of the graph structure.