Compiler and Runtime Support for Data Intensive Computing on Multi-Dimensional Data

The analysis and processing of large datasets that arise from simulations and from sensors plays an increasingly important role in many domains of scientific research. Typical examples of very large scientific datasets include long running simulations of time-dependent phenomena that periodically generate snapshots of their state (e.g., hydrodynamics and chemical transport simulation for estimating pollution impact on water bodies, magnetohydrodynamics simulation of planetary magnetospheres, simulation of a flame sweeping through a volume, airplane wake simulations), archives of raw and processed remote sensing data (e.g. AVHRR, Thematic Mapper, MODIS), and archives of medical images (e.g. high resolution light microscopy, CT imaging, MRI, sonography). These datasets are usually multi-dimensional. The data dimensions can be spatial coordinates, time, or varying experimental conditions such as temperature, velocity or magnetic field. The increasing importance of such datasets has been widely recognized.

In this project, we are developing techniques and middleware system support for 1) efficient storage and querying of multi-dimensional datasets on storage clusters, and 2) efficient processing of data on distributed storage and computation systems. Our approach is to develop policies that optimize computational efficiency for a broad range of computations carried out on multi-dimensional datasets. These policies need to take into account the spatial structure of a dataset, the partitioning of the dataset between storage units, and the computations to be performed. We implement these policies in middleware systems to support development of applications that consist of interacting components of data query and application specific processing operations. Some of the results from our research so far can be summarized as follows:

Support for partial data replication and data reordering to support data subsetting and data aggregation queries on distributed memory parallel machines. We developed a cost model and compiler and runtime optimizations for combined use of space partitioned and attribute partitioned replicas for executing data subsetting range queries. The algorithm allows uneven partitioning of replicas across storage nodes. Different replicas can be partitioned across different subsets of storage nodes. We investigated application of dynamic programming and greedy heuristics for determining the best set of replicas.

Support for application of XML data management support in scientific data analysis workflows. We have develop runtime support that aims to address issues associated with metadata management, data storage and management, and execution of data analysis workflows on distributed storage and computation platforms. Our framework couples a distributed, filter-stream based dataflow engine with a distributed XML-based data and metadata management system.

Support efficient data source abstractions that provide an object-relational view of data while hiding the details of storage and transport mechanisms and dataset layouts. In this abstraction, Basic Data Sources (BDS) interpret flat files as a set of records and are the building blocks of the view mechanism. Derived Data Sources (DDS) may be built on top of BDSs and provide more complex objects that serve the scientists' needs. The simplest DDS is one that supports a join based view over BDSs. We examined issues involving building such DDSs for scientific applications and consider distributed versions of the indexed join and the Grace Hash join algorithms.

A framework and techniques for efficient storage, retrieval, and processing of multi-resolution datasets on parallel and distributed disk-based storage clusters. We evaluated the techniques in the navigation and parallel visualization of Terabyte scale 3D biomedical image datasets. Support for efficient use of peer-to-peer storage systems to support efficient querying and subsetting of multi-dimensional datasets. We have developed several query scheduling strategies to improve query response times when multiple queries are submitted to the system. We have implemented these strategies in a prototype data server systems built on top of a peer-to-peer object storage system called Pond.

Project Researchers

Tahsin Kurc, Ph.D.

Project Publications