DEIM Forum 2016 A7-3

Finding “Coordinate” Relationships in Search Results
Meng ZHAO† , Hiroaki OHSHIMA† , and Katsumi TANAKA†† Department of Social Informatics, Graduate School of Informatics, Kyoto University
Yoshida Honmachi, Kyoto, 606–8501 Japan
E-mail: †{zhao,ohshima,tanaka}@dl.kuis.kyoto-u.ac.jp
Abstract We propose a method to structure search results of a user-given query depending on some perspectives,
while these perspectives are detected and extracted from the given data collection, and moreover, confirmed byuser perceptions on the Web. For example, in the case of news articles, take as an example the search results ofa keyword query “school shooting”. They can be grouped by diﬀerent events, such as “Oregon school shooting”,
or “Virginia Tech shooting”, or by developmental stages of events, such as “occurrence of an event”, “number ofcasualties”, or “end of the shooter”. However, since it is intellectually easier to understand “school shooting” byconsidering similar but diﬀerent events, our method finally chooses to cluster the collection into diﬀerent events,
viz. the former grouping. We aim at providing a more comprehensible way for users to have a whole and exhaustive
understanding of unstructured search results by transforming to perspective-based structured ones.
Key words coordinate relationship, clustering, Web search results
paper search”, which provides a way for users to access aca-

1. Introduction

demic papers indexed on the Web. Suppose one wants to
（注 1）

（注 2）

survey papers on ranking algorithm, and correspondingly,

play a more and more important role in people’s daily

issues a keyword query “ranking algorithm”. Figure 2(a)life. People can obtain a variety of information they wantshows papers found by Google Scholar（注 6）, while Figure 2(b)through search engines. Take two diﬀerent search services

shows papers found by Microsoft Academic Search（注 7）. Fromfor example. One is “news search”, which provides an im-

the figures, we can find that similar situations happen. The

portant access to Web versions of newspapers, magazines,

presentation of papers is a simple list. They do not show

and news wires. Suppose one wants to know recently hap-

any connections or relations between papers. For example,

pened school shootings, and correspondingly, issues a key-

paper A is a rival of paper B. Therefore, it is hard to sur-word query “school shooting”. Figure 1 shows search results

vey a research area by scanning the paper list. From thereturned by Google News（注 3） (at the time of writing the doc-

above discussion, we can find that the major problem is theument). From it, we can see that similar news articles, such

unstructured search results.

Nowadays, search engines, such as Google

and Bing

as ones about plan to fight gun violence, or Facebook shoot-Many previous work have tackled the problem by apply

ing massacre threat, are aggregated together. However, theclustering method [16] [17] [11] [20]. Clustering is the task ofpresentation of news articles is a simple list, which means itgrouping a set of objects in such a way that objects in themixes together diﬀerent events about school shooting. Al-

same group (called a cluster) are more similar (in some sensethough users can scan the list from top to bottom until theyor another) to each other than to those in other groups (clus-

have found the information they are looking for, it is hardters). Therefore, by clustering search results, similar Web

to pick up a certain event, for example, “Newtown school

pages (news articles or academic papers in the above exam-shooting”. Moreover, it is also hard to survey the whole topicples) are classified into the same group. However, results“school shooting”. The same happens when querying Yahoo

from the state-of-the-art clustering methods might deviateNews（注 4）. On the other hand, Bing News（注 5） cannot find any

from human cognition. In the previous “school shooting” ex-results for “school shooting”. Another example is “academic

ample, the following two news articles, titled “Oregon School
Shooting: 1 Student Dead, Suspect Also Killed” and “Sec-（注 1）：http://www.google.com

ond Suspect Pleads Guilty in Frederick High School Shoot-（注 2）：http://www.bing.com（注 3）：https://news.google.com（注 4）：http://news.yahoo.com（注 6）：https://scholar.google.com（注 5）：https://www.bing.com/news（注 7）：http://academic.research.microsoft.com

ing”, respectively, are more likely to be grouped in the samecluster, since both of them describe the injuries and deaths
during shootings. However, for human beings, it is naturaland intuitive to capture these two news articles as diﬀerent
events. One is “Oregon School Shooting”, and another is“Frederick High School Shooting”.

Oregon School Shooting: 1 Student Dead, Suspect Also Killed
At a press conference following the Oregon school
shooting this morning, police say one student was
gunned down at Reynolds High School in Troutdale,
Ore.

According to USA Today, oﬃcials later con-firmed that the shooter was also deceased. At thispoint...

Second Suspect Pleads Guilty in FrederickHigh School Shooting
The second of two men charged in a shooting thatwounded two teenage boys outside Frederick HighSchool at a basketball game pleaded guilty for hisrole in the incident Tuesday. Brandon Earl Tyler, 22,
pleaded guilty to two counts of first-degree assault.

Our objective is to structure search results of a user-given
query in such a way that it is intellectually easier for users
to understand the aggregation result. In order to accomplish this goal, we introduce “coordinate relationship” between pairs of documents. In brief, two documents are coordinate to each other if they talk about the same topic,
and moreover, their primary actions are similar, and doers
or receivers of actions are correspondingly coordinate. Our
notion is that coordinate documents should not be grouped
into the same cluster, since they are mutually exclusive insemantics. Hence, we first detect coordinate documents inthe Web search results, and then modify a clustering algorithm by giving a penalty to the distance between paris of
coordinate documents.
The remainder of the paper is organized as follows. We
dedicate Section 2. to the discussion of the previous work
on classic clustering, event detection and tracking in news
stream, and scientific literature clustering. We then discuss
the key concept of this work, “coordinate relationship” inSection 3.. In Section 4., we describe the details of our proposed method. In Section 5., we show experimental resultson news search and give an analysis of them. Finally, we
conclude the paper in Section 6..

Figure 1 Search results of “school shooting” by Google News.

2. Related Work
2. 1 Clustering
Clustering algorithms aim to create groups (called clusters) that are coherent internally, but clearly diﬀerent fromeach other. In other words, objects within the same cluster
should be as similar as possible; and objects in one cluster should be as dissimilar as possible from objects in otherclusters.
According to the structure of clusters, they can be broadlygrouped into two categories: flat clustering and hierarchical clustering. Flat clustering [3] [10] creates a flat set ofclusters, which means that its clusters are independent ofeach other. K-means [10] is the most important flat clustering algorithm, which takes an iterative refinement technique.
Given K, the number of clusters, the first thing to do is torandomly select K objects as initial cluster centers. The algorithm then moves the cluster centers around in space inorder to minimize the average squared Euclidean distance ofobjects from their cluster centers. This is done iteratively
by alternating between two steps until a stopping criterion is
met: reassigning objects to the cluster with the closest centroid, and recalculating each centroid based on the objects

(a)

(b)

Figure 2 Search results of “ranking algorithm”.

in each new cluster. On the other hand, hierarchical cluster-

mation contained in a news article are very helpful for RED.

ing [6] [7] [15] results in a hierarchy of clusters, which means

Since many work, including [19], only focus on the utilization

its clusters can be visualized using a tree structure (a den-of the contents, Li et al. [9] considered better representations

drogram). Its algorithms are either top-down (divisive) orof news events, which eﬀectively models both the contentsbottom-up (agglomerative). For example, bottom-up algo-

and time information.

rithms regard each object as a singleton cluster at the very

Nallapati et al. [13] made a similar attempt as us. They

beginning and then agglomerate pairs of clusters until all

also considered that viewing a news topic as a flat collection

clusters have been merged into a single cluster that containsof stories is not eﬃcient for users to understand the topic

all objects. Besides, hierarchical clustering algorithms do not

quickly. Hence, they introduced an event model to captureneed a pre-given number of clusters.

the rich structure of news events and their dependencies in

2. 2 News Event Mining

a news topic, such as the causality or temporal-ordering be-

Allan et al. introduced the concept of new event detection

tween pairs of news events. Their algorithm first groups(NED) in [1]. NED requires identifying news stories that dis-

news stories into unique events in the topic by using the ag-

cuss an event that has not already been reported in the past.

glomerative clustering with time decay, and then constructs

They proposed a possible definition of event as something

dependencies among them.

that happens at a particular time and place. However, there

Feng and Allan [4] [5] also dealt with the problem that news

are some problems with this definition. In their discussion,

topics are treated as a flat list, ignoring the intrinsic connec-

it is hard to define event, but it is easier to define parts oftion among each stories. In [4], they clustered text passages

event identity, the properties that make two events the same.

and then created links with scenario-specific rules to generate

Therefore, part of their problem became deciding what prop-

incident threading. While in [5], they removed the assump-erties of news stories can be used to distinguish diﬀerenttion that a news story covers a single topic, and consequently,

events. They found that news stories about the same event

extended the incident threading to passage level.

often occur in clumps and there must be something about
the story that makes its appearance worthwhile. Finally,
they used a single pass clustering algorithm and a thresholding model that incorporates the properties of events to

3. Coordinate Relationship
Here, we introduce a key concept in this paper, called “coordinate relationship”.

detect new events. Kumaran and Allan [8] tackled the same

“Coordinate relationship” exists in diﬀerent levels, suchproblem and employed text classification techniques as wellas term level, sentence level, passage level and document

as named entities to improve the performance of NED.

level. In term level, two terms are coordinate to each other

Compared with NED, Yang et al. proposed the concept

if a term shares a hypernym with another. For example,of retrospective news event detection (RED) in [19]. RED

since both “lemon” and “grapefruit” belong to citrus fruit

is defined as the discovery of previously unidentified events

category, they are coordinate terms. Here, “citrus fruit” isin historical news corpus. Both of contents and time infor-

their common hypernym. When it comes to sentence level,

we make an extension as stated in our previous work [21].

or the aﬀected of similar actions, such as the time and place

We believe a sentence can be mapped by a template andwhere events took place. In more details, the occurrence

an entity tuple. Take as an example the sentence “lemons

time of the Oregon shooting, October 1, 2015, is coordinate

are rich in vitamin c”. It can be generated by the templateto the occurrence time of the Virginia Tech shooting, April

X are rich in Y and the entity tuple (lemons, vitamin c).

16, 2007. Similarly, the occurrence location of the Oregon

Another entity tuple, such as (apples, pectin), is coordinate

shooting, UCC campus, is coordinate to that of the Virginia

to (lemons, vitamin c), since there also exists the highCon-

Tech shooting, campus of Virginia Polytechnic Institute andcentration relation between “apples” and “pectin” such that

State University.

apples contain a high amount of pectin. As a consequence,

Based on the above discussion, we know that primary ac-

two sentences are coordinate to each other if they satisfy

tions in documents can be regarded as an extension of tem-the following two conditions: (1) their templates convey theplates in sentences, but in a more abstract level; doers orsame meaning; (2) their entity tuples are coordinate to each

receivers of actions form an extension of entity tuples in sen-other. In the aforementioned example, the sentence “lemons

tences, no longer limited to two entities. As a consequence,are rich in vitamin c” is coordinate to the sentence “apples

in the following, we focus on these two observations to detect

contain a high amount of pectin”.

coordinate documents.

Let us go one step further and discuss “coordinate relationship” in document level. It can be regarded as an extension

4. Our Methodof that in sentence level. To understand the “coordinate re-As we mentioned in Section 1., we believe that the presen-lationship” in document level, we present an example. Con-tation of search results in a flat list is diﬃcult for users tosider the two news articles given below.

understand the intrinsic connection among individual search

Article 1: Oregon shooting

result. Therefore, our attempt is to group search results into

The Oregon shooting occurred on October 1, 2015 at theclusters such that documents in the same cluster talk about

UCC campus near Roseburg, Oregon, United States. Christo-

the same event; and documents in diﬀerent clusters describepher Harper-Mercer, a 26-year-old enrolled at the school,

diﬀerent events under the same topic (also called “coordinate

fatally shot an assistant professor and eight students in a

events”). Besides, within each cluster, we also show the de-classroom. Seven to nine others were injured. After beingvelopment of an event, such as the beginning, the outcome,wounded by two police oﬃcers, the gunman committed sui-or the impact of an event.

cide by shooting himself in the head.

Our notion is that coordinate documents should not be

Article 2: Virginia Tech shooting

grouped into the same cluster, since they are mutually ex-

The Virginia Tech shooting occurred on April 16, 2007, on

clusive in semantics. Hence, we first detect coordinate docu-

the campus of Virginia Polytechnic Institute and State Uni-ments in the Web search results, and then modify a clustering

versity in Blacksburg, Virginia, United States. Seung-Huialgorithm by giving a penalty to the distance between paris

Cho, a senior at Virginia Tech, shot and killed 32 peopleof coordinate documents.

and wounded 17 others in two separate attacks, approximately two hours apart, before committing suicide.
While both these articles talk about school shootings andtheir casualties, they obviously are about diﬀerent events. In
human cognition, it is easy to distinguish them as two different events under the topic “school shooting”. We foundthat there are two main reasons. First, the primary actions
in both these articles are similar (see terms or phrases inbold). For example, in the beginning of both these articles, it states the occurrence of an event, using exactly thesame term “occurred”. When it comes to the injuries anddeaths of each shootings, article 1 used the term “injured”,
while article 2 used the term “wounded”. Though these twoterms have diﬀerent surface forms, they have the same semantic meaning. Second, the doers of similar actions aresomekind of coordinate to each other. So are the receivers

4. 1 Finding Coordinate Documents
As we discussed in Section 3., two documents are coordinate to each other if they talk about the same topic, andmoreover, their primary actions are similar, and doers or receivers of actions are correspondingly coordinate. Since wedevote to help users quickly and better capture search resultsof their queries, we assume that the issued query is a topic
that they concern with. Consequently, search results of acertain query are regarded to talk about the same topic. As
a result, the problem of finding coordinate documents turns
to the following two sub-problems:•confirming coordinate relationships between pairs ofdoers or receivers.
•

confirming semantic similarities between pairs of ac-

tions.
Since doers or receivers are nouns or noun phrases, and actions are described by verbs, we extract nouns/noun phrases

and verbs and treat them in diﬀerent ways.

on the Web.

4. 1. 1 Coordinate Relationship Confirmation
Since two terms are coordinate to each other if they share acommon hypernym, it is intuitive to verify whether two terms
are coordinate to each other by finding if they share any com-

Algorithm 1 Constrained Hierarchical Agglomerative Clustering Algorithm
Input: Set of documents D = {d1 , d2 , ..., dN },set of pairs of coordinate documents C = {(di , dj )},mon hypernyms. Therefore, an intuitive way is to check dictionaries. WordNet [12] is a lexical database for the English

distance function dist(di , dj ).
Output: Disjoint partitioning C = {C1 , C2 , ...}of D.

language, widely used as a dictionary or thesaurus. In Word-for i = 1 to N dofor j = 1 to N do

Net, terms are grouped into sets of synonyms called synsets,

I[i][[j] ⇐ dist(di , dj )while each synset expresses a distinct concept. Moreover,end forsynsets are interlinked by means of conceptual-semantic andend forlexical relations. Given a synset, more general synsets (hy-C ⇐ []

pernyms) can be found. As a result, we can confirm coordi-

for k = 1 to N − 1 donate relationship between a pair of terms (or part of phrases)< i, m >⇐ arg min I[i][m]<i,m>:i=m|

by using hypernym information in WordNet.

C.AP P EN D(< i, m >)However, just like other dictionaries, for terms or phrases

for n = 1 to N do
I[i][j] ⇐ dist(i, m, n)

not in WordNet, nothing can be found through it. So we

I[j][i] ⇐ dist(i, m, n)turn our eyes on the Web, the greatest data factory. But weend fordo not find shared hypernyms anymore. Instead, we directlyend forcheck whether two terms are coordinate or not by coordinate conjunctions, such as “and”, or “or”. The idea is froma bi-directional lexico-syntactic pattern-based algorithm [14],4. 1. 2 Semantic Similarity Confirmation

which can quickly acquire coordinate terms (or phrases) for

Since we can get synonyms of terms from WordNet, a sim-any query term (phrase). Suppose we want to confirm theple way to check whether two verbs are semantically similar iscoordinate relationship between Umpqua Community College

to see whether they are synonyms in WordNet. However, stilland Virginia Polytechnic Institute and State University. The

we have the problem that nothing can be found if the verb

following two queries are generated and queried on the Web.

is not in WordNet. We again use the Web to confirm seman-- “Umpqua Community College and Virginia Polytech-tic similarity between verbs. In our previous work [21], westated that if two templates convey the same meaning, theynic Institute and State University”- “Virginia Polytechnic Institute and State University

share many common entity tuples. Similarly, if two verbs are

and Umpqua Community College”

semantically similar to each other, they should have many

If both these two queries can have search results returned, it

common entity tuples. Based on this hypothesis, we extract

shows that Umpqua Community College is coordinate to Vir-

entity tuples for each verb from the Web and regard them as

ginia Polytechnic Institute and State University. Otherwise,

the context of each verb. Suppose we want to check whether

they are not coordinate to each other.

“wound” is a synonym of “hurt”. Since in most cases, search

Besides, since we focus on certain topics, the queries given

results of a single verb cover vast quantities of diﬀerent in-

by users, we also take topics into consideration. It means

formation, we use the user given query for limitation. Stillwhen we check the coordinate relationship, we also consider

take the “school shooting” for example. For “wound”, thethe context where terms (or phrases) are. Therefore, in thegenerated query is wound AND “school shooting”, while for“school shooting” example, the aforementioned two queries“hurt”, the generated query is hurt AND “school shooting”.

turn to be

Nouns or Noun phrases just before or just after the verb are- “Umpqua Community College and Virginia Polytech（注 8）

nic Institute and State University” AND“school shoot-ing”

extract from the top N Web search results. They constructentity tuples, further. For example, we have (gunshot, jaw),(gunshot, head), (shot, arm) for “wound”. Then these entity- “Virginia Polytechnic Institute and State University

tuples are used to generate a vector, which represents theand Umpqua Community College” AND “school shooting”

context of a certain verb. A tf/idf weighting is applied toThen, similarly, the confirmation is based on their occurrence

weigh each element in vectors. Two verbs are similar if thecosine similarity of their vectors are greater than a threshold（注 8）：Notice that this “and” indicates an AND search rather than aconjunction in natural language.

θ.

4. 1. 3 Constrained HAC based on Coordinate Documents
As we discussed before that coordinate documents are mutually exclusive, they should not be grouped in the samecluster. It is a meaningful selection of cannot-link con-the Web search results, and then modify a clustering algorithm by giving a penalty to the distance between paris of
coordinate documents.

Acknowledgment

straints（注 9）[18]. In previous work [2] [18], cannot-link pairs

This work was supported in part by the following projects:

are selected by manual, while we aim at choosing these con-

Grants-in-Aid for Scientific Research (Nos. 15H01718 andstraints automatically.

24680008) from MEXT of Japan.

Our clustering algorithm is shown in Algorithm 1. We firstcompute the N × N distance matrix I, where penalties are
given based on coordinate degree between documents. The
algorithm then executes N − 1 steps of merging the currently most similar clusters. In each iteration, the two most

References

similar clusters are merged and correspondingly, there is a[1] Allan, J., Papka, R., Lavrenko, V.: On-line new event detection and tracking. In: Proceedings of the 21st Annual
International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 37–45. SIGIR ’98,
ACM (1998)[2] Basu, S., Banerjee, A., Mooney, R.J.: Active semisupervision for pairwise constrained clustering. In: Proceedings of the 2004 SIAM International Conference on Data
Mining (SDM-04) (April 2004)[3] Dempster, A.P., Laird, N.M., Rubin, D.B.: Maximum likelihood from incomplete data via the em algorithm. Journalof the Royal Statistical Society, Series B 39(1), 1–38 (1977)[4] Feng, A., Allan, J.: Finding and linking incidents in news.
In: Proceedings of the Sixteenth ACM Conference on Conference on Information and Knowledge Management. pp.
821–830. CIKM ’07, ACM (2007)[5] Feng, A., Allan, J.: Incident threading for news passages.
In: Proceedings of the 18th ACM Conference on Information and Knowledge Management. pp. 1307–1316. CIKM
’09, ACM (2009)[6] F.Murtagh: A survey of recent advances in hierarchicalclustering algorithms. The Computer Journal 26, 354–359(1983)[7] G.N.Lance, W.T.Williams: A general theory of classificatory sorting strategies. The Computer Journal 9, 373–380(1967)[8] Kumaran, G., Allan, J.: Text classification and named entities for new event detection. In: Proceedings of the 27th
Annual International ACM SIGIR Conference on Researchand Development in Information Retrieval. pp. 297–304. SIGIR ’04, ACM (2004)[9] Li, Z., Wang, B., Li, M., Ma, W.Y.: A probabilistic model
for retrospective news event detection. In: Proceedings ofthe 28th Annual International ACM SIGIR Conference on
Research and Development in Information Retrieval. pp.
106–113. SIGIR ’05, ACM (2005)[10] MacQueen, J.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the 5thBerkeley Symposium on Mathematical Statistics and Probability. pp. 281–297 (1967)[11] Mecca, G., Raunich, S., Pappalardo, A.: A new algorithm
for clustering search results. Data Knowl. Eng. 62(3), 504–
522 (Sep 2007)[12] Miller, G.A.: Wordnet: A lexical database for english. Commun. ACM 38(11), 39–41 (1995)[13] Nallapati, R., Feng, A., Peng, F., Allan, J.: Event threading within news topics. In: Proceedings of the Thirteenth
ACM International Conference on Information and Knowledge Management. pp. 446–453. CIKM ’04, ACM (2004)[14] Ohshima, H., Oyama, S., Tanaka, K.: Searching coordinate

update in I. The clustering is stored as a list of merges in
C. The function dist(i, m, n) computes the distance between
cluster Cn and the new cluster that merged cluster Ci and
Cm . Single-link, complete-link or average-link can be usedhere.

5. Evaluations
Currently, we concentrate on News search. In other words,
the search results we tackle with are news articles at present.
Since our objective is to structure search results of a usergiven query, we plan to prepare 100 keyword queries for evaluation. Besides, those 100 queries are chosen from diﬀerent
categories, such as world, business, technology, entertainment, sports, science and health. Our claim is that withthe help of our organization of search results, it is intellectually easier for users to understand a topic. Hence, a user
study will be constructed to demonstrate that our structureof search results better fits human cognition.

6. Conclusion
The presentation of search results in a flat list is diﬃcult
for users to understand the intrinsic connection among individual search result. Besides, it is also hard to survey a usergiven topic by scanning the flat list. As a result, we proposeda method to structure search results of a user-given query insuch a way that it is intellectually easier for users to understand the aggregation result. We defined two documents arecoordinate to each other if they talk about the same topic,
and moreover, their primary actions are similar, and doers or
receivers of actions are correspondingly coordinate. Our basic idea is that coordinate documents should not be grouped
into the same cluster, since they are mutually exclusive insemantics. Hence, we first detect coordinate documents in（注 9）：Cannot-link constraints specify that two in- stances must not

be placed in the same cluster.

[15]
[16]

[17]

[18]

[19]

[20]

[21]

terms with their context from the web. In: Proceedings ofWISE. pp. 40–47 (2006)
Olson, C.F.: Parallel algorithms for hierarchical clustering.
Parallel Computing 21(8), 1313–1325 (1995)
Osinski, S., Stefanowski, J., Weiss, D.: Lingo: Search results clustering algorithm based on singular value decomposition. In: Proceedings of the International Intelligent Information Processing and Web Mining. pp. 359–368. IIPWM’04, Springer Berlin Heidelberg (2004)
Osinski, S., Weiss, D.: A concept-driven algorithm for clustering search results. IEEE Intelligent Systems 20(3), 48–54(May 2005)
Wagstaﬀ, K., Cardie, C., Rogers, S., Schrödl, S.: Constrained k-means clustering with background knowledge. In:
Proceedings of the Eighteenth International Conference on
Machine Learning. pp. 577–584. ICML ’01, Morgan Kaufmann Publishers Inc. (2001)
Yang, Y., Pierce, T., Carbonell, J.: A study of retrospective and on-line event detection. In: Proceedings of the 21st
Annual International ACM SIGIR Conference on Researchand Development in Information Retrieval. pp. 28–36. SIGIR ’98, ACM (1998)
Zeng, H.J., He, Q.C., Chen, Z., Ma, W.Y., Ma, J.: Learning
to cluster web search results. In: Proceedings of the 27th
Annual International ACM SIGIR Conference on Researchand Development in Information Retrieval. pp. 210–217. SIGIR ’04, ACM (2004)
Zhao, M., Ohshima, H., Tanaka, K.:
Sentential
query rewriting via mutual reinforcement of paraphrasecoordinate relationships. In: Proceedings of the 17th International Conference on Information Integration and Webbased Applications & Services. iiWAS 2015 (2015)