US 7,689,585 B2Granted

Reinforced clustering of multi-type data objects for search term suggestion

AssigneeMicrosoft Corporation

InventorsHua-Jun Zeng, Benyu Zhang, Zheng Chen, Wei-Ying Ma, Li Li, Ying Li, Tarek Najm

Life of this patent

Estimating the term…

Abstract

Systems and methods for related term suggestion are described. In one aspect, relationships among respective ones of two or more multi-type data objects are identified. The respective ones of the multi-type data objects include at least one object of a first type and at least one object of a second type that is different from the first type. The multi-type data objects are iteratively clustered in view of respective ones of the relationships to generate reinforced clusters.

Claims22

Dependent claims

A computer-implemented method performed by a computing device that has one or more processors to execute instructions, the method comprising:

identifying relationships between multi-type data objects that include at least one object of a first type and at least one object of a second type different from the first type, the relationships being at least one of intra-layer relationships or inter-layer relationships among the multi-type data objects;
iteratively clustering the multi-type data objects based on the relationships to generate reinforced clusters;
generating a list of suggested search terms associated with a bid term using the reinforced clusters, the search terms generated in response to receiving the bid term from a user;
transmitting, via a network interface, the list of suggested search terms to a user;
and
mutually reinforcing an importance of individual ones of the multi-type data objects within an object type and between different object types based on the following:
{
a
⁡
(
X
)
=
β
⁢
⁢
L
X
T
⁢
h
⁡
(
X
)
+
(
1
-
β
)
⁢
L
XY
⁢
i
⁡
(
Y
)
h
⁡
(
X
)
=
β
⁢
⁢
L
X
⁢
a
⁡
(
X
)
+
(
1
-
β
)
⁢
L
XY
⁢
i
⁡
(
Y
)
i
⁡
(
X
)
=
a
⁡
(
X
)
+
h
⁡
(
X
)
a
⁡
(
Y
)
=
γ
⁢
⁢
L
Y
T
⁢
h
⁡
(
Y
)
+
(
1
-
γ
)
⁢
L
YX
⁢
i
⁡
(
X
)
h
⁡
(
Y
)
=
γ
⁢
⁢
L
Y
⁢
a
⁡
(
Y
)
+
(
1
-
γ
)
⁢
L
YX
⁢
i
⁡
(
X
)
i
⁡
(
Y
)
=
a
⁡
(
Y
)
+
h
⁡
(
Y
)
wherein X={x1, x2, . . . xm} and Y={y1, y2, . . . yn} represent respective object sets of heterogeneous object type with relationships RX, RY, RXY and RYX if directionality is considered LX and LY represent adjacent matrixes of links identifying relationships within set X and Y respectively, LXY and LYX represent adjacent matrixes of links identifying relationships from objects in X to objects in Y, a(X) and h(X) are an authority score and a hub score of nodes within X respectively, a(Y) and h(Y) respectively represent authority scores and hub scores of nodes in Y, i(X) and i(Y) respectively represent an importance of the nodes in X and Y, and β and γ are weight parameters to adjust influence of links derived from different relationships.

169 more elements

A computer-readable storage medium comprising computer-executable instructions executable by a processor for:

identifying at least one of intra-layer and inter-layer relationships among multi-type data objects, wherein the multi-type data objects comprise at least one object of a first type and at least one object of a second type different from the first type;
iteratively clustering the multi-type data objects by at least one of the relationships to generate reinforced clusters;
generating a list of suggested search terms associated with a bid term using the reinforced clusters, the suggested search terms generated in response to receiving the bid term from a user;
and
mutually reinforcing an importance of individual ones of the multi-type data objects within an object type and between different object types based on the following:
{
a
⁡
(
X
)
=
β
⁢
⁢
L
X
T
⁢
h
⁡
(
X
)
+
(
1
-
β
)
⁢
L
XY
⁢
i
⁡
(
Y
)
h
⁡
(
X
)
=
β
⁢
⁢
L
X
⁢
a
⁡
(
X
)
+
(
1
-
β
)
⁢
L
XY
⁢
i
⁡
(
Y
)
i
⁡
(
X
)
=
a
⁡
(
X
)
+
h
⁡
(
X
)
a
⁡
(
Y
)
=
γ
⁢
⁢
L
Y
T
⁢
h
⁡
(
Y
)
+
(
1
-
γ
)
⁢
L
YX
⁢
i
⁡
(
X
)
h
⁡
(
Y
)
=
γ
⁢
⁢
L
Y
⁢
a
⁡
(
Y
)
+
(
1
-
γ
)
⁢
L
YX
⁢
i
⁡
(
X
)
i
⁡
(
Y
)
=
a
⁡
(
Y
)
+
h
⁡
(
Y
)
wherein X={x1, x2, . . . xm} and Y={y1, y2, . . . yn} represent respective object sets of heterogeneous object type with relationships RX , RY , RXY and RYX if directionality is considered, LX and LY represent adjacent matrixes of links identifying relationships within set X and Y respectively, LXY and LYX represent adjacent matrixes of links identifying relationships from objects in X to objects in Y, a(X) and h(X) are an authority score and a hub score of nodes within X respectively, a(Y) and h(Y) respectively represent authority scores and hub scores of nodes in Y, i(X) and i(Y) respectively represent an importance of the nodes in X and Y, and β and γ are weight parameters to adjust influence of links derived from different relationships.

168 more elements

Dependencies are inferred from the claim text.

patentgrep

Loading patent…

Abstract

A computer-implemented method performed by a computing device that has one or more processors to execute instructions, the method comprising:

identifying relationships between multi-type data objects that include at least one object of a first type and at least one object of a second type different from the first type, the relationships being at least one of intra-layer relationships or inter-layer relationships among the multi-type data objects;
iteratively clustering the multi-type data objects based on the relationships to generate reinforced clusters;
generating a list of suggested search terms associated with a bid term using the reinforced clusters, the search terms generated in response to receiving the bid term from a user;
transmitting, via a network interface, the list of suggested search terms to a user;
and
mutually reinforcing an importance of individual ones of the multi-type data objects within an object type and between different object types based on the following:
{
a
⁡
(
X
)
=
β
⁢
⁢
L
X
T
⁢
h
⁡
(
X
)
+
(
1
-
β
)
⁢
L
XY
⁢
i
⁡
(
Y
)
h
⁡
(
X
)
=
β
⁢
⁢
L
X
⁢
a
⁡
(
X
)
+
(
1
-
β
)
⁢
L
XY
⁢
i
⁡
(
Y
)
i
⁡
(
X
)
=
a
⁡
(
X
)
+
h
⁡
(
X
)
a
⁡
(
Y
)
=
γ
⁢
⁢
L
Y
T
⁢
h
⁡
(
Y
)
+
(
1
-
γ
)
⁢
L
YX
⁢
i
⁡
(
X
)
h
⁡
(
Y
)
=
γ
⁢
⁢
L
Y
⁢
a
⁡
(
Y
)
+
(
1
-
γ
)
⁢
L
YX
⁢
i
⁡
(
X
)
i
⁡
(
Y
)
=
a
⁡
(
Y
)
+
h
⁡
(
Y
)
wherein X={x1, x2, . . . xm} and Y={y1, y2, . . . yn} represent respective object sets of heterogeneous object type with relationships RX, RY, RXY and RYX if directionality is considered LX and LY represent adjacent matrixes of links identifying relationships within set X and Y respectively, LXY and LYX represent adjacent matrixes of links identifying relationships from objects in X to objects in Y, a(X) and h(X) are an authority score and a hub score of nodes within X respectively, a(Y) and h(Y) respectively represent authority scores and hub scores of nodes in Y, i(X) and i(Y) respectively represent an importance of the nodes in X and Y, and β and γ are weight parameters to adjust influence of links derived from different relationships.

169 more elements