Efficient Range Distribution Query for Visualizing Scientific Data

Visualization applications implicitly run queries on the data to re-trieve distributions and statistical measures derivable from distri-butions. Distribution based data summaries can substitute for the raw data to answer statistical queries of different kinds. However, frequent access to the raw data is no longer practical, if possible at all, for answering large number of queries on large-scale data. Our work addresses the issue by accelerating range distribution query, which returns the distribution of an axis-aligned query re-gion. Maintaining the interactivity of such query results is a chal-lenging task because the workload, which affects the response time, of such queries scales up with the data and the query size. In this paper, we present a framework for answering range distribution queries for any arbitrary region in near constant time, regardless of data and query size. We adapt an integral histogram based data structure to bound the workload which is a combination of compu-tation, I/O and communication cost. We propose two novel trans-formations of this data structure – a decomposition and a similarity-driven indexing – to reduce the huge storage cost associated with it. In addition to studying performance of query, we also demonstrate the benefits that our technique offers to visualization applications which directly or indirectly require distributions.