FastBit: interactively searching massive data
Journal of Physics Conference SeriesPublished 1 July 2009Open access
Kesheng Wu, Sean Ahern, E. Wes Bethel, Jiabei Chen, Hank Childs, E. Cormier‐Michel
Citations144
SJR score0.19
SNIP0.31
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A summary of the key underlying technologies, namely bitmap compression, encoding, and binning, that enable FastBit to answer structured (SQL) queries orders of magnitude faster than popular database systems are presented.
Abstract
As scientific instruments and computer simulations produce more and more data, the task of locating the essential information to gain insight becomes increasingly difficult. FastBit is an efficient software tool to address this challenge. In this article, we present a summary of the key underlying technologies, namely bitmap compression, encoding, and binning. Together these techniques enable FastBit to answer structured (SQL) queries orders of magnitude faster than popular database systems. To illustrate how FastBit is used in applications, we present three examples involving a high-energy physics experiment, a combustion simulation, and an accelerator simulation. In each case, FastBit significantly reduces the response time and enables interactive exploration on terabytes of data.
Keywords
Computer ScienceDecision Sciences
Communications of the ACMMapReduce
18,538 Citations2008Jay B. Dean, Sanjay Ghemawat
This presentation explains how the underlying runtime system automatically parallelizes the computation across large-scale clusters of machines, handles machine failures, and schedules inter-machine communication to make efficient use of the network and disks.
Computer Networks and ISDN SystemsThe anatomy of a large-scale hypertextual Web search engine
15,828 Citations1998Sergey Brin, Lawrence M. Page
This paper provides an in-depth description of Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext and looks at the problem of how to effectively deal with uncontrolled hypertext collections where anyone can publish anything they want.
ACM SIGMOD RecordAn overview of data warehousing and OLAP technology
2,404 Citations1997Surajit Chaudhuri, Umeshwar Dayal
An overview of data warehousing and OLAP technologies, with an emphasis on their new requirements, is provided, based on a tutorial presented at the VLDB Conference, 1996.
NatureHigh-quality electron beams from a laser wakefield accelerator using plasma-channel guiding
1,973 Citations2004C. G. R. Geddes, Csaba Tóth +7 more
A laser accelerator that produces electron beams with an energy spread of a few per cent, low emittance and increased energy (more than 109 electrons above 80 MeV) and opens the way for compact and tunable high-brightness sources of electrons and radiation.
ACM Computing SurveysUbiquitous B-Tree
1,826 Citations1979Douglas E. Comer
The major variations of the B-tree are discussed, especially the B+-tree, contrasting the merits and costs of each implementation and illustrating a general purpose access method that uses a B- tree.
ACM Computing SurveysInverted files for text search engines
1,077 Citations2006Justin Zobel, Alistair Moffat
This tutorial introduces the key techniques in the area of text indexing, describing both a core implementation and how the core can be enhanced through a range of extensions.
Computational Science & DiscoveryTerascale direct numerical simulations of turbulent combustion using S3D
562 Citations2009J. H. Chen, Alok Choudhary +11 more
Recent results from terascale DNS of turbulent flames are presented, illustrating its role in elucidating flame stabilization mechanisms in a lifted turbulent hydrogen/air jet flame in a hot air coflow, and the flame structure of a fuel-lean turbulent premixed jet flame.
Improved query performance with variant indexes
482 Citations1997Patrick E. O׳Neil, Dallan Quass
A new method whereby multi-dimensional group-by queries, reminiscent of OLAP/Datacube queries but with more flexibility, can be very efficiently performed is introduced.
Bitmap index design and evaluation
349 Citations1998Chee-Yong Chan, Yannis Ioannidis
A general framework to study the design space of bitmap indexes for selection queries and examine the disk-space and time characteristics that the various alternative index choices offer, and describes a bitmap-index-based evaluation algorithm that represents an improvement over earlier proposals.
ACM Transactions on Database SystemsOptimizing bitmap indices with efficient compression
329 Citations2006Kesheng Wu, Ekow Otoo +1 more
This article presents a new compression scheme called Word-Aligned Hybrid (WAH) code that makes compressed bitmap indices efficient even for high-cardinality attributes and proves that the new compressed bit map index, like the best variants of the B-tree index, is optimal for one-dimensional range queries.
Pattern Analysis and ApplicationsOptimizing two-pass connected-component labeling algorithms
289 Citations2008Kesheng Wu, Ekow Otoo +1 more
Communications of the ACMThe data warehouse and data mining
259 Citations1996W.H. Inmon
There is a relationship between the activity of data mining and the data warehouse—the architectural foundation of decision support systems—which sets the stage for effective data mining.
Lecture notes in computer scienceMODEL 204 architecture and performance
194 Citations1989Patrick O’Neil
Some of the major architectural principles of MODEL 204, a commercial database product of Computer Corporation of America for the IBM 370 computer, are presented and how these principles result in exceptional performance advantages performing certain common tasks in complex query processing are indicated.
A Contract Based System For Large Data Visualization
158 Citations2006Hank Childs, Eric Brugger +5 more
This work introduces the concept of a contract to the standard data flow network design, which enables each component of the data Flow Network to modify the set of optimizations used.
Elsevier eBooksOn the Performance of Bitmap Indices for High Cardinality Attributes
156 Citations2004Kesheng Wu, Ekow Otoo +1 more
This paper systematically analyze the two most efficient bitmap compression techniques, the Byte-aligned Bitmap Code (BBC) and the Word-Aligned Hybrid (WAH) code and concludes that bitmap index is efficient on attributes of low cardinalities as well as on those of high cardinalities.
IBM Systems JournalAn architecture for a business and information system
145 Citations1988Barry Devlin, P. T. Murphy
The background and components of the architecture of EBIS are described, which proposes an integrated warehouse of company data based firmly in the relational database environment and simplified by a consistent set of tools provided by an end-user interface.
The VLDB JournalQuery processing and optimization in Oracle Rdb
138 Citations1996Gennady Antoshenkov, Mohamed Ziauddin
This paper contains an overview of the technology used in the query processing and optimization component of Oracle Rdb, a relational database management system originally developed by Digital Equipment Corporation and now under development by Oracle Corporation.
Compressing bitmap indexes for faster search operations
137 Citations2003Kesheng Wu, Ekow Otoo +1 more
A CPU-friendly scheme which is significantly outperforms well-known compression schemes at a modest increase in storage space and performs logical operations about 12 times faster and uses only 60% more space than the uncompressed scheme.
Query-Driven Visualization of Large Data Sets
89 Citations2006Kurt Stockinger, John Shalf +2 more
A practical and general-purpose approach to large and complex visual data analysis where visualization processing, rendering and subsequent human interpretation is constrained to the subset of data deemed interesting by the user called "bitmap indexing".
ACM Transactions on Database SystemsMulti-resolution bitmap indexes for scientific data
82 Citations2007Rishi Rakesh Sinha, Marianne Winslett
The authors' experiments with large data sets from two scientific domains show that multi-resolution, parallelizable bitmap indexes occupy an acceptable amount of storage while improving range query performance by roughly a factor of 10, compared to a single-resolution bitmap index of reasonable size.
Using bitmap index for interactive exploration of large datasets
71 Citations2003Kesheng Wu, Wendy S. Koegler +2 more
Space efficient bitmap indexing
70 Citations2000Nick Koudas
This work proposes a technique to index large cardinality attributes using bitmaps taking into account both the query and data distribution of the attribute instance, as well as the space requirements of the bitmaps.
Lecture notes in computer scienceBreaking the Curse of Cardinality on Bitmap Indexes
63 Citations2008Kesheng Wu, Kurt Stockinger +1 more
This paper proposes a novel binned bitmap index that greatly reduces the cost to answer queries, and therefore breaks the curse of cardinality, and augments the binned index with an Order-preserving Bin-based Clustering (OrBiC) structure.
eScholarship (California Digital Library)HDF5-FastQuery: Accelerating Complex Queries on HDF Datasets Using Fast Bitmap \nIndices
62 Citations2005Luke Gosink, John Shalf +3 more
Lecture notes in computer scienceEvaluation Strategies for Bitmap Indices with Binning
61 Citations2004Kurt Stockinger, Kesheng Wu +1 more
A performance comparison of bitmap indexes
61 Citations2001Kesheng Wu, Ekow Otoo +1 more
Two new word-aligned schemes are presented that perform logical operations on compressed data 12 times faster than BBC and achieve this performance advantage by guaranteeing that during logical operations every machine instruction performs useful work on words rather than on bytes or bits.
eScholarship (California Digital Library)Bit transposed files
57 Citations1985Harry K. T. Wong, Hsiu-Fen Liu +3 more
Results from experiments suggest that the bit transposed file is a reasonable alternative file structure for large SSDBs and is also amenable to special parallel hardware.
IGI Global eBooksBitmap Indices for Data Warehouses
52 Citations2008Kurt Stockinger, Kesheng Wu
This chapter discusses various bitmap index technologies for efficient query processing indata warehousing applications, and introduces anefficient bitmap compression algorithm and examines the space and time complexity of the compressed bit map index on large data sets from real applications.
Optimizing candidate check costs for bitmap indices
46 Citations2005Doron Rotem, Kurt Stockinger +1 more
A new strategy for optimizing the placement of bin boundaries to minimize the cost of query evaluation using bitmap indices with binning is proposed and it is shown that the dynamic programming based algorithm can efficiently determine the bin boundaries.
Journal of Chemical Information and ModelingBeyond the Virtual Screening Paradigm: Structure-Based Searching for New Lead Compounds
36 Citations2009Jochen Schlosser, Matthias Rarey
The new method named TrixX BMI is ideally suited for application scenarios in which medicinal chemists request a certain pharmacophore interaction pattern to a protein, while the observed runtimes are clearly below one second per compound.
Imaging and visual analysis---Detecting distributed scans using high-performance query-driven visualization
31 Citations2006Kurt Stockinger, E. Wes Bethel +3 more
This paper presents a set of parallel algorithms that demonstrate how an efficient selection mechanism - bitmap indexing - significantly speeds up a common analysis task, namely, computing conditional histogram on very large datasets.
Lecture notes in computer scienceOptimizing I/O Costs of Multi-dimensional Queries Using Bitmap Indices
18 Citations2005Doron Rotem, Kurt Stockinger +1 more
An efficient candidate check algorithm based on attribute value distribution, query distribution as well as query selectivity with respect to each dimension is presented and it is shown that re-ordering the dimensions during query evaluation can be used to reduce I/O costs.
Compressed bitmap indices for efficient query processing
18 Citations2001Kesheng Wu, Ekow Otoo +1 more
In a number of tests on both synthetic data and real application data, it is found that the new schemes significantly outperform the well-known compression schemes while using only modestly more space.
A spatial bitmap-based index for geographical data warehouses
17 Citations2009Thiago Luís Lopes Siqueira, Ricardo Rodrigues Ciferri +2 more
The Spatial Bitmap Index (SB-index), which is an index based on Bitmap and Minimum Bounding Rectangle to provide efficient query processing in Geographical Data Warehouses, showed significantly improvement of 25% up to 95% with regards to the query processing time.
IEEE Transactions on Nuclear ScienceThe ROD crate DAQ software framework of the ATLAS data acquisition system
12 Citations2006S. Gameiro, G. Crone +15 more
The design, functionality and performance of the ROD Crate DAQ and its usage in the ATLAS data acquisition system and during detector tests are presented.
Journal of Physics Conference SeriesCommissioning of the ALICE data acquisition system
5 Citations2008T. Antičić, V. Chibante Barroso +15 more
The DAQ software and hardware architecture is reviewed, including the latest features of the final design, such as the handling of the numerous calibration procedures in a common framework.
Performances of Multi-Level and Multi-Component Compressed BitmapIndices
4 Citations2007Kesheng Wu, Kurt Stockinger +1 more
A systematic study of two large subset of bitmap indexing methods that use multi-component and multi-levelencodings that are shown to be optimal because their worst-case timecomplexities for answering a query is a linear function of the number of hits.
Grid Collector: Facilitating Efficient Selective Access from Data Grids
4 Citations2005Kesheng Wu, Junmin Gu +5 more
The Grid Collector is a system that facilitates the effective analysis and spontaneous exploration of scientific data that combines an efficient indexing technology with a Grid file management technology to speed up common analysis jobs on high-energy physics data and to enable some previously impractical analysis jobs.
Data triage
3 Citations2007Joseph M. Hellerstein, Frederick Reiss
This dissertation proposes an approach to passive network monitoring in which the monitor is provisioned for the average data rate on the network, generally an order of magnitude or more lower than the peak rate.
Grid Collector: Using an event catalog to speed up user analysis in distributed environment - eScholarship
3 Citations2004Kesheng Wu, Arie Shoshani +3 more
Indexing scientific data
2 Citations2007Marianne Winslett, Rishi Rakesh Sinha
Multi-resolution bitmap indexes, which group data into bins at multiple granularities, are introduced and a novel algorithm to consolidate data points into regions of interest is introduced to achieve sublinear running times, with respect to the number of points in the query result, for both the index lookup and region consolidation.
Application of High-performance Visual Analysis Methods to Laser Wakefield Particle Acceleration Data
1 Citations2008Oliver Rübel
This work extends histogram-based parallel coordinates for use in visual information display as well as an interface for guiding and performing data mining operations, which are based upon multi-dimensional and temporal thresholding and data subsetting operations.