Spatial data arises in a variety of contexts, including Geographical Information Systems (GIS), scientific simulations, and medical applications. With growing size of spatial data, there is an increasing emphasis on efficiently parallelizing spatial join algorithms. In this paper, we show how existing parallel spatial join algorithms suffer from load imbalance problem. Next, we describe an effective approach for load balancing that is based on using bitmaps as a summary structure of the data. We also use bitmaps to speedup in-memory sequential processing. The specific algorithms we have developed are Bitmap Partitioning Spatial Join (BPSJ), where the main ideas is to perform effective load balancing using bitmaps, and In-memory Bitmap-based Spatial Join (IBSJ), which uses bitmaps for efficient spatial join filtering step. Both algorithms have been compared against existing methods. Parallel BPSJ algorithm outperforms parallel well-known PBSM method by an average of 6.1x while IBSJ has an average speed-up of 4.2 times over plane-sweep and 3.06 times over the R-tree method.

Neither the memory capacity, memory access speeds, nor disk bandwidths are increasing at the same rate as the computing power in current and upcoming parallel machines. This has led to considerable recent research on in-situ data analytics. However, many open questions remain on how to perform such analytics, especially in memory constrained systems. Building on our earlier work that demonstrated bitmap indices (bitmaps) can be a suitable summary structure for key (offline) analytics tasks, this paper develops an in-situ analysis approach that performs data reduction (such as time-steps selection) using just bitmaps, and subsequently, stores only the selected bitmaps for post-analysis. We construct compressed bitmaps on the fly, show that many kinds of in-situ analyses can be supported by bitmaps without requiring the original data (and thus reducing memory requirements for in-situ analysis), and instead of writing the original simulation output, we only write the selected bitmaps to the disks (reducing the I/O requirements). We also demonstrate that we are able to use bitmaps for key offline analysis steps. We extensively evaluate our method with different simulations and applications, and demonstrate the effectiveness of our approach.

Approximate aggregation has been a popular approach for interactive data analysis and decision making, especially on large-scale datasets. While there is clearly a need to apply this approach for scientific datasets comprising massive arrays, existing algorithms have largely been developed for relational data, and cannot handle both dimension-based and value-based predicates efficiently while maintaining accuracy. In this paper, we present a novel approach for approximate aggregations over array data, using bitmap indices or bitvectors as the summary structure, as they preserve both spatial and value distribution of the data. We develop approximate aggregation algorithms using only the bitvectors and certain additional pre-aggregation statistics (equivalent to a 1-dimensional histogram) that we require. Another key development is choosing a binning strategy that can improve aggregation accuracy -- we introduce a v-optimized binning strategy and its weighted extension, and present a bitmap construction algorithm with such binning. We compare our method with other existing methods including sampling and multi-dimensional histograms, as well as the use of other binning strategies with bitmaps. We demonstrate both high accuracy and efficiency of our approach. Specifically, we show that in most cases, our method is more accurate than other methods by at least one order of magnitude. Despite achieving much higher accuracy, our method can require significantly less storage than multi-dimensional histograms.

With growing computational capabilities of parallel machines, scientific simulations are being performed at finer spatial and temporal scales, leading to a data explosion. Careful analysis of this data holds much promise for future scientific discoveries. Particularly, correlation analysis, which focuses on studying the potential relationships among multiple variables, is becoming a useful method for scientific analysis. This paper focuses on the problem of correlation analysis across large-scale simulation datasets, including 1) accelerating this analysis with the use of bitmap indexing as a representative summary of the data, 2) developing efficient algorithms for parallel execution, 3) performing analysis in distributed environments, i.e., for cases where different attributes are stored in geographically distributed repositories, and 4) combining sampling with correlation analysis. These algorithms have been implemented in a system that provides a high-level API for specification of the analyses, including allowing correlation analysis on specified value-based and dimension-based subsets of the data, and supports interactive and incremental analysis. We have extensively evaluated our framework for efficiency, and have also carried out case studies with domain scientists to establish how it can aid data-driven discovery process.

Scientific simulations are now being performed at finer temporal and spatial scales, leading to an explosion of the output data, and challenges in storing, managing, disseminating, analyzing, and visualizing these datasets. Tools commonly used today for disseminating and visualizing such data have inherent limitations, making it extremely hard to deal with larger datasets. We have developed a light-weight data management tool, which allows server-side sub setting and aggregation on scientific datasets stored in HDF5, one of the most popular scientific data formats. To support a variety of queries efficiently, our tool generates code for hyper slab selector and content-based filtering, and parallelizes selection and aggregation queries efficiently using novel algorithms. Additionally, our tool also supports certain most recent HDF5 features including dimension scale and compound data type. Through extensive evaluation, we show that our system is capable of efficiently supporting a variety of queries, scaling performance by parallelizing the queries, and reducing wide area data transfers through server-side data aggregation. We demonstrate that even for sub setting queries that are directly supported in OPeNDAP, a tool widely used by data dissemination portals, the sequential performance of our system is better.

In many science areas where datasets need to be transferred or shared, rapid growth in dataset size, coupled with much slower increases in wide area data transfer bandwidths, is making it extremely hard for scientists to analyze the data. This paper addresses the current limitations by developing SDQuery DSI, a GridFTP plug-in that supports flexible server-side data subsetting. An existing GridFTP server is able to dynamically load this tool to support new functionality. Different queries types (query over dimensions, coordinates and values) are supported by our tool. A number of optimizations, like parallel indexing, performance model for data subsetting, and parallel streaming are also applied. We compare our SDQuery DSI with GridFTP default File DSI in different network environments, and show that our method can achieve better efficiency in almost all cases.

While dissemination of scientific data is becoming crucial for facilitating scientific discoveries, a key challenge being faced by these efforts is that the dataset sizes continue to grow rapidly. Coupled with the fact that wide area data transfer bandwidths and disk retrieval speeds are growing at a much slower pace, it is becoming extremely hard for scientists to download, manage, and process scientific datasets. We have developed a light-weight data management tool, which allows server-side sub setting and aggregation on scientific datasets stored in a native format. While our approach is more general, this paper describes an implementation specific to NetCDF, which is one of the most popular scientific data formats. To support a variety of queries efficiently, our tool generates code for pre-filtering and post-filtering, and parallelize selection and aggregation queries efficiently using novel algorithms. We have extensively evaluated our implementation and compared its performance and functionality against Open DAP. We demonstrate that even for sub setting queries that are directly supported in Open DAP, the sequential performance of our system is better. In addition, our system is capable of supporting a larger variety of queries, scaling performance by parallelizing the queries, and reducing wide area data transfers through server-side data aggregation.

With increasing emphasis on analysis of large-scale scientific data, and with growing dataset sizes, a number of new challenges are arising. Particularly, novel data management solutions are needed, which can work together with the existing tools. This paper examines indexing support for supporting high-level queries (primarily those for sub setting) on array-based scientific datasets. This work is motivated by the limitations arising in visualizing climate datasets (stored in Net CDF), using tools like Para View. We have developed a new indexing strategy, which can help support a variety of sub setting queries over these datasets, including those requiring sub setting over dimensions/coordinates and those involving variable values. Our approach is based on bitmaps, but involves use of two-level indices and careful partitioning, based on query profiles. We also show how our indexing support can be used for sub setting operations executed in parallel. We compare our solutions against a number of other solutions, and demonstrate that our method is more effective.