Division of Computational Informatics
Computational Intelligence Group
Hiroyuki Kitagawa
Center for Computational Sciences
Graduate School of Systems andInformation Engineering
2007/10/30

Computational Intelligence1Members
 Facultyz Hiroyuki Kitagawa (Professor)z Toshiyuki Amagasa (Assistant Professor)z Hideyuki Kawashima (Assistant Professor)(Joined CCS in February 2007)

 Postdoctoral Researchers
z Yousuke Watanabe (JST/CREST)z MoonBae Song (JSPS Postdoctoral Fellow)

 Studentsz Doctoral Program: 5z Master Program: 13z Undergraduate: 5z Research Student: 1
2007/10/30

Computational Intelligence2Overview
 Management and utilization of databases andlarge datasets
 R&D in data engineering and databases
 Main Research Areasz Meteorological Databases• GPV/JMA data archivez Information Integration• Integrated use of different types of information sources:
Databases, Web, Files, Sensors, …
z Data Mining and Knowledge Discovery• Extraction of useful information from databases and webz XML• XML: Standard format for data interoperability• XML data management and databases
2007/10/30

Computational Intelligence3Collaboration
Division of Global Environment
and Biological Sciences
Global Environmental Science Group

Division of Computational InformaticsComputational Media Group- Monthly Division
Meeting(ComputationalInformatics Seminar)- Real-world Sensing
Data Management- Development andMaintenance ofGPV/JMA DataArchive

Division of Computational Informatics
Computational Intelligence Group

2007/10/30

Computational Intelligence4

Research Areas
9 Meteorological Databasesz GPV/JMA data archive Information Integrationz Integrated use of different types of information

sources: Databases, Web, Files, Sensors, …
 Data Mining and Knowledge Discovery
z Extraction of useful information from databases

and web XMLz XML: Standard format for data interoperabilityz XML Data management and databases
2007/10/30

Computational Intelligence5GPV/JMA Data Archive
http://gpvjma.ccs.hpcc.jp

Developed and maintained in collaboration with Global
Environmental Science Group since Jan. 2005
2007/10/30

Computational Intelligence6GPV/JMA Data Archive Daily operational weather forecasting data (Grid

Points Values Data (GPV)) provided by the Japan
Meteorological Agency (JMA) For scientific development of weather and climate
forecasting technology

GSM:
Global Spectral Model
2007/10/30

RSM:
Regional Spectral Model

Computational Intelligence

MSM:
Meso-Scale nonhydrostatic Model

7

GPV/JMA Data Archive Weekly ensemble
 Monthly ensemble Seasonal ensemble

2007/10/30

Computational Intelligence8GPV/JMA Data Archive
Number of Registered Users

2007/10/30

Computational Intelligence9GPV/JMA Data Archive
Archived Data Size

2007/10/30

Computational Intelligence10Weather Maps on GoogleEarth GoogleEarthz Virtual globe programby Googlez Can show several kindsof images overlaid on
the surface of the earth KML (Keyhole Markup Language)z Tag-based file format

used to display
geographic data in anearth browser
T. Amagasa, H. Kitagawa and T. Komano, “Constructiong a Web Service
System for Large-scale Meteorological Grid Data,” IEEE Conf. on e-Scienceand Grid Computing, Dec. 2007.
2007/10/30

Computational Intelligence11Research Areas
9 Meteorological Databasesz GPV/JMA data archive

9 Information Integrationz Integrated use of different types of information

sources: Databases, Web, Files, Sensors, …
 Data Mining and Knowledge Discovery
z Extraction of useful information from databases

and web XMLz XML: Standard format for data interoperabilityz XML Data management and databases
2007/10/30

Computational Intelligence

12

Information Integration
 A huge number of online information sources
zDifferent data formats, access methods, query languages, …

 Information integration framework for datainteroperability
Information Intgration Framework
Wrapper
Wrapper

Wrapper
Wrapper

Wrapper
WrapperURL
keywords

Contents

mailaddress

Mediator
Mediator
Wrapper
Wrapper

PathFile

2007/10/30

Mailing-list
Mailing-list

Computational Intelligence

SQL

XML
Document

Relation

RDB
RDB

Web
Data
Data
Broadcast
Broadcast

Wrapper
Wrapper

XQueryXPathWeb
pages

mailWrapper
Wrapper

XMLDB

File
File SystemSystem

13

Information Integration
 StreamSpinnerz Integration frameworkfor heterogeneous
information sourcesz Can cope with streaming
data sources such assensors, location data,
streaming media, etc.
z SQL-like continuous
query languagez Distributed stream
processing and data
integration
StreamSpinner

2007/10/30

MASTER Sensor
SELECT *FROM Sensor[1sec]
WHERE Sensor.Temp >= 30

Application

Spinlet API
Query Analyzer
StreamArchiverConnector

Mediator
Wrapper

Wrapper

Sensors

CameraComputational Intelligence

Proxy
ModuleRDBMSStreamSpinnerStreamSpinner

Query result

Continuous query

StreamSpinnerStreamSpinner

14

Example 1: Simple Filtering
Notify when the temperature
value (ttxd11) exceeds 25℃

MASTER Sensor
SELECT timestamp, fsr
FROM Sensor[1]
WHERE Sensor.ttxd11 > 25
(ttxd11 expresses a valueof the temperature sensor)
Temperature
RPM…
2007/10/30

StreamSpinnertimestamp
timestamp ttxd11
ttxd11 ttxd12
ttxd12 tnhrpm
tnhrpm fsr
fsr
9867664…
9867664… 23.3
23.3 23.9
23.9 1234
1234 87.2
87.2
9867664…
9867664… 23.4
23.49867664…
9867664… 23.6
23.6

24.1
24.1 1234
1234 87.3
87.3
24.1
24.1 1235
1235 87.5
87.59867664…

24.4

Sensors monitor
behavior of aplant
Computational Intelligence

24.1

1244

Turbinestream87.8

Sensor streams
15

Example 2: Storing Stream Data
into Database
MASTER Sensor
INSERT INTO SensorDB VALUES (SELECT *FROM Sensor [now])
Store sensor data into adatabase when a new data itemarrives

System can meet various
insertion requirements•Store data directly•Store data after filtering•Store the average value

InserionrequestStreamSpinner

DBSensorDB
2007/10/30

Computational Intelligence

Sensor streams

16

Example 3: Integration of Streams
and Database
Function to compute
similarity of two arrays

MASTER Clock_1minute
SELECT dist(S1.v, S2.v)FROM( SELECT array(value) AS v FROM Turbine[60s]) AS S1,( SELECT array(value) AS v FROM TurbineDB) AS S2

similarity
DB
Historical sensor datastored in DB
2007/10/30

Computational Intelligence

Monitor similarity between
the recent pattern and thepast pattern in the database

Queryresult

StreamSpinnerStreamSpinner
Sensor

demo

10:02
10:01
28℃
10:0026℃30℃

17

Integration of Streams and Database
Location-based
information delivery

demo

StreamSpinner

Location

Exhibits inf.

StreamSpinner
CameraFace Rec.

Personnel inf.

Video stream monitoring
2007/10/30Computational Intelligence18

Research Areas
9 Meteorological Databasesz GPV/JMA data archive

9 Information Integrationz Integrated use of different types of information

sources: Databases, Web, Files, Sensors, …
9 Data Mining and Knowledge Discovery
z Extraction of useful information from databases

and web XMLz XML: Standard format for data interoperabilityz XML Data management and databases
2007/10/30

Computational Intelligence19Data Mining and Knowledge Discovery
 Outlier Detection
 Ratio Rule Mining
 Information Extraction from DocumentDatabases
 Novelty-based Document Clustering Topic Detection from Documents…

2007/10/30

Computational Intelligence20Outlier Detectionz Detecting outliers is an important problem withmany applications such as anomaly and otherinteresting event detection.
z Intuitively, an object is an “outlier” if it is in someway “significantly different” from other objects.

It is an outlier because thenumber of its neighbors isvery small compared withothers.
2007/10/30

Computational Intelligence21

Example-based Outlier Detectionfor High Dimensional Data
 Focusing on low dimensional projections todetect outliers in high dimensional datasets.
 Based on user supplied outlier examples.
Data：Abalone (UCI Machine Learning Repository) 4177 items

Outlier Examples in Subspace (A)2007/10/30

Outlier Examples in Subspace (B)Computational Intelligence

Detected Outliers in The Optimal Subspace22

Outlier Detection for Categorical Records
Detects anomaly records in which many attribute values are not observed
despite they should occur in association with other attribute values.
Association rules with high confidence

Animal Data

Each record presents
a habit of an individual animal
ID Egg Legs#Aquatic…

1

Yes

4

Yes…

2

Yes

4

Yes…

3Yes

4Yes…

4Yes

4Yes…

5Yes

0No…

Our method shows enough detection
accuracies in an accuracies evaluationcompared with the recent related work
[KDD07, Das] for network intrusion data.
2007/10/30

Computational Intelligence{ (Egg, Yes) }→{ (Legs#, 4) }{ (Egg, Yes) }→{ (Aquatic, Yes) }{ (Egg, Yes) }→{(Legs#, 4), (Aquatic, Yes) }Support ≧ 40%, Confidence ≧ 75%

Rule’s right hand itemset must have astrong association with the left hand
itemset.
Outlier degree of record tConsider an ideal form t+ of t including
all items which should observed in t.

t5+ = { (Egg, Yes), (Leg#, 0), (Aquatic, No),(Legs#, 4), (Aquatic, Yes) }| t+ −t | 2= = 0.4
od (t ) =+|t |523

Ratio Rule Miningrelationships) in numeric dataz Capture linear relationships
in the data

70

65

weight (kg) Extract Ratio Rules (linear(weight) = 0.6×(height) - 40

60

55

50

 Featuresz Can extract local linear relationships as well as
150

155

160
165
height (cm)

170

175

global onesz Introduce Support (population size relevant to therule) and Confidence (confidence degree of therule) to characterize each ratio rule

2007/10/30

Computational Intelligence24

Ratio Rule Mining
Example: Wine Data

Our Ratio Rules extract both two
linear relationships separately

Only strong correlation can be extracted
by setting appropriate parameters

Linear regression: only the global
linear relationship2007/10/30

Computational Intelligence25

Record Extraction from Document
Databases
Problem: Extract records fit for
user interests with highaccuracy and efficiency
Basic idea: Narrow the search
to documents which willcontain target information

SeedRecords

RecordExtraction
ModuleNew YorkIntel

Santa ClaraGoogle

Mtn. View…

…

Record extraction
from documents…amanager atIntel in
Santa Claradoing …

…

researchers
at IBM in
New York
have …

Document
database

User interest:
IT Company & Location

IBM

Document
database
Relevance
Evaluation
Y
Y
N…

…
Document
Selection
ModuleExtracted Records

Documents which are more likely
to contain the target inf.

Sort records by their confidence
Append2007/10/30

Computational Intelligence26

Research Areas
9 Meteorological Databasesz GPV/JMA data archive9 Information Integrationz Integrated use of different types of information

sources: Databases, Web, Files, Sensors, …
9 Data Mining and Knowledge Discovery
z Extraction of useful information from databases

and web
9 XML
z XML: Standard format for data interoperabilityz XML Data management and databases
2007/10/30

Computational Intelligence27

Processing XML data in PC cluster systems
Background• XML data processing is not cheapÎParallel XML processing tocope with growing XML data volume
Approach• Path‐based partitioning of XML data
– Cost estimation for XPath queries– Using GA to compute optimal
partitions and allocation based on
workload information

Results• Nearly optimal partitioning andallocation of XML fragments• Good scalability for XML data size[sec] 120
10080

1台
5台
10台

60
40
200110MB

2007/10/30

Computational Intelligence

2100MB

31GB28

Storage and retrieval of XML in P2P
Approach
Motivation• Based on DHT• Overlay network (P2P)• Separate DHTs for XML contenxts andInfrastructure for sharing information
structures
among distant / different organizations
Contents (C‐DHT)Î Efficient XML query processing
Structure (S‐DHT)
over P2P network
Results• Prototype system implementation• Good query performance comparedwith an existing method

2007/10/30

Computational Intelligence29

Analytical processing of XML (XML OLAP)
Approach
Motivation• In‐depth analysis on large volume of XML • Definition of facts/dimensions in XMLdata• Definition of XML datacube– Decision making• Mapping XML datacube to RDBMS– Detailed analysis of scientific
Making use of relational storage
dataResultsÎInteractive analysis of XML data
• Prototype system implementation(XML OLAP)• Performance evaluation

Time (ms)

10,000.000

1,000.000

100.000

10.00010MB

rollup(payment)

2007/10/30

Computational Intelligence

100MB

200MB 300MBFile size

rollup(region)

400MB

500MBrollup(regionpay)

30

Funds Grant-in-Aid for Scientific Research from

Ministry of Education, Culture, Sports, Scienceand Technology (~$0.6 million; past 3 years)z Grant-in-Aid for Scientific Research A
z Grant-in-Aid for Scientific Research on Priority

Areas (Infoplosion Project)z Grant-in-Aid for Exploratory Researchz Grant-in-Aid for Young Scientists
 JST CREST Project (in collaboration with OSgroup) (~$0.3 million; past 3 years)
 From industry
2007/10/30

Computational Intelligence31

Publication and Awards
 Refereed Papers
z 2004: 17 (Journal 10, Conference 7)
z 2005: 14 (Journal 7, Conference 7)
z 2006: 18 (Journal 7, Conference 11)
z 2007: 20 (Journal 9, Conference 11) (As of August 2007)

 Awardsz 2 Best Paper Awards (DBSJ, IEICE)z Young Researchers’ Award (DBSJ)z 2 Achievement Awards (IPSJ Fellow, IEICEFellow)
z 15 Students’ Awards

2007/10/30

Computational Intelligence32

Future Plan Research and development of technologies

for data engineering infrastructure Scientific databasesz Collaboration with Global Environmental ScienceGroupz Other datasets, data mining, …
 Reinforcement of collaboration with othergroups and divisions to tackle new researchissues in data engineering

2007/10/30

Computational Intelligence33

Thank you.

2007/10/30

Computational Intelligence34