INFORMATION SEARCHING APPARATUS, INFORMATION SEARCHING METHOD, AND COMPUTER PRODUCT

• US 20090259652A1
• Filed: 03/20/2009
• Published: 10/15/2009
• Est. Priority Date: 04/11/2008
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Igata, Nobuyuki, Yamane, Yasuo
• Granted Patent: US 8,583,646 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

An information searching apparatus retrieves a sub graph matching an inquiry graph from a graph to be searched. The apparatus includes an extracting unit that extracts, from among clusters of nodes in the graph to be searched, plural cluster pairs that each include a first cluster and a second cluster including a node linked by a link to a node in the first cluster and a calculating unit that calculates a bonding strength for each of the cluster pairs. The apparatus further includes a determining unit that determines, among the cluster pairs and based on the bonding strength of each of the cluster pairs, a cluster pair to be merged; a merging unit that merges the cluster pair; and a searching unit that searches the merged clusters for a sub graph matching the inquiry graph. An output unit outputs a search result of the searching unit.

Claims

1. A computer-readable recording medium storing therein an information searching program of a computer that retrieves a sub graph matching an inquiry graph from a graph to be searched including nodes and a link interlinking the nodes, the information searching program causing the computer to execute:

extracting, from among clusters of nodes in the graph to be searched, a plurality of cluster pairs, each of the cluster pairs consisting of a first cluster and a second cluster including a node linked by a link to a node in the first cluster, wherein the clusters include nodes that differ;

calculating a bonding strength for each of the cluster pairs extracted at the extracting;

determining, among the cluster pairs and based on the bonding strength of each of the cluster pairs, a cluster pair to be merged;

merging the cluster pair determined at the determining;

searching merged clusters formed at the merging, for a sub graph matching the inquiry graph; and

outputting a search result of the searching.

2. The computer-readable recording medium according to claim 1, wherein

the calculating includes calculating the bonding strength so that the bonding strength increases as nodes in the first cluster and the second cluster of the cluster pair decrease.

3. The computer-readable recording medium according to claim 1, wherein

the calculating includes calculating the bonding strength so that the bonding strength increases as links linking nodes in the cluster pair to nodes in another cluster decrease.

4. The computer-readable recording medium according to claim 1, wherein

the calculating includes calculating the bonding strength so that the bonding strength increases as links linking nodes the first cluster and the second cluster increase in number.

5. The computer-readable recording medium according to claim 1, wherein

the determining includes determining a cluster pair, whose bonding strength is strongest among the cluster pairs, to be the cluster pair to be merged.

6. The computer-readable recording medium according to claim 1, the information searching program further causing the computer to execute:

judging whether a quantity of the merged clusters formed at the merging has reached a given number, wherein

the extracting further includes extracting the cluster pairs from among the merged clusters when at the judging, the quantity of the merged clusters is judged to be below the given number.

7. The computer-readable recording medium according to claim 1, the information searching program further causing the computer to execute:

narrowing down the merged clusters, based on a condition of the inquiry graph, wherein

the searching includes searching the merged clusters narrowed down at the narrowing down, for the sub graph matching the inquiry graph.

8. An information searching apparatus that retrieves a sub graph matching an inquiry graph from a graph to be searched including nodes and a link interlinking the nodes, the information searching apparatus comprising:

an extracting unit that extracts, from among clusters of nodes in the graph to be searched, a plurality of cluster pairs, each of the cluster pairs consisting of a first cluster and a second cluster including a node linked by a link to a node in the first cluster, wherein the clusters include nodes that differ;

a calculating unit that calculates a bonding strength for each of the cluster pairs extracted by the extracting unit;

a determining unit that determines, among the cluster pairs and based on the bonding strength of each of the cluster pairs, a cluster pair to be merged;

a merging unit that merges the cluster pair determined by the determining unit;

a searching unit that searches merged clusters formed by the merging unit, for a sub graph matching the inquiry graph; and

an output unit that outputs a search result of the searching unit.

9. An information searching method of retrieving a sub graph matching an inquiry graph from a graph to be searched including nodes and a link interlinking the nodes, the information searching method comprising:

extracting, from among clusters of nodes in the graph to be searched, a plurality of cluster pairs, each of the cluster pairs consisting of a first cluster and a second cluster including a node linked by a link to a node in the first cluster, wherein the clusters include nodes that differ;

calculating a bonding strength for each of the cluster pairs extracted at the extracting;

determining, among the cluster pairs and based on the bonding strength of each of the cluster pairs, a cluster pair to be merged;

merging the cluster pair determined at the determining;

searching merged clusters formed at the merging, for a sub graph matching the inquiry graph; and

outputting a search result of the searching.