INFORMATION SEARCHING APPARATUS, INFORMATION SEARCHING METHOD, AND COMPUTER PRODUCT

• US 20140040267A1
• Filed: 10/10/2013
• Published: 02/06/2014
• Est. Priority Date: 04/11/2008
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Yamane, Yasuo, Igata, Nobuyuki
• Granted Patent: US 8,898,168 B2
• Time in Patent Office: Days
• 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-9. -9. (canceled)

10. A non-transitory, computer-readable recording medium that stores therein a 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 the maximum bonding strength among all cluster pairs into a merged cluster;

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

extracting a cluster pair from among clusters after merge when a quantity of the clusters after merge is larger than a given number, wherein

the calculating includes calculating the bonding strength f_pq between the merged cluster and each of clusters linked thereto based on the following equation;

11. A clustering method 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 the maximum bonding strength among all cluster pairs into a merged cluster;

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

extracting a cluster pair from among clusters after merge when a quantity of the clusters after merge is larger than a given number, wherein

the calculating includes calculating the bonding strength f_pq between the merged cluster and each of clusters linked thereto based on the following equation;