# Presentation: 832825

## Document Clustering on Supercomputers

- Yu (Cathy) Jiao, Ph.D.
**Applied Software Engineering Research Group**
**Computational Sciences and Engineering Division**

## National challenge

**Data**

**Binary**

**Text**

**Image**

**Multimedia**

**Sensors**

**One small**
**step for man**

**11010010**

- 1970

- 1980

- 1990

- 2000

- 2010

**Data are everywhere**
**Sources are unreliable**
**Data are difficult to merge **
**Merging cannot be ****done manually**

**?**

## Key technologies

- Intelligent agents** **
**Peer-to-peer communication**
**Encapsulated messages**
**Computation distribution**
**Adaptive and collaborative behavior**
**Fault tolerance**

- High-performance computing
**Red/White Oak clusters**
**135 Dell computers**
**Largest cluster computer at ORNL**
**1.7 Tflops**
**270 GB memory **
**11.3 TB disk**

## What is in there?
Are there any threats?
What am I missing?

**What is in there?**
**Are there any threats?**
**What am I missing?**

**Paper**
**records**

**Old **
**disks**

**Legacy databases**

- What to do with this?

## How ORNL can help

**Raw documents**

**Organize the**
**information**

**What are the connections? **

**Connect the information**

**What are ****they planning?**

- Take action

**What do we have?**

**Find the threats**

**How credible is the threat?**

## The technical problem

|  | Doc 1 | Doc 2 | Doc 3 |
| --- | --- | --- | --- |
| Army | 1 | 0 | 0 |
| Sensor | 1 | 1 | 1 |
| Technology | 1 | 1 | 0 |
| Help | 1 | 0 | 0 |
| Find | 1 | 0 | 0 |
| Improvise | 1 | 0 | 0 |
| Explosive | 1 | 0 | 1 |
| Device | 1 | 0 | 1 |
| ORNL | 0 | 1 | 0 |
| Develop | 0 | 1 | 1 |
| Homeland | 0 | 1 | 1 |
| Defense | 0 | 1 | 1 |
| Mitre | 0 | 0 | 1 |
| Won | 0 | 0 | 1 |
| Contract | 0 | 0 | 1 |

- Vector Space Model
**10,000 documents 100 terms**
**1 second**

- Similarity Matrix
**10,000 documents **
**1.6 Minutes**

**Words to documents**

**Documents to documents**

- Cluster Analysis

**Most similar documents**

*O(n**2* log *n*)

|  | Doc 1 | Doc 2 | Doc 3 |
| --- | --- | --- | --- |
| Doc 1 | 100% | 17% | 21% |
| Doc 2 |  | 100% | 36% |
| Doc 3 |  |  | 100% |

**D1**

**D2**

**D3**

- Powerful but expensive

## Breakthrough—inverse corpus frequency

- Reed et al., “_Multi-Agent System for Distributed Cluster Analysis_,” *Third International Workshop on Software Engineering for Large-Scale Multi-Agent Systems (SELMAS'04),* May 24 – 25, 2004, Edinburgh, Scotland.

**We analyzed nearly ****1 million documents from six major ****research corpora**
**We found 229,023 unique terms (a large dictionary contains around 70,000 terms)**
**We use this term frequency distribution as our “global” ****term frequency**

- Look at the forest, not the trees

## Distributed clustering

- Reed et. al., “_An Agent-based Method for Distributed Clustering of Textual Information_,” patent pending, licensed to industry

- Head Node

- Computer 4

- Computer 5

- Computer 6

- Computer 7

- Computer 8

- Computer 9

- Computer 10

- Computer 11

- Computer 1

- Computer 2

- Computer 3

- Black Board

## Breakthrough – bio-inspired distributed solution 

**Ant colony optimization**

**Bird flocking model**

- Breakthrough – bio-inspired distributed solution

- Alignment

- Separation

- Cohesion

## Summary

**Current technology **cannot solve** emerging national challenges.**
**Intelligent software agents are a **significant breakthrough** technology.**
**Results indicate ****high potentia**l** to help solve these national challenges.**
**We have a progression of significantly successfully deployed agent systems and research to our credit.**

## Contact

- Yu (Cathy) Jiao, Ph.D.
- Applied Software Engineering Research Group
- Computational Sciences and Engineering Division
- (865) 574-0647
- jiaoy@ornl.gov

-    Yu_Potok_Clustering_0611