|
 ABSTRACT
Bitmap indexing has been touted as a promising approach for processing complex adhoc queries in read-mostly environments, like those of decision support systems. Nevertheless, only few possible bitmap schemes have been proposed in the past and very little is known about the space-time tradeoff that they offer. In this paper, we present 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. In particular, we draw a parallel between bitmap indexing and number representation in different number systems, and define a space of two orthogonal dimensions that captures a wide array of bitmap indexes, both old and new. Within that space, we identify (analytically or experimentally) the following interesting points: (1) the time-optimal bitmap index; (2) the space-optimal bitmap index; (3) the bitmap index with the optimal space-time tradeoff (knee); and (4) the time-optimal bitmap index under a given disk-space constraint. Finally, we examine the impact of bitmap compression and bitmap buffering on the space-time tradeoffs among those indexes. As part of this work, we also describe a bitmap-index-based evaluation algorithm for selection queries that represents an improvement over earlier proposals. We believe that this study offers a useful first set of guidelines for physical database design using bitmap indexes.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
AIPD Technical Publications. Sybase IQ Indexes. In Sybase IQ Administration Guide, Sybase IQ Release 11.2 Collection, chapter 5. Sybase Inc., March 1997. http://sybooks.sybase.com/cgi-bin/nphdynaweb/siq 11201/iq_admin/l .toc.
|
| |
2
|
C.Y. Chart and Y.E. Ioannidis. Bitmap Index Design and Evaluation. Computer Sciences Dept., University of Wisconsin-Madison, 1997. http ://www. cs. wis c.edu/~ cychan/paper 101 .ps.
|
 |
3
|
|
| |
4
|
Transaction Processing Performance Council, May 1995. http://www.tpc.org.
|
| |
5
|
H. Edelstein. Faster Data Warehouses. Information Week, pages 77- 88, December 1995.
|
| |
6
|
|
| |
7
|
|
| |
8
|
|
| |
9
|
|
| |
10
|
|
| |
11
|
Thin-Fong Tsuei , Allan N. Packer , Keng-Tai Ko, Database buffer size investigation for OLTP workloads, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.112-122, May 11-15, 1997, Tucson, Arizona, United States
|
| |
12
|
J. Winchelt. Rushmore's Bald Spot. DBMS, 4(10):58, September 1991.
|
| |
13
|
H.K.T. Wong, J.Z. Li, F. Olken, D. Rotem, and L. Wong. Bit Tranposition for Very Large Scientific and Statistical Databases. Algorithmica, 1(3):289-309, 1986.
|
| |
14
|
H.K.T. Wong, H-E Liu, E Olken, D. Rotem, and L. Wong. Bit Tranposed Files. In VLDB'85, pages 448-457, Stockholm, 1985.
|
CITED BY 55
|
|
|
|
|
Robert W.P. Luk , H. V. Leong , Tharam S. Dillon , Alvin T.S. Chan , W. Bruce Croft , James Allan, A survey in indexing and searching XML documents, Journal of the American Society for Information Science and Technology, v.53 n.6, p.415-437, May, 2002
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Kurt Stockinger , Kesheng Wu , Arie Shoshani, Strategies for processing ad hoc queries on large data warehouses, Proceedings of the 5th ACM international workshop on Data Warehousing and OLAP, p.72-79, November 08-08, 2002, McLean, Virginia, USA
|
|
|
Eugene Inseok Chong , Jagannathan Srinivasan , Souripriya Das , Chuck Freiwald , Aravind Yalamanchi , Mahesh Jagannath , Anh-Tuan Tran , Ramkumar Krishnan , Richard Jiang, A mapping mechanism to support bitmap index and other auxiliary structures on tables stored as primary B+-trees, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
|
|
|
|
|
|
Eugene Inseok Chong , Jagannathan Srinivasan , Souripriya Das , Chuck Freiwald , Aravind Yalamanchi , Mahesh Jagannath , Anh-Tuan Tran , Ramkumar Krishnan , Richard Jiang, A mapping mechanism to support bitmap index and other auxiliary structures on tables stored as primary B+-trees, ACM SIGMOD Record, v.32 n.2, June 2003
|
|
|
Ashima Gupta , Karen C. Davis , Jennifer Grommon-Litton, Performance comparison of property map and bitmap indexing, Proceedings of the 5th ACM international workshop on Data Warehousing and OLAP, p.65-71, November 08-08, 2002, McLean, Virginia, USA
|
|
|
|
|
|
|
|
|
|
|
|
Bijit Hore , Hakan Hacigumus , Bala Iyer , Sharad Mehrotra, Indexing text data under space constraints, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Kurt Stockinger , E. Wes Bethel , Scott Campbell , Eli Dart , Kesheng Wu, Imaging and visual analysis---Detecting distributed scans using high-performance query-driven visualization, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Nikos Karayannidis , Aris Tsois , Timos Sellis , Roland Pieringer , Volker Markl , Frank Ramsak , Robert Fenk , Klaus Elhardt , Rudolf Bayer, Processing star queries on hierarchically-clustered fact tables, Proceedings of the 28th international conference on Very Large Data Bases, p.730-741, August 20-23, 2002, Hong Kong, China
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Carlo Dell'Aquila , Ezio Lefons , Filippo Tangorra, Analytic use of bitmap indices, Proceedings of the 6th Conference on 6th WSEAS Int. Conf. on Artificial Intelligence, Knowledge Engineering and Data Bases, p.159-164, February 16-19, 2007, Corfu Island, Greece
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Oliver Rübel , Prabhat , Kesheng Wu , Hank Childs , Jeremy Meredith , Cameron G. R. Geddes , Estelle Cormier-Michel , Sean Ahern , Gunther H. Weber , Peter Messmer , Hans Hagen , Bernd Hamann , E. Wes Bethel, High performance multivariate visual data exploration for extremely large data, Proceedings of the 2008 ACM/IEEE conference on Supercomputing, November 15-21, 2008, Austin, Texas
|
|
|
|
|
|
Carlo Dell'aquila , Ezio Lefons , Filippo Tangorra, Capturing semantics from bitmap indices for data analysis, Proceedings of the 6th WSEAS International Conference on Simulation, Modelling and Optimization, p.438-443, September 22-24, 2006, Lisbon, Portugal
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
H.3