# Presentation: 211951

## Data Reduction TechniquesUsing Subsampling

- Data Reduction TechniquesUsing Subsampling

**Lori A. Freitag**
**Raymond M. Loy**

***Mathematics and Computer Science Division***
***Argonne National Laboratory***

## Motivation

- Scientists often have access to remote MPP resources for computation
- Generate giga- and terabyte data sets
- Resource limitations make analysis via interactive visualization difficult
- network bandwidth
- local storage capacity
- high-end graphics workstations limited to 2563 points

- Compute

- Desktop

- Storage

- OC3-OC12
-   (maybe)

## Remote Visualization Paradigms

- Goal:  to provide interactive analysis capabilities of large data sets on limited local resources by utilizing remote resources and high speed networks
- Three primary techniques
- Image-based rendering
- Parallel visualization servers
- Subsampling and clustering techniques
- Uniform
- Multi-resolution

- Raw Data

- Derived
- Entities

- Rendering

- Images

- Display

- Filtering and Mapping

## Image-Based Rendering

- Technique:  use two or more reference images from multiple viewpoints to reconstruct the geometry or new images as viewpoint changes
- Example: Image warping [Chang, et. al. 1999, Mark, 1999]
- use color, depth, and surface normal information to “warp” input images to desired output
- Advantages:
- data transferred is independent of scene complexity or original data set size
- fixed local computation and communication costs
- no approximation errors in the reference images
- Disadvantages:
- reconstructed geometry or viewpoint can contain errors
- reconstruction moderately expensive (1.5 frames/sec using four reference images [Chang et.al., 1999]

## Parallel Visualization Server

- Technique: filter and map the full data set using remote MPP resources to create derived visualization entities (e.g., isosurfaces, cutting planes, streamlines)
- Examples: post-processing step [Crockett, 1996, Hanson and Hinker 1992] or as computation proceeds [Haimes, 1994, Vaziri and Kremenetsky, 1995]
- Advantages:
- Derived visualization entities have no approximation or reconstruction errors
- Disadvantages:
- Size of transmitted data grows as problem size grows
- Less reduction if using 3D visualization techniques

## Subsampling and Clustering

**Technique:** to create a smaller, full-dimensional data set by sampling the original data set at specified locations or averaging clusters of points
**Examples**:
- Uniform grid subsampling (very common)
- Multi-resolution subsampling using quad- or octrees [Lindstrom, et. al. 1996, LaMar, et. al. 1999] wavelets [Roerdink and Westenberg, 1998], progressive meshes [Hoppe, 1996]
**Advantages:**
- useful for fast local exploration of reduced data set
- remote computation and data transfer time fixed
**Disadvantages:**
- approximation errors in the subsampled data
- exacerbated as the original problem size increases
- mitigated by the use of windowing approaches
- nonconforming meshes in multi-resolution techniques can lead to difficulties with standard visualization algorithms

## Subsampling Techniques

- Data Insertion
- Based on spatial coordinates
- Simple API that assumes only a point cloud
- Data Agglomeration
- Simple average of data collected in each leaf octant
- Average values at parent octants not currently computed or stored
- Error indication
- Gives an indication of fidelity of reduced data set to original data set
- Leaf Cells
- standard deviation ***n**  *normalized by mean
- maximum deviation  *e**n** *normalized by mean
- Global values over all leaves
- Maximum ***n* , *e**n*
- Average ***n* , *e**n*

## Uniform Subsampling

- Total number of desired grid points specified
- 3D block partitioning strategy decomposes geometry into a uniform grid
- Data inserted and averages computed
- Empty cells filled by computing the average of the neighboring cells
- Average values and error values sent to processor zero which publishes the origin, spacing, dimensions, and reduced data set

## Multiresolution Subsampling

- Octree Data Structure
- Leaf octant subdivision
- Criteria
- Number of points per octant
- Deviation from average value
- User-specified error function
- Minimize error for a given performance criteria

- *

- *

- *

**N**

**LR**

- Leaf octants subdivided when error > criteria
- Leaf octants pruned when siblings collectively contain an error < criteria

-    Interactive adaptive changes
-   New error bounds requested and applied globally or locally
-  Octree is refined and pruned as needed

## Parallel Octree Data Structures

- Parent/Child links are either local or non local
- Off-processor parents maintained in a “Local Root” list which allows local octree traversal without communication
- Partitioning via a space filling curve
- Load balancing via arbitrary octant migration supported by AUTOPACK

## Visualization Performance Constraints

- User specifies desired size of reduced data set, NR
- System automatically determines the error threshold needed to generate NR octants
- If desired NR is greater than actual NR – refine
- If desired NR is smaller than actual NR – coarsen
- Histogram used to determine candidate octants for refinement/coarsening
- Given a new error threshold, histogram analysis used to predict how many octants will be added/removed
- Perform the operation and compare with predicted results
- Repeat recursively until desired result is obtained

## Our Approach - The Big Picture

**Visualization Tools**

- GMV
- vtk toolkits*
*IRIS Explorer**
*IDL*
- CAVE VR*

**Application**

**Data Reduction**

**File Input**

- Batch Mode Post Processing

*Interactive Request for New Data Sets*

- Tet meshes
- Quad Meshes
- Hex Meshes

**File Output**

**Interactivity**

- New Reduced Data Sets
*Application Monitoring*
*Application Steering*

*Computational Steering*

- 1

- 1

- 2

- 3

- 4

## Visualization Tools

- Criteria:
- Must support unstructured/multi-resolution data sets
- Primarily interested in freely-available, open source desktop tools

- Currently support three environments
- GMV (LANL)
- custom vtk desktop toolkit (interactive)
- custom CAVE immersive environment (interactive)
- vtk toolkit
- Graphics techniques: isosurfaces, cutting planes, vector glyphs, surface and mesh visualization
- Java Swing GUI

## Subsampling Communication Model

- Data Reduction

- Visualization

-  Publish control/parameter variables
-  Publish reduced data set
-  Publish “new request” toggle variable

-  Access control/parameter variables
-  Access and visualize reduced data     set
-  Modify parameter variables
-  Request new reduced data set via toggle variable

-  Take write access of data values
-  Update data values
-  Release and publish new data
-  Reset toggle variable

-  Check toggle variable

- Time

-  When toggle variable reset, access and visualize new data data
-  Modify parameter variables
-  Request new reduced data set via toggle variable

## Examples

- Rayleigh Taylor Instabilities
- 2D, 5.3 • 104 data points
- Characterized by a contact discontinuity (lower dimensional entity)
- Hairpin Vortices
- 3D, 2.05 • 106 data points
- Scalar field of interest describes fully 3D features
- X-Ray burst
- 2D, 2.7 • 106 data points
- Characterized by the interface between two fluids
- All results run on an 250 MHz R10000 SGI Origin

## Windowing in Multiresolution SubsamplingX-Ray Burst

- Criteria: Min ***n** *
- using 5000 octants

- Criteria: 12.5% Error in window
- 18,959 Octants

- Error for 18,959 Octants

- 2.7 million points

## Comparison of Subsampling Techniques

-     Rayleigh-Taylor and Hairpin vortex data sets achieve same average error with a factor of 5 and 10 fewer grid points using multi-resolution subsampling, respectively

- 34798 points
-  = 3.14

- 34725 points
-  = 1.46

- 15616 points
-  = .0347

- 4102 points
-  = .0339

***What are the problem regimes/characteristics for which each subsampling strategy is most cost effective?  ***

## Performance Models

**Visualization Task:** Isosurface Generation
- Commonly used
- Lower-dimensional entity
- Mature techniques for both structured and unstructured meshes
**Costs Modeled**
- Isosurface generation time
- Data transfer time over a WAN
- Data reduction time for subsampling
**Assumptions/Simplifications**
- Remote algorithms are performed on a parallel computer and are scalable
- Original computational mesh is unstructured
- Data compression algorithms for data transfer not considered
- Advanced decimation routines for isosurface generation not considered

-    **Costs Not**** ****Modeled**
-    Time to read and distribute data
-    Time to load and process data             	on local graphics machine

## Parameters and Model Variables

- Hardware Characteristics
- P: number of processors on remote MPP
- R: WAN bandwidth (Mbs) (Use R=10Mbs as base case, vBNS web page)
- L: WAN latency (s) (Use L=20ms as base case, vBNS web page)
- Task Complexity
- N: number of data elements
- I: number of isosurfaces
- NR: number of data elements in subsampled data sets
- NC: number of cells containing an isosurface contour
- System-dependent Computational Costs
- CRU, CRM: Subsampling cost (uniform and multi-resolution)
- CRU, CRM: Isosurface generation cost (uniform, octree, general)

## Uniform Subsampling Model

- M3 = CRU/P + CIUI+ 32•(9+2NR) /106R + 2L

- Isosurface Generation
- Uniform Reduced Mesh
- I isosurfaces

- Data Transfer
- 32 bit floats/ints
- 9 floats for origin, spacing,
-   problem size
- 2NR floats for data and error

- Latency
-  Reduced
-    data set

- Data Reduction
- Uniform Subsampling
- Parallel

## Multi-resolution Subsampling Model

- M3 = CRM/P + CIOI+ 32•(22NR) /106R + 2L

- Isosurface Generation
- Octree Reduced Mesh
- I isosurfaces

- Data Transfer
- 32 bit floats/ints
- 4NR vertices
- 3 floats/vertex for coord
- 8NR ints for connectivity
- 2NR floats for data and error

- Latency
-  Reduced
-    data set

- Data Reduction
- Multi-resolution Subsampling
- Parallel

## Isosurface Cost Parameters

- In general,
- CI = A N + B NC
-     where A gives cost to visit each cell, B gives additional cost to contour
- Timed *vtkContourMarchingFilter* for a uniform grid, changing only the way it’s represented in vtk data structures
- uses vtk patented routine for structured points
- modified to provide an efficient, octree specific routine
- LSA for N=103, 203, 303, 403, 503, 603

## Subsampling Cost ParameterUniform Subsampling

- Single processor performance of parallel code
- N = 503, 753, 1003, 1253
- NR = 1, 53, 103, 203 , 303
- For NR = 1
- For NR > 1, variance is less than 5%
- LSA yields CRU = (1.274e-5 + 1.553e-13N) N

## Subsampling Cost ParameterMulti-resolution Subsampling

- Single processor
- N as before, NR varies
- For NR =1,  CRM = CRU
- For NR>1, cost increases
- octant cell division, data sorting, reassignment
- function of both N and NR
- LSA yields
- CRM = CRU + .1410 + 2.35e-6N + 1.36e-4NR+6.19e-11N NR

## Total Expected Runtime

- Small values of R can significantly affect run time
- Most dramatic increase in time results from an increase in N
- For MR, increasing I and NC have minimal effect but increasing NR is dramatic due to increased subsampling and isosurface generation costs
- For Uniform grid, increasing I and NC significantly impact performance due to increased isosurface generation costs

## Relative Performance

- Plot the ratio of the multi-resolution subsampling  NRM to uniform subsampling NRU
- As NC increases, NRM approaches NRU
- As N increases, multi-resolution subsampling is less cost effective
- Must examine the error reduction achieved with a given percentage of NR for each technique to obtain the effective cost

- NC=N2/3

- NC=3N2/3

- NC=5N2/3

## How do our test cases fare?

- Well, there is no clear winner...
- In all cases, the same approximation error is achieved with far fewer multiresolution grid points
- R-T problem – factor of 5 (tie)
- X-Ray burst – factor of 2-3 (uniform better)
- Hairpin Vortex – factor of 10 (MR better)
- Will investigate more 3D problems to determine if hairpin vortex case is typical
- Note that adaptivity and windowing functionalities may increase MR attractiveness

## Future Work

- Functional representations on leaf octants rather than simple averages
- Better representation of the underlying data set
- Useful for feature extraction, compression, data differencing, time-dependent data
- Can be used with any approximation technique
- Novel architectures for fast decompression schemes
- Real time steering and visualization algorithms