Transcript No Slide Title

Army High Performance Computing Research Center
Prof. Shashi Shekhar
Computer
Science
Enabling
Technologies
for Scientific
Simulation
Visualization
Battlefield
Visualization
for
Training
Computational
Mechanics
Environment
Environmental
Contaminant
Remediation
Computational Sciences
& Engineering for Defense
Technology Applications
Materials
Processing
Materials
High Speed
Flow
Simulations
Fluids
Computational
Mechanics
& Simulation
Based Design
Prof. Shashi Shekhar
AHPCRC/Dept. of Computer Science, University of Minnesota
Research Interests
•
High Performance Geographic Information Systems (HPGIS)
•
Spatial Databases
•
Indexing, Clustering, Storage methods
•
Query Processing and Optimization
Maps
•
Terrain Visualization
Battlefield Events
Surveillance Data
Soldiers
Situation Assessment
HPGIS
Battlefield Simulation
Maps are as important to soldiers as guns
Soldiers
Surveillance Data
HPGIS
Battlefield Events
Maps
Situation Assessment
Battlefield Simulation
Example Usage of Geographic Info. Systems (GIS) in Battlefield :
•Rescue of pilots after their planes went down (recently in Kosovo)
•Precision targeting e.g. avoid accidental bombing of friendly embassies
•Logistics of Troop movements, avoid friendly fires
GIS Analysis by Army
• Tactical: (1) Navigate in unfamiliar terrain, (2) Avoid friendly fire, (3)
Given recent firing patterns, locate hidden enemy units.
• Operational: (1) Corridor Analysis: Identify sequence of land parcels
suitable for troop movement for given unit size and vehicle types ? (2)
Simulate enemy terrain for training in a flight simulator.
• Strategic: Which Army Base locations are most critical given strategic
interests, local demographic/political conditions ?
Parallelizing Range Queries for Battlefield Simulation
•(1/30) second Response time constraint on Range Query
•Parallel processing necessary since best sequential computer cannot meet requirement
•Green rectangle = a range query, Polygon colors shows processor assignment
Set of
Polygons
Graphics
Engine
Display
2Hz.
Set of
Polygons
Local
Terrain
Database
8Km X 8Km
Bounding Box
30 Hz. View
Graphics
25 Km X 25 Km
Bounding Box
High
Performance GIS
Component
Remote
Terrain
Databases
Declustering and Load-Balancing Methods to Parallelize GIS
S. Shekhar, S. Ravada, V. Kumar (University of Minnesota), D. Chubb, G. Turner (US Army)
Research Objective: Meet the response time
constraint for real time battlefield terrain visualization
in flight simulator.
Methodology:
•Data-partitioning approach
•Evaluation on Cray T3D, SGI Challenge.
Results:
•Data replication needed for dynamic load-balancing,
as local processing is cheaper than data transfer
•Good de-clustering method needed for dynamic loadbalancing
Significance:
•A major improvement in capability of geographic
information systems for determining the subset of
terrain polygons within the view point (Range Query)
of a soldier in a flight simulator using real geographic
terrain data set.
Dividing a Map among 4 processors. Polygons within a
processor have common color
BattleField Assesment: A Database Querying Approach
S. Shekhar, X. Liu and S.Chawla(U. of M), Dr. J. Gurney, Dr. E. Klipple (ARL Adelphi)
Research Objective: Design of spatial
database query language for Battlefield
decision support system.
Methodology:
• Object model for directions. E.g., North,
Between, Left, 3 O’ Clock.
• Integrate directional data-types in
industry-standard query language (SQL)
and Spatial Library(OGIS).
Results:
• An algebra(value-domain, operators) for
direction objects.
• Integration of algebra in commercial
object-relational databases.
Significance:
A major step towards simple “natural
language” like query interface for
battlefield decision support systems.
Query: List the farm fields to the left of the lake which are
suitable for tank movement ?
SELECT F.name, F.extent
FROM FarmField F, Lake L,Viewer V
WHERE V.left (F.extent, L.extent)
AND L.name = ‘Beech Lake’ AND F.soil-firmness > 5;
Note: Left is a viewer-based “direction” predicate.
Orientation-based Direction Query Processing
• Classical Strategies
– Based on Range query strategy
• Limitations
– May lead to large unnecessary I/O and CPU cost
– Need to know world boundary and calculate the intersection of
boundary and direction region
– Post Filter step is needed even for MBR objects
• Our approach
– Open shape based strategy(OSS)
Open Shape based Strategy(OSS)
• Basic idea
– Model direction region as an open shape
– Use actual direction region as a filter
• Advantages
– Improve filtering efficiency by eliminating
false hits
– Reduce unnecessary I/O and CPU cost
– Eliminate post Filter step for MBR objects
– Do not need to have knowledge of world
boundary
• Experimental evaluations
– Consistently outperforms classical range
query strategy both in I/O and CPU.
Extension Period
• Open Shape Strategy for Directional Query processing
• Join Index Data Structure
• Spatial Data Mining
• Workshop: Battlefield Visualization and Real Time GIS.
Spatial Data Mining(SDM)
• Historical Example: London Asiatic Cholera(Griffith)
• Search of implicit, interesting patterns embedded in geo-spatial databases
– Reconnaissance
– Vector maps(NIMA, TEC)
– GPS
• Data Mining vs. Statistics: High utility local trends
• SDM vs. DM: Spatial Autocorrelation
Army Relevance of SDM
• A decision aid in establishing the next service center
– location, location, location
• Detection of lost ammunition dumps at civil war
battlegrounds (Dr. Radhakrishnan)
• Search for local trends in massive simulation data stored in
Army lab databases
• Army/DoD is one of the biggest landowners.
– pristine environment, home to endangered species
–
balance unique defense requirements(training and war games) with
environmental regulations
Spatial Data Mining: Case Study of location Prediction
Given:
1. Spatial Framework
S  {s1 ,...sn }
f Xk : S  R
2. Explanatory functions:
fY : S  {0,1}
3. A dependent function
4. A family  of function mappings:
R  ... R  {0,1}
Find: A function
fˆy  
Nest locations
Objective:maximize
classification_accuracy
Distance to open water
( fˆy , f y )
Constraints:
Spatial Autocorrelation exists
Vegetation durability
Water depth
SDM Evaluation: Changing Model
• Linear Regression y  X  
• Spatial Regression y  Wy  X  
• Spatial model is better
SDM Evaluation: Changing measure
New measure:
ADNP( A, P)   dist( Ak , Ak .nearest( P))
k
Accomplishments
• Scaleable parallel methods for GIS Querying for Battlefield Visualization
• A spatial data model for directions for querying battlefield information
• Spatial data mining: Predicting Locations Using Maps Similarity (PLUMS)
•An efficient indexing method, CCAM, for spatial graphs, e.g. Road Maps
Army Relevance and Collaborations
•Relevance: “Maps are as important to soldiers as guns” - unknown
•Joint Projects:
– High Performance GIS for Battlefield Simulation (ARL Adelphi)
– Spatial Querying for Battlefield Situation Assessment (ARL Adelphi)
•Joint Publications:
– w/ G. Turner (ARL Adelphi, MD) & D. Chubb (CECOM IEWD)
– IEEE Computer (December 1996)
– IEEE Transactions on Knowledge and Data Eng. (July-Aug. 1998)
– Three conference papers
•Visits, Other Collaborations
– GIS group, Waterways Experimentation Station (Army)
– Concept Analysis Agency, Topographic Eng. Center, ARL, Adelphi
• Workshop on Battlefield Visualization and Real Time GIS (4/2000)