一般論文

DBSJ Journal, Vol.7, No.3
December 2008

Querying Topic Evolution in Time Series Document Clusters

in clusters over time [6, 7, 10]. Some further developped visualizing tools for browsing clusters and exploring trends
in time series clustering results [1, 4]. In these works,
without browsing, it is still difficult to obtain informationof user interest.
Consider, for example, a sequence of clustering results
as shown in Fig. 1. A user is interested in the US Democrat
presidential nomination campaign. The topic can be represented, for example, by the keywords clinton, obama,
campaign. The user wants to find occurrences of clusters,
as shown in Fig. 1, highly related to the keywords. As another example, a user wants to know whether the topic
Clinton, campaignn dissolves and changes to Obama,
campaign? Or does Clinton, campaign merge with
Obama campaign and form a broader topic Democrat,
campaign? To the best of our knowledge, none of existing
methods support such user requirements. By manually exploring the data, it is not easy for the user to judge whether
those likely clusters correctly respond to his/her interest.

Sophoin KHY Yoshiharu ISHIKAWA
Hiroyuki KITAGAWA
A document clustering method for time series documents produces a sequence of clustering resultsover time. Analyzing the contents and trends in along sequence of clustering results is a hard andtedious task since there are too many number ofclusters. In this paper, we propose a framework
to find clusters of users’ topics of interest and evolution patterns called transition patterns involving
the topics. A cluster in a clustering result may
continue to appear in or move to another cluster,branch into more than one cluster, merge with otherclusters to form one cluster, or disappear in the adjacent clustering result. This research aims at providing users facilities to retrieve specific transition
patterns in the clustering results. For this purpose,
we propose a query language for time series document clustering results and an approach to query
processing. The first experimental results on TDT2
corpus clustering results are presented.

Time

1

Introduction

Jan 1

As information is more pervasive and overwhelming,organizing and extracting salient information becomes achallenging task. Document clustering is a method used
to find and group documents such that documents in thesame clusters are similar with each other and are dissimilar from other documents in different clusters. It has beenused as a fundamental and pre-processing method in many
areas, such as information retrieval [3], topic detection andtracking [2], text classification [9] and summarization of
documents [8].
A document clustering method for time series documents such as the one in reference [5] produces a sequenceof snapshots of clustering results over time (Fig. 1). Tracking topic evolution in a large stream of clusters is very important in the analysis of the characteristics of the data
and the real world events. Analyzing the contents andtrends in a long sequence of clustering snapshots, however,is a hard and tedious task since there are too many number of clusters; a user may need to access every cluster andread every document contained in each cluster. Some recent works have embraced tracing and analyzing changes

Jan 8

Jan 15

Jan 22

Jan 29Figure 1: A Sequence of Clustering Results(a) persist(b) branch(c) merge

Figure 2: Transition Patterns
Further, in a sequence of clustering results of time series
documents, a cluster in a clustering result may persist inanother cluster, branch into more than one cluster, merge
with other clusters to form one cluster, or disappear in theadjacent clustering result. These phenomena are called
cluster transitions in reference [10] and we call the occurrence patterns of one or more such phenomena together,as shown in Fig. 2, transition patterns. In this paper, we
propose a framework to find clusters related to users’ topics of interest and transition patterns involving the topics.
Specifically, we aim at providing users facilities to retrieve
specific transition patterns in the clustering results. For
this purpose, we propose a query language for time series
document clustering results and an approach to query processing. Given a query of a transition pattern, it finds occurrences of cluster transitions that match the given pattern and are relevant to the query. The results are ranked
and returned to the users.

Student Member. Graduate School of System and Information
Engineering, University of Tsukuba.
sophoin@kde.cs.tsukuba.ac.jp

 Regular Member. Information Technology Center, Nagoya University. ishikawa@itc.nagoya-u.ac.jp

 Regular Member. Graduate School of System and Informa-tion Engineering / Center for Computational Science, Universityof Tsukuba. kitagawa@cs.tsukuba.ac.jp1

日本データベース学会論文誌 Vol.7, No.3
2008 年 12 月

一般論文

DBSJ Journal, Vol.7, No.3
December 2008

Query ::= Find_Clause From_Clause With_Clause
Find_Clause ::= ’find’ Transition_Pattern
From_Clause ::= ’from’ G
With_Clause ::= ’with’ Bindings
Transition_Pattern ::= Snapshot_Spec(-> Snapshot_Spec)*
Snapshot_Spec ::= Node | ’{’ Node_List ’}’
Node_List ::= Node (, Node)*
G ::= Seq_Name(’[’TimeStamp, TimeStamp’]’)?
Bindings ::= Node ’=’ Keyword_List (, ’and’
Node ’=’ Keyword_List)*
Keyword_List ::= ’{’Keyword (, Keyword)*((, ’not(’Keyword’)’)*)?’}’The remainder of this paper is organized as follows. Section 2 reviews related work. The preparations in this work
are described in Section 3. Section 4 introduces the querylanguage and explains the query processing scheme. The
evaluation of the query language is shown in Section 5.
Section 6 concludes the paper and discusses future work.

2

Related Work

There are several researches on identifying relationshipbetween clusters. Mei et al. proposed an approach todiscovering the evolutionary patterns of themes in a text
stream [6]. In the approach, themes are generated using
a probabilistic mixture model and theme evolutionary relations are discovered. Nallapati et al., based on the notion of events and topics in TDT [2], identified events thatmake up a topic and established dependencies among them[7]. Several dependency models have been proposed in theapproach. Though the underlying problem in finding transitions between clusters is relevant to our work, the two
approaches do not restrict to finding transitions between
two consecutive time points, but finding all possible transitions between clusters from all time instances. These approaches aim at finding all relevant topics. Hence, theirunderlying objectives differ from our approach.
Spiliopoulou et al. proposed an approach called MONIC
to model and track cluster transitions on clustering results
at consecutive time points [10]. A cluster transition at agiven time point is a change experienced by a cluster thathas been discovered at an earlier time point. A transition
may concern the content and form of the cluster, which isinternal to it, or it may concern its relationship to the restof the clustering, which is an external transition. MONIC
detects both internal and external transitions of clusters
and models their lifetime. The cluster transition graph(Section 3.2) in our approach is based on the idea of external transitions in MONIC.
T-Scroll [4] is an information visualization interface tool
to visualize the overall trend of time series documents. It
displays links between clusters, which represents related
clusters from two consecutive time points, and allows users
to explore more detailed information such as keyword lists
and contents of documents in a cluster. In addition, Adomavicius et al. in reference [1] proposed a data analysis and visualization technique for representing trends in
multiattribute temporal data called C-TREND, a system
for temporal cluster construct. The idea in T-Scroll and
C-TREND is partly related to our work. However, in ourwork, we proposed a query language for temporal clusters
aiming at providing users facilities to search for specificpatterns in the clustering results.

3

Figure 3: The BNF of the Query Language  
. All clusters in each       are assumed
non-overlapped, i.e.,          , if  .
3.2 Constructing Cluster Transition Graph
A cluster transition, proposed in reference [10], at a given
time point is a change experienced by a cluster that has
been discovered at an earlier time point. It provides insights about the nature of cluster changes: is a cluster a
newly emerged cluster or a disappeared one or does someof its member move to different clusters. In this work, weconstruct the cluster transition graph based on the idea ofcluster transitions in reference [10].
A cluster transition graph is constructed by connecting
pairs of adjacent clustering results. A pair of two adjacentclustering results  at time point   and  at the successive time point   is connected by detecting transitions
between all clusters in  and  as follows.
For each cluster  in  and   in  , the degree towhich  overlaps   is measured. The following function,
the transition probability of the number of documents thatwere in  and moved to   , is used in this work.

      

(1)where  and   are the number of documents in  and  , respectively.

A list of clusters in  , which are matched clusters ofclusters in  , and the corresponding transition probability values are obtained. Then, links between clusters and,hence, graphs can be constructed.

4

The Query Language

4.1 The Query Language Syntax

Preparations

The query language proposed in this paper is a quite simple declarative language of small number of constructs, but
can represent information needed for analyzing document
clustering snapshots and detect transition patterns. Figure 3 shows the extended BNF notation of the query language.

3.1 Target Data

The target data in this work is a collection of accumulated
at consecutive time
document clustering results
points      generated by a clustering method on timeseries documents where a sliding window is adopted.
Let      be document sets in which   is the document set from which the document clustering result  isgenerated.   is assumed to be overlapped with   , i.e.,

4.2 Examples of Queries
The following examples show the query language syntax.

2

日本データベース学会論文誌 Vol.7, No.3
2008 年 12 月

一般論文




Query 1
find C -> Cfrom S08-7days[2008-Jan-01, 2008-Feb-28]
with C = {clinton, obama, campaign}In the examples in this section, we assume S08-7days
is the name of a sequence of document clusters and suppose it contains a sequence of document clusters fromJanuary 1, 2008 to present, and the clustering was performed based on seven-day incremental basis. The notation S08-7days[2008-Jan-01, 2008-Feb-28] specifies the restriction on the scope of the query target to theperiod between January 1, 2008 and February 28, 2008
within S08-7days.

1: C#Jan15-5 -> C#Jan22-4
2: C#Jan1-3 -> C#Jan8-2
...







The following example shows a query using different
keyword sets for two clusters.
Query 3find C1 -> C2from S08-7days[2008-Jan-01, 2008-Feb-28]
with C1 = {clinton, campaign, not(obama)},and C2 = {obama, campaign, not(clinton)}This query retrieves cluster transitions, where the firstcluster corresponds to clinton, campaign but does not include obama, and the second one corresponds to obama,
campaign but does not include clinton.



4.3 Examples of Query Processing

It is a ranked list of cluster transitions corresponding
to the query. The user may be able to specify the preferred number of entries in the list. The notation such as
C#Jan15-5 denotes the identity of a cluster. In this case, it
represents the fifth cluster of January 15 clustering snapshot.

Query 2find C -> C -> Cfrom S08-7days[2008-Jan-01, 2008-Feb-28]
with C = {clinton, obama, campaign}









The next example shows a query to retrieve the repeatedoccurrences of a transition with length two.

Query 4find C1 -> {C2, C3}from S08-7days[2008-Jan-01, 2008-Feb-28]
with C1 = {clinton, obama, campaign}, andC2 = {clinton, not(obama)}, andC3 = {obama, not(clinton)}

The query wants to find the occurrences of two transitions  and   , where  and  branch from  andare highly related to the given keywords.
The next one is the opposite; it contains a transition pattern of merge.
Query 5find {C1, C2} -> C3from S08-7days[2008-Jan-01, 2008-Feb-28]
with C1 = {clinton, not(obama)}, andC2 = {obama, not(clinton)}, andC3 = {clinton, obama, campaign}

In the above query example, the transition pattern
C -> C in the find clause specifies the occurrences of thecluster transition to be found. The with clause with C= clinton, obama, campaign specifies the associate
keywords for cluster C; it means we want to find occurrences of the cluster transition C -> C in which both clusters can be represented by the keywords clinton, obama,
campaign.
The results of the query are given, for example, as follows.

DBSJ Journal, Vol.7, No.3
December 2008






In this section, the processing scheme of the query language regarding the query examples in Section 4.2 is givenin the same order as follows.

4.3.1 Query 1: The Most Simple Case
We consider to answer Query 1. Let the set of keywords
. In the exappearing in the with clause beample, is clinton, obama, campaign.
The find clause specifies that the two clusters, whichhave a transition, correspond to the same query , but arefrom two different clustering results at consecutive time
points. To avoid confusion, the two clusters are denoted as and  , where  temporally precedes  . We define the in terms of queryscore for the cluster transition by

        

 



(2)

Intuitively, the score gives a probability that the occurrence of a cluster transition is related to the given query .
The score is calculated and used to rank the query results.
Next, we consider how to derive the probabilities   and  .
   can be defined as



 



  

(3)

where    is defined in Eq. 1 in Section 3.2.
  is a conditional probability that given the query, we obtain  as a relevant cluster to . It is defined as    

(4)

where     is the occurrence probability of a query
term  of in cluster  . It is defined as follows.

The following query contains a transition pattern with abranch.

    3    





(5)



日本データベース学会論文誌 Vol.7, No.3
2008 年 12 月

一般論文

DBSJ Journal, Vol.7, No.3
December 2008

4.3.4 Query 4: Query with Branch

where

 is the set of all terms appeared in the doc     is the total frequency
uments in cluster  andof  in  and is defined as follows.
Suppose  contains documents       and let thefrequency of term  in document  be     . The totalfrequency of  in  is defined by:       

We consider Query 4. We assume the two cluster transitions are independent.








(6)

 

                    



(10)

The results can be evaluated using the same approachas Query 1 and Query 3.

In summary, we get                  


4.3.5 Query 5: Query with Merge







  










         

For Query 5, we use the same assumption as Query 4that the two transitions are independent.



(7)





5

4.3.2 Query 2: Long Sequence                              

We consider Query 3. In this case, we need to consider
two keyword sets for  and  . Let the corresponding keyand  be .
word sets for  be
In the example, their contents are clinton, campaign,not(obama) and obama, campaign, not(clinton), respectively.
In this query language, not() in the with clause isa predicate used to negate the effect of the query keyword
in it. If a query contains the predicate is, for example, C= clinton, campaign, not(obama),   is computed asfollows.

                                     


 



Evaluation

5.2 Results and Discussion

Finally, similar to Query1, we process this query as follows.

           (11)

In this evaluation, the document clustering results of an
extended-  -means-based incremental clustering method
on TDT2 Corpus [11] in reference [5] is used as the data
set. The TDT2 Corpus consists of chronologically orderednews stories obtained from various sources. The clustering results were generated by three-day incremental basis.
We used 20 sets of clustering results dated from February
2 to March 31, 1998. Each clustering result contains 17
clusters and is associated with a timestamp, the date theclustering was performed.
Due to limitations in the data, some transition patterns and query keywords may not give meaningful results. Query keywords should be chosen such that the results are not empty. For this evaluation, we chose keywords which represent topics in the TDT2 Corpus. In addition, for query patterns of branch and merge, we use thesame query keyword sets for all clusters C1, C2 and C3.
 C -> C pattern, bomb, abortion, clinic; italy, cable, car, crash; pope, cuba; monica, clinton;
tornado, florida; iraq, weapon, inspection C1 -> {C2, C3} pattern, C1 = C2 = C3 = monica,
clinton; iraq, weapon, inspection
 {C1, C2} -> C3 pattern, C1 = C2 = C3 = monica,
clinton; iraq, weapon, inspection

(8)

4.3.3 Query 3: Different Keyword Sets

5.1 Experimental Setup

The two probabilities can be calculated using themethod of Query 1.

   

In this section, we evaluate the proposed query language
and processing scheme described above.
For the implementation,     (Eq. 5) and    
(Eq. 1) are computed beforehand and stored persistently sothat we can retrieve them when needed in the computationof query scores.

Next, we consider Query 2. In this case, we assume thetwo transitions are nearly independent and approximate
the probability.
                    

To evaluate the query results, topic labels for clusters of
the clustering data are used as evaluation data. A topic
label for a cluster was obtained by measuring precision of
the cluster against the evaluation data of the TDT2 Corpus. If the precision score of the cluster for a topic is larger
than a threshold, the cluster was labeled with the topic.

(9)4日本データベース学会論文誌 Vol.7, No.3
2008 年 12 月

一般論文

DBSJ Journal, Vol.7, No.3
December 2008

Table 2: Top-10 Results of C
C Patterns of Querybomb, abortion, clinic

Table 1: Clusters and Labeled Topics
Cluster ID
Feb05-7, Feb08-8, Feb11-4, Feb14-4, Feb17-4,
Feb17-4, Feb20-4, Feb23-4, Feb26-3, Mar01-3,
Mar04-2, Mar07-2, Mar10-2, Mar13-4, Mar16-4,
Mar19-3, Mar22-3, Mar25-3, Mar28-3, Mar31-3
Feb08-3, Feb11-3, Feb14-3, Feb17-3, Feb17-3,
Feb20-3, Feb23-3, Feb26-2, Mar01-2, Mar04-1,
Mar07-1, Mar10-1, Mar13-3, Mar16-3, Mar19-2,
Mar22-2, Mar25-2, Mar28-2, Mar31-2
Feb02-6, Feb02-12, Feb05-11, Feb08-7,
Feb08-12, Feb11-12, Feb14-12, Feb17-12,
Feb20-12, Feb23-12, Feb26-12, Mar1-12,
Mar4-12
Feb02-3, Feb02-5, Feb05-3, Feb05-6, Feb08-6,
Feb11-7, Feb14-7, Feb17-10, Feb20-10,
Feb23-10, Feb26-9, Feb26-10, Mar01-10,
Mar04-10, Mar07-9, Mar10-9, Mar13-11,
Mar16-11, Mar19-9, Mar22-5, Mar22-9,
Mar25-5, Mar25-10, Mar28-5, Mar28-9,
Mar31-5, Mar31-10
Feb02-0, Feb05-0, Feb05-5, Feb08-0, Feb08-5,
Feb11-0, Feb11-6, Feb14-0, Feb14-6, Feb17-0,
Feb20-0, Feb23-0, Feb26-0, Mar01-0, Mar01-8,
Mar01-14, Mar04-8, Mar04-14, Mar07-7,
Mar07-14, Mar10-7, Mar10-14, Mar13-9,
Mar16-10, Mar19-8, Mar19-14, Mar22-13,
Mar25-8, Mar25-13, Mar28-7, Mar28-12,
Mar31-8, Mar31-14

Topic Name
Bombing
AL Clinic

Query bomb, abortion, clinic
Mar16-4
Mar19-3
Mar19-3
Mar22-3
Mar22-3
Mar25-3
Mar25-3
Mar28-3
Mar13-4
Mar16-4
Feb11-4
Feb14-4
Feb14-4
Feb17-4
Feb17-4
Feb20-4
Feb20-4
Feb23-4
Mar04-2
Mar07-2

Cable Car
Crash
Pope Visits
Cuba
MonicaLewinsky
Case

Score
4.48E-10
4.48E-10
4.48E-10
3.77E-10
2.85E-10
2.14E-10
1.91E-10
1.91E-10
1.91E-10
1.90E-10

Table 3: Top-10 Results of C
C Patterns of Query
italy, cable, car, crash
Query italy, cable, car, crash
Feb08-3 Feb11-3
Feb11-3 Feb14-3
Feb14-3 Feb17-3
Feb20-3 Feb23-3
Feb23-3 Feb26-2
Feb26-2 Mar01-2
Mar01-2 Mar04-1
Feb17-3 Feb20-3
Mar04-1 Mar07-1
Mar13-3 Mar16-3

Current
Conflictwith Iraq

Table 1 shows some cluster ID’s and the topic labels forthe clusters of the clustering data when the threshold is
set to 0.5. Ideally, clusters in Table 1 should appear in top
ranked results of the queries for the topics.
Due to space constraint, we show only results of somequeries. For the transition pattern C -> C, query bomb,abortion, clinic returns 36 instances as results; italy, cable, car, crash 39 instances; pope, cuba 21 instances;monica, clinton 53 instances; tornado, florida 24 instances; iraq, weapon, inspection 91 instances. Tables 2, 3, and 4 show top-10 results of queries bomb,abortion, clinic, italy, cable, car, crash and pope,
cuba, respectively. For the transition pattern of branch
C1 -> {C2, C3}, query monica, clinton returns 20
instances as results; iraq, weapon, inspection 30 instances. Table 5 shows top-10 results of query iraq,
weapon, inspection. For the transition pattern of merge{C1, C2} -> C3, query monica, clinton returns 19 instances as results; iraq, weapon, inspection 52 instances.
Table 6 shows top-10 results of query monica, clinton.
We compared the clusters in the query results with theevaluation data in Table 1. Low-ranked results generally
have very small occurrence frequencies of the query keywords in the clusters and small transition probability values between the clusters. That is they are less similar to
the topic of the query. The results in the middle ranks
have either small occurrence frequencies of the query keywords and high transition probability values, or high occurrence frequencies of the query keywords and low transition probability values. The results in the top ranks ingeneral have high occurrence frequencies of the query keywords and high transition probability values. Top- results
mostly contain transitions highly relevant to the topic of

Score
1.67E-16
1.48E-16
1.08E-16
1.02E-16
1.02E-16
1.02E-16
1.02E-16
9.38E-17
2.18E-17
8.50E-18

the query. Top  thus provide meaningful results.

6

Conclusions and Future WorkIn this paper, we presented a novel declarative querylanguage and its processing scheme to retrieve transition
patterns in time series document clustering results. The
query language is composed of simple and small constructs
but can retrieve interesting and meaningful patterns. The
experimental evaluation confirmed the effectivenss of thequery processing scheme.
Depending on the applications and user requirements,
other transition patterns may be interesting. The querylanguage is not limited to only clustering data set. It canbe applied to any sequences of a time series of grouped dataset, which can be regarded as clusters in some sense, andwhere cluster transitions can be detected. Applications of
the query language to other data set and further extension of the query language may present more interesting
retrieval results and effectiveness of the language. In addition, a visualizing tool to highlight retrieval results inthe sequence of periodical clustering results can facilitate
users in analyzing and exploring the data.

[Acknowledgements]
This research is partly supported by the Grant-in-Aid
for Scientific Research (19300027) from Japan Society for
the Promotion of Science (JSPS) and the Grant-in-Aid for
Scientific Research (19024006) from the Ministry of Education, Culture, Sports, Science and Technology (MEXT),
Japan.

5

日本データベース学会論文誌 Vol.7, No.3
2008 年 12 月

一般論文

DBSJ Journal, Vol.7, No.3
December 2008

Table 4: Top-10 Results of C
C Patterns of Querypope, cubaQuery pope, cubaFeb02-12 Feb05-11
Feb05-11 Feb08-12
Feb11-12 Feb14-12
Feb08-12 Feb11-12
Feb14-12 Feb17-12
Feb17-12 Feb20-12
Mar01-12 Mar04-12
Feb26-12 Mar01-12
Feb20-12 Feb23-12
Feb23-12 Feb26-12

Table 6: Top-10 Results of Merge Patterns of Querymonica, clinton

Score
1.73E-06
1.70E-06
1.69E-06
1.60E-06
9.59E-07
4.54E-07
4.40E-07
4.03E-07
2.10E-07
1.36E-07

Query monica, clintonMar28-5, Mar28-9 Mar31-5
Mar22-5, Mar22-9 Mar25-5
Feb05-3, Feb05-6 Feb08-6
Feb02-3, Feb02-5 Feb05-6
Mar25-10, Mar25-5 Mar28-5
Mar22-5, Mar22-9 Mar25-10
Feb26-10, Feb26-9 Mar01-10
Feb02-3, Feb02-5 Feb05-3
Mar22-13, Mar22-9 Mar25-10
Mar22-13, Mar22-5 Mar25-10

Table 5: Top-10 Results of Branch Patterns of Queryiraq, weapon, inspection
Query iraq, weapon, inspection
Mar25-13
Mar28-7, Mar28-12
Mar25-8
Mar28-7, Mar28-12
Feb05-0
Feb08-0, Feb08-5
Feb08-0
Feb11-0, Feb11-6
Mar04-8
Mar07-7, Mar07-14
Feb11-0
Feb14-6, Feb14-0
Feb11-6
Feb14-0, Feb14-6
Feb05-5
Feb08-0, Feb08-5
Mar07-7
Mar10-14, Mar10-7
Mar01-8
Mar04-8, Mar04-14

Score
1.28E-15
2.56E-16
7.35E-17
6.49E-17
6.42E-17
3.73E-17
1.05E-18
1.60E-19
1.61E-20
1.20E-21[8] Radev, D., Otterbacher, J., Winkel, A., BlairGoldensohn, S.: NewsInEssence, Summarizing Online News Topics. Communications of the ACM, pp.
95–98 (2005)

Score
2.02E-21
9.30E-22
1.11E-22
1.22E-23
5.18E-24
3.26E-24
2.75E-24
1.90E-24
9.16E-25
7.16E-25[9] Sebastiani, F.: Machine Learning in Automated Text
Categorization. ACM Computing Surveys, 34(1), pp.
1–47 (2002)[10] Spiliopoulou, M., Ntoutsi, I., Theodoridis, Y., Schult,R.: MONIC – Modeling and Monitoring Cluster Transitions. In: Proc. of KDD Conference, pp. 706–711(2006)[11] Linguistic Data Consortium (LDC),
http://www.ldc.upenn.edu/[References]

Sophoin KHY[1] Adomavicius, G., Bockstedt, J.: C-TREND: Temporal Cluster Graphs for Identifying and Visualizing
Trends in Multiattribute Transactional Data. IEEE
Trans. on Know. and Data Eng. 20(6), 721–735 (June2008)

Sophoin Khy is a Ph.D student of Graduate School of Systems and Information Engineering, University of Tsukuba.
She received the M.Eng. degree from Master’s Program in
Sciences and Engineering, University of Tsukuba, in 2006.
Her research interests include text and web mining anddatabases. She is a student member of ACM SIGMOD
Japan and the Database Society of Japan.

[2] Allan, J. (ed.): Topic Detection and Tracking: Eventbased Information Organization. Kluwer, Boston(2002)

Yoshiharu ISHIKAWA

Yoshiharu Ishikawa is a Professor at Information Technology Center, Nagoya University. His research interests include spatio-temporal and document databases, data andweb mining, digital libraries, information retrieval and
Web information systems．He is a member of the Database
Society of Japan, IPSJ, IEICE, JSAI, ACM and IEEE Computer Society．

[3] Cutting, D., Karger, D.R., Pedersen, J.O., Tukey, J.W.:
Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections. In: Proc. of 15th
ACM SIGIR conference, pp. 318–329 (1992)[4] Ishikawa, Y., Hasegawa, M.: T-Scroll: Visualizing
Trends in a Time-series of Documents for Interactive
User Exploration. In: Proc. of the 11th ECDL Conference, pp. 235–246 (2007)

Hiroyuki KITAGAWA

Hiroyuki Kitagawa is a Professor at Graduate Schoolof Systems and Information Engineering, University ofTsukuba. His research interests include integration ofheterogeneous information sources, sensor databases andstreams, data mining, WWW and databases, XML andsemi-structured data, multimedia databases, and humaninterface. He is a member of ACM, IEEE Computer Society, the Database Society of Japan, IEICE, IPSJ, and
JSSST. He is now an IEICE Fellow, an IPSJ Fellow, anda Trustee of the Database Society of Japan.

[5] Khy, S., Ishikawa, Y., Kitagawa, H.: A Novelty-based
Clustering Method for On-line Documents. World
Wide Web Journal 11(1), 1–37 (March 2008)[6] Mei, Q., Zhai, C.: Discovering Evolutionary Theme
Patterns from Text - An Exploration of Temporal Text
Mining. In: Proc. of ACM KDD Conference, pp. 198–
207 (2005)[7] Nallapati, R., Feng, A., Peng, F., Allan, J.: Event
Threading within News Topic. In: Proc. of CIKM Conference, pp. 446–453 (2004)

6日本データベース学会論文誌 Vol.7, No.3
2008 年 12 月