The database and the information retrieval communities have been working on separate sets of techniques for querying structured data and text data, but there is a growing need to handle these types of data together. In this paper, we present a strategy to efficiently answer joint queries on both types of data. By using an efficient compression algorithm, our compressed bitmap indexes, called FastBit, are compact even when they contain millions of bitmaps. Therefore FastBit can be applied effectively on hundreds of thousands of terms over millions of documents. Bitmap indexes are designed to take advantage of data that only grows but does not change over time (append-only data), and thus are just as effective with append-only text archives. In a performance comparison against a commonly used database system with a full-text index, MySQL, we demonstrate that our indexes answer queries 50 times faster on average. Furthermore, we demonstrate that integrating FastBit with a open source database system, called MonetDB, yields similar performance gains. Since the integrated MonetDB/FastBit system provides the full SQL functionality, the overhead of supporting SQL is not the main reason for the observed performance differences. Therefore, using FastBit in other database systems can offer similar performance advantages.

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.

This paper presents a systematic study of two large subsets of bitmap indexing methods that use multi-component and multi-level encodings. Earlier studies on bitmap indexes are either empirical or for uncompressed versions only. Since most of bitmap indexes in use are compressed, we set out to study the performance characteristics of these compressed indexes. To make the analyses manageable, we choose to use a particularly simple, but efficient, compression method called the Word-Aligned Hybrid (WAH) code. Using this compression method, a number of bitmap indexes are shown to be optimal because their worst-case time complexities for answering a query is a linear function of the number of hits. Since compressed bitmap indexes behave drastically different from uncompressed ones, our analyses also lead to a number of new methods that are much more efficient than commonly used ones. As a validation for the analyses, we implement a number of the best methods and measure their performance against well-known indexes. The fastest new methods are predicted and observed to be 5 to 10 times faster than well-known indexing methods.

Bitmap indices have been widely used in scientific applications and commercial systems for processing complex, multi-dimensional queries where traditional tree-based indices would not work efficiently. A common approach for reducing the size of a bitmap index for high cardinality attributes is to group ranges of values of an attribute into bins and then build a bitmap for each bin rather than a bitmap for each value of the attribute. Binning reduces storage costs, however, results of queries based on bins often require additional filtering for discarding \it false positives, i.e., records in the result that do not satisfy the query constraints. This additional filtering, also known as "candidate checking," requires access to the base data on disk and involves significant I/O costs. This paper studies strategies for minimizing the I/O costs for "candidate checking" for multi-dimensional queries. This is done by determining the number of bins allocated for each dimension and then placing bin boundaries in optimal locations. Our algorithms use knowledge of data distribution and query workload. We derive several analytical results concerning optimal bin allocation for a probabilistic query model. Our experimental evaluation with real life data shows an average I/O cost improvement of at least a factor of 10 for multi-dimensional queries on datasets from two different applications. Our experiments also indicate that the speedup increases with the number of query dimensions.

Bitmap indexing is a common technique for indexing high-dimensional data in data warehouses and scientific applications. Though efficient for low-cardinality attributes, query processing can be rather costly for high-cardinality attributes due to the large storage requirements for the bitmap indices. Binning is a common technique for reducing storage costs of bitmap indices. This technique partitions the attribute values into a number of ranges, called bins, and uses bitmap vectors to represent bins (attribute ranges) rather than distinct values. Although binning may reduce storage costs, it may increase the access costs of queries that do not fall on exact bin boundaries (edge bins). For this kind of queries the original data values associated with edge bins must be accessed, in order to check them against the query constraints.In this paper we study the problem of finding optimal locations for the bin boundaries in order to minimize these access costs subject to storage constraints. We propose a dynamic programming algorithm for optimal partitioning of attribute values into bins that takes into account query access patterns as well as data distribution statistics. Mathematical analysis and experiments on real life data sets show that the optimal partitioning achieved by this algorithm can lead to a significant improvement in the access costs of bitmap indexing systems for high-cardinality attributes.

In this paper, we propose a new strategy for optimizing the placement of bin boundaries to minimize the cost of query evaluation using bitmap indices with binning. For attributes with a large number of distinct values, often the most efficient index scheme is a bitmap index with binning. However, this type of index may not be able to fully resolve some user queries. To fully resolve these queries, one has to access parts of the original data to check whether certain candidate records actually satisfy the specified conditions. We call this procedure the candidate check, which usually dominates the total query processing time. Given a set of user queries, we seek to minimize the total time required to answer the queries by optimally placing the bin boundaries. We show that our dynamic programming based algorithm can efficiently determine the bin boundaries. We verify our analysis with some real user queries from the Sloan Digital Sky Survey. For queries that require significant amount of time to perform candidate check, using our optimal bin boundaries reduces the candidate check time by a factor of 2 and the total query processing time by 40 percent.

Over the last few years various scientific experiments and Grid projects have developed different catalogs for keeping track of their data files. Some projects use specialized file catalogs, others use distributed replica catalogs to reference files at different locations. Due to this diversity of catalogs, it is very hard to manage files across Grid projects, or to replace one catalog with another. In this paper we introduce a new Grid service called the Replica Registration Service (RRS). It can be thought of as an abstraction of the concepts for registering files and their replicas. In addition to traditional single file registration operations, the RRS supports collective file registration requests and keeps persistent registration queues. This approach is of particular importance for large-scale usage where thousands of files are copied and registered. Moreover, the RRS supports a set of error directives that are triggered in case of registration failures. Our goal is to provide a single uniform interface for various file catalogs to support the registration of files across multiple Grid projects, and to make Grid clients oblivious to the specific catalog used.

Bitmap indices have been widely used in scientific applications and commercial systems for processing complex, multi-dimensional queries where traditional tree-based indices would not work efficiently. This paper studies strategies for minimizing the access costs for processing multi-dimensional queries using bitmap indices with binning. Innovative features of our algorithm include (a) optimally placing the bin boundaries and (b) dynamically reordering the evaluation of the query terms. In addition, we derive several analytical results concerning optimal bin allocation for a probabilistic query model. Our experimental evaluation with real life data shows an average I/O cost improvement of at least a factor of 10 for multi-dimensional queries on datasets from two different applications. Our experiments also indicate that the speedup increases with the number of query dimensions.