Information searching apparatus, information searching method, and computer product

• US 8,583,646 B2
• Filed: 03/20/2009
• Issued: 11/12/2013
• Est. Priority Date: 04/11/2008
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Yamane, Yasuo, Igata, Nobuyuki
• Primary Examiner(s): DWIVEDI, MAHESH H
• Application Number:
  US12/407,973
• Publication Number:
  US 20090259652A1
• Time in Patent Office: 1,698 Days
• Field of Search: 707/705, 707/736, 707/737
• US Class Current: 707/737
• 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 non-transitory 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;

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

searching merged clusters narrowed at the narrowing, for a sub graph matching the inquiry graph; and

outputting a search result of the searching, the calculating includes calculating the bonding strength f_pq based on an equation of;

2. 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.

3. 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.

4. 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 narrowing unit that narrows the merged clusters, based on a condition of the inquiry graph;

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

an output unit that outputs a search result of the searching unit, the calculating unit calculates the bonding strength f_pq based on an equation of;

5. 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;

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

searching merged clusters narrowed at the narrowing, for a sub graph matching the inquiry graph; and

outputting a search result of the searching, the calculating includes calculating the bonding strength f_pq based on an equation of;

6. A non-transitory, computer-readable recording medium that stores therein a hierarchical clustering program that causes a computer to execute:

setting a plurality of clusters that include a plurality of nodes of a graph, respectively;

merging a cluster pair having a maximum bonding strength among all cluster pairs into a merged cluster; and

calculating the bonding strength between the merged cluster and each of other clusters, wherein

the calculating includes calculating the bonding strength f_pq based on an equation of;

7. A hierarchical clustering apparatus comprising:

a setting unit that sets a plurality of clusters that include a plurality of nodes of a graph, respectively;

a merging unit that merges a cluster pair having a maximum bonding strength among all cluster pairs into a merged cluster; and

a calculating unit that calculates the bonding strength between the merged cluster and each of other clusters, wherein

the calculating unit calculates the bonding strength f_pq based on an equation of;

8. A hierarchical clustering method comprising:

setting, by a processor, a plurality of clusters that include a plurality of nodes of a graph, respectively;

merging, by the processor, a cluster pair having a maximum bonding strength among all cluster pairs into a merged cluster; and

calculating, by the processor, the bonding strength between the merged cluster and each of the other clusters, wherein

the calculating includes calculating the bonding strength f_pq based on an equation of;