Lawrence Berkeley National Laboratory

Scientific data analysis often requires mining large databases or data warehouses to find features in space. One important task is to find regions of interest such as stellar objects in astrophysics or flame fronts in combustion studies. Typically, this task is performed in two steps. The first step (searching) identifies records satisfying certain conditions specified by the user and outputs a set of cells. The second step (region-growing) groups these cells into connected regions. Most common approaches essentially perform a brute-force scan for these arching step. A number of indexing schemes have been proposed to speed up the searching step. Because they usually also slow down the region-growing step, these schemes have not reduced the overall time. In this article, we propose an approach based on compressed bitmap indices. Our approach speeds up not only the searching step, but also the region-growing step. In the literature, the time complexity of the region-growing step is demonstrated to be linear in the number of records in the dataset. In our tests, we show that the response time of our region-growing algorithm is linear in the number of records close to the surface of the regions of interest which is a small subset of all cells.