{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T04:35:35Z","timestamp":1768106135311,"version":"3.49.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,2,15]],"date-time":"2008-02-15T00:00:00Z","timestamp":1203033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-AC02-05CH11231"],"award-info":[{"award-number":["DE-AC02-05CH11231"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2010,2]]},"abstract":"<jats:p>Bitmap indexes are known as the most effective indexing methods for range queries on append-only data, and many different bitmap indexes have been proposed in the research literature. However, only two of the simplest ones are used in commercial products. To better understand the benefits offered by the more sophisticated variations, we conduct an analytical comparison of well-known bitmap indexes, most of which are in the class of multi-component bitmap indexes. Our analysis is the first to fully incorporate the effects of compression on their performance. We produce closed-form formulas for both the index sizes and the query processing costs for the worst cases. One surprising finding is that the two simple indexes are in fact the best among multi-component indexes. Additionally, we investigate a number of novel variations in a class of multi-level indexes, and find that they answer queries faster than the best of multi-component indexes. More specifically, some two-level indexes are predicted by analyses and verified with experiments to be 5 to 10 times faster than well-known indexes. Furthermore, these two-level indexes have the optimal computational complexity for answering queries.<\/jats:p>","DOI":"10.1145\/1670243.1670245","type":"journal-article","created":{"date-parts":[[2010,2,16]],"date-time":"2010-02-16T20:51:06Z","timestamp":1266353466000},"page":"1-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":44,"title":["Analyses of multi-level and multi-component compressed bitmap indexes"],"prefix":"10.1145","volume":"35","author":[{"given":"Kesheng","family":"Wu","sequence":"first","affiliation":[{"name":"Lawrence Berkeley National Laboratory, Berkeley, CA"}]},{"given":"Arie","family":"Shoshani","sequence":"additional","affiliation":[{"name":"Lawrence Berkeley National Laboratory, Berkeley, CA"}]},{"given":"Kurt","family":"Stockinger","sequence":"additional","affiliation":[{"name":"Lawrence Berkeley National Laboratory, Berkeley, CA"}]}],"member":"320","published-online":{"date-parts":[[2008,2,15]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/874051.874730"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050026"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Bloch G. Greiner S. De Meer H. and Trivedi K. S. 1998. Queueing Networks and Markov Chains. John Wiley and Sons New York.   Bloch G. Greiner S. De Meer H. and Trivedi K. S. 1998. Queueing Networks and Markov Chains. John Wiley and Sons New York.","DOI":"10.1002\/0471200581"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(90)90072-A"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009931317394"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276336"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304201"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.970575"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM Press","author":"Delis A.","unstructured":"Delis , A. , Faloutsos , C. , and Ghandeharizadeh , S. , Eds . 1999 . In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM Press , New York. Delis, A., Faloutsos, C., and Ghandeharizadeh, S., Eds. 1999. In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM Press, New York."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2275.357411"},{"key":"e_1_2_2_12_1","volume-title":"Proceedings of the International Conference on Very Large DataBases (VLDB '96)","author":"Faloutsos C.","unstructured":"Faloutsos , C. , Matias , Y. , and Silberschatz , A . 1996. Modeling skewed distribution using multifractals and the '80-20' law . In Proceedings of the International Conference on Very Large DataBases (VLDB '96) . Morgan Kaufmann, San Francisco, CA, 307--317. Faloutsos, C., Matias, Y., and Silberschatz, A. 1996. Modeling skewed distribution using multifractals and the '80-20' law. In Proceedings of the International Conference on Very Large DataBases (VLDB '96). Morgan Kaufmann, San Francisco, CA, 307--317."},{"key":"e_1_2_2_13_1","volume-title":"Proceedings of the International Conference on Very Large DataBases (VLDB). K. B\u00f6hm, C. S. Jensen, L. M. Haas, M. L. Kersten, P.-\u00c5. Larson, and B. C. Ooi Eds., ACM Press","author":"Hu Y.","unstructured":"Hu , Y. , Sundara , S. , Chorma , T. , and Srinivasan , J . 2005. Supporting RFID-based item tracking applications in oracle DBMS using a bitmap datatype . In Proceedings of the International Conference on Very Large DataBases (VLDB). K. B\u00f6hm, C. S. Jensen, L. M. Haas, M. L. Kersten, P.-\u00c5. Larson, and B. C. Ooi Eds., ACM Press , New York, 1140--1151. Hu, Y., Sundara, S., Chorma, T., and Srinivasan, J. 2005. Supporting RFID-based item tracking applications in oracle DBMS using a bitmap datatype. In Proceedings of the International Conference on Very Large DataBases (VLDB). K. B\u00f6hm, C. S. Jensen, L. M. Haas, M. L. Kersten, P.-\u00c5. Larson, and B. C. Ooi Eds., ACM Press, New York, 1140--1151."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/645925.671351"},{"key":"e_1_2_2_15_1","volume-title":"The Art of Computer Programming","author":"Knuth D. E.","unstructured":"Knuth , D. E. 1998. The Art of Computer Programming 2 nd Ed. Vol. 3 . Addison Wesley . Knuth, D. E. 1998. The Art of Computer Programming 2nd Ed. Vol. 3. Addison Wesley.","edition":"2"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/354756.354819"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1086\/427203"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0255(99)00068-7"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the 30th International Conference on Very Large DataBases (VLDB'04)","author":"MacNicol R.","unstructured":"MacNicol , R. and French , B . 2004. Sybase IQ multiplex - Designed for analytics . In Proceedings of the 30th International Conference on Very Large DataBases (VLDB'04) . 1227--1230. MacNicol, R. and French, B. 2004. Sybase IQ multiplex - Designed for analytics. In Proceedings of the 30th International Conference on Very Large DataBases (VLDB'04). 1227--1230."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/133160.133210"},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases (VLDB'04)","author":"Nascimento M. A.","unstructured":"Nascimento , M. A. , \u00d6zsu , M. T. , Kossmann , D. , Miller , R. J. , Blakeley , J. A. , and Schiefer , K. B. , Eds . 2004 . In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB'04) . Morgan Kaufmann. Nascimento, M. A., \u00d6zsu, M. T., Kossmann, D., Miller, R. J., Blakeley, J. A., and Schiefer, K. B., Eds. 2004. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB'04). Morgan Kaufmann."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1304611.1306564"},{"key":"e_1_2_2_23_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 2nd International Workshop in High Performance Transaction Systems","author":"O'Neil P.","unstructured":"O'Neil , P. 1987. Model 204 architecture and performance . In Proceedings of the 2nd International Workshop in High Performance Transaction Systems . Lecture Notes in Computer Science , vol. 359 . Springer , 40--59. O'Neil, P. 1987. Model 204 architecture and performance. In Proceedings of the 2nd International Workshop in High Performance Transaction Systems. Lecture Notes in Computer Science, vol. 359. Springer, 40--59."},{"key":"e_1_2_2_24_1","first-page":"38","article-title":"Informix indexing support for data warehouses","volume":"10","author":"O'Neil P.","year":"1997","unstructured":"O'Neil , P. 1997 . Informix indexing support for data warehouses . Datab. Program. Des. 10 , 2, 38 -- 43 . O'Neil, P. 1997. Informix indexing support for data warehouses. Datab. Program. Des. 10, 2, 38--43.","journal-title":"Datab. Program. Des."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253268"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/211990.212001"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/646497.695627"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1099554.1099718"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272746"},{"key":"e_1_2_2_30_1","first-page":"57023","volume-title":"Proceedings of the International Conference on Statistical and Scientific Database Management (SSDBM'05)","author":"Stockinger K.","unstructured":"Stockinger , K. , Shalf , J. , Bethel , W. , and Wu , K . 2005. DEX: Increasing the capability of scientific data analysis pipelines by using efficient bitmap indices to accelerate scientific visualization . In Proceedings of the International Conference on Statistical and Scientific Database Management (SSDBM'05) . 35--44. LBNL rep. LBNL- 57023 . Stockinger, K., Shalf, J., Bethel, W., and Wu, K. 2005. DEX: Increasing the capability of scientific data analysis pipelines by using efficient bitmap indices to accelerate scientific visualization. In Proceedings of the International Conference on Statistical and Scientific Database Management (SSDBM'05). 35--44. LBNL rep. LBNL-57023."},{"key":"e_1_2_2_31_1","unstructured":"Stockinger K. and Wu K. 2006. Bitmap Indices for Data Warehouses. Idea Group Inc. Chapter VII 179--202. LBNL-59952.  Stockinger K. and Wu K. 2006. Bitmap Indices for Data Warehouses. Idea Group Inc. Chapter VII 179--202. LBNL-59952."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/583890.583901"},{"key":"e_1_2_2_33_1","volume-title":"Proceedings of the International Conference on Database and Expert Systems Applications (DEXA'04)","author":"Stockinger K.","unstructured":"Stockinger , K. , Wu , K. , and Shoshani , A . 2004. Evaluation strategies for bitmap indices with binning . In Proceedings of the International Conference on Database and Expert Systems Applications (DEXA'04) . Springer. Stockinger, K., Wu, K., and Shoshani, A. 2004. Evaluation strategies for bitmap indices with binning. In Proceedings of the International Conference on Database and Expert Systems Applications (DEXA'04). Springer."},{"key":"e_1_2_2_34_1","volume-title":"Proceedings of the International Conference on Very Large DataBases (VLDB'85)","author":"Wong H. K. T.","unstructured":"Wong , H. K. T. , Liu , H.-F. , Olken , F. , Rotem , D. , and Wong , L . 1985. Bit transposed files . In Proceedings of the International Conference on Very Large DataBases (VLDB'85) . 448--457. Wong, H. K. T., Liu, H.-F., Olken, F., Rotem, D., and Wong, L. 1985. Bit transposed files. In Proceedings of the International Conference on Very Large DataBases (VLDB'85). 448--457."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/16\/1\/077"},{"key":"e_1_2_2_36_1","doi-asserted-by":"crossref","unstructured":"Wu K. Otoo E. and Shoshani A. 2001a. Compressed bitmap indices for efficient query processing. Tech. rep. LBNL-47807 Lawrence Berkeley National Laboratory Berkeley CA.  Wu K. Otoo E. and Shoshani A. 2001a. Compressed bitmap indices for efficient query processing. Tech. rep. LBNL-47807 Lawrence Berkeley National Laboratory Berkeley CA.","DOI":"10.2172\/808915"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/502585.502689"},{"key":"e_1_2_2_38_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'04)","author":"Wu K.","unstructured":"Wu , K. , Otoo , E. , and Shoshani , A . 2004. On the performance of bitmap indices for high cardinality attributes . In Proceedings of the International Conference on Very Large Databases (VLDB'04) . 24--35. LBNL-54673. Wu, K., Otoo, E., and Shoshani, A. 2004. On the performance of bitmap indices for high cardinality attributes. In Proceedings of the International Conference on Very Large Databases (VLDB'04). 24--35. LBNL-54673."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132864"},{"key":"e_1_2_2_40_1","volume-title":"RC 20449","author":"Wu K.-L.","unstructured":"Wu , K.-L. and Yu , P . 1996. Range-Based bitmap indexing for high cardinality attributes with skew. Tech. rep . RC 20449 , IBM Watson Research Division, Yorktown Heights, NY. Wu, K.-L. and Yu, P. 1996. Range-Based bitmap indexing for high cardinality attributes with skew. Tech. rep. RC 20449, IBM Watson Research Division, Yorktown Heights, NY."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304202"},{"key":"e_1_2_2_42_1","volume-title":"Proceedings of the 14th International Conference on Data Engineering. IEEE Computer Society, 220--230","author":"Wu M.-C.","unstructured":"Wu , M.-C. and Buchmann , A. P . 1998. Encoded bitmap indexing for data warehouses . In Proceedings of the 14th International Conference on Data Engineering. IEEE Computer Society, 220--230 . Wu, M.-C. and Buchmann, A. P. 1998. Encoded bitmap indexing for data warehouses. In Proceedings of the 14th International Conference on Data Engineering. IEEE Computer Society, 220--230."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/296854.277632"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1670243.1670245","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1670243.1670245","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:40:58Z","timestamp":1750250458000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1670243.1670245"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2,15]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["10.1145\/1670243.1670245"],"URL":"https:\/\/doi.org\/10.1145\/1670243.1670245","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2,15]]},"assertion":[{"value":"2008-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-02-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}