US 8,898,168 B2Granted

Information searching apparatus, information searching method, and computer product

AssigneeFujitsu Limited

InventorsYasuo Yamane, Nobuyuki Igata

Life of this patent

Estimating the term…

Loading patent…

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.

Claims2

Dependent claims

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 fpq between the merged cluster and each of clusters linked thereto based on the following equation:
f
pq
=
l
⁡
(
C
p
,
C
q
)
λ
n
⁡
(
C
p
)
v
×
n
⁡
(
C
q
)
v
×
d
⁡
(
C
p
)
δ
×
d
⁡
(
C
q
)
δ
where n(Cp) denotes the number of nodes in a first cluster Cp;
n(Cq) denotes the number of nodes in a second cluster Cq;
d(Cp) denotes the number of links originating from the first cluster Cp;
d(Cq) denotes the number of links originating from the second cluster Cq;
l(Cp, Cq) denotes the number of links linking together the first and second clusters Cp and Cq;
and ν, δ, and λ denote adjustment coefficients.

53 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/050,410Filed 10 Oct 2013 · continuation
Priority: JP 2008-10383511 Apr 2008
Published: US 2014/0040267 A16 Feb 2014
Granted: 25 Nov 2014
Term ends: Not estimatedThe source records don’t support an estimate.

Classification3 codes

G06F 16/285
Relational databases: clustering or classification
G06F 16/9024
Indexing; Data structures therefor; Storage structures: graphs; Linked lists
G06F
Computing and data processing

Family

Application12/407,973Parent of this continuation · filed 20 Mar 2009
US 2014/0040267 A1Pre-grant publication · published 6 Feb 2014
US 8,583,646 B2Parent of this continuation
US 2009/0259652 A1Published application
US 8,898,168 B2This patent

From the US filing history. Foreign family members aren’t listed.