Advances in Indexing Scientific Data

The ability to extract information from collected data has always driven science. Today’s large computers and automated sensing technologies collect terabytes of data in a few weeks. Extracting information from such large amounts of data is like trying to find a needle in a haystack. This book proposes the use of bitmap indexes to efficiently solve this problem. Earlier solutions around bitmap indexes were either too slow or too large to answer large-range scientific queries, and did not provide a way to efficiently consolidate queried data points into meaningful objects. To solve these problems, we introduce multi-resolution, adaptive bitmap indexes in this book and a novel algorithm to consolidate points into objects of interest. Data is binned at multiple granularities, and indexes created for these bins giving a 10x performance gain compared to traditional bitmaps. Making these indexes adaptive reduces the size requirement, giving a 6x performance improvement over a regular bitmap index of the same size. The consolidation algorithm uses special properties of compressed bitmaps and scientific meshes to create objects in time sub linear in number of points retrieved.