{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T11:33:55Z","timestamp":1791459235011,"version":"4.3.4"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,3]]},"abstract":"<jats:p>\n            Bitmap indices are efficient for answering queries on low-cardinality attributes. In this article, we present a new compression scheme called\n            <jats:italic>Word-Aligned Hybrid<\/jats:italic>\n            (WAH) code that makes compressed bitmap indices efficient even for high-cardinality attributes. We further prove that the new compressed bitmap index, like the best variants of the B-tree index, is optimal for one-dimensional range queries. More specifically, the time required to answer a one-dimensional range query is a linear function of the number of hits. This strongly supports the well-known observation that compressed bitmap indices are efficient for multidimensional range queries because results of one-dimensional range queries computed with bitmap indices can be easily combined to answer multidimensional range queries. Our timing measurements on range queries not only confirm the linear relationship between the query response time and the number of hits, but also demonstrate that WAH compressed indices answer queries faster than the commonly used indices including projection indices, B-tree indices, and other compressed bitmap indices.\n          <\/jats:p>","DOI":"10.1145\/1132863.1132864","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":239,"title":["Optimizing bitmap indices with efficient compression"],"prefix":"10.1145","volume":"31","author":[{"given":"Kesheng","family":"Wu","sequence":"first","affiliation":[{"name":"Lawrence Berkeley National Laboratory, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ekow J.","family":"Otoo","sequence":"additional","affiliation":[{"name":"Lawrence Berkeley National Laboratory, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arie","family":"Shoshani","sequence":"additional","affiliation":[{"name":"Lawrence Berkeley National Laboratory, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10--14","author":"Amer-Yahia S.","year":"2000","unstructured":"Amer-Yahia , S. and Johnson , T . 2000. Optimizing queries on compressed bitmaps . In VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10--14 , 2000 , Cairo, Egypt, A. E. Abbadi, M. L. Brodie, S. Chakravarthy, U. Dayal, N. Kamel, G. Schlageter, and K.-Y. Whang, Eds. Morgan Kaufmann, San Francisco, CA, 329--338.]] Amer-Yahia, S. and Johnson, T. 2000. Optimizing queries on compressed bitmaps. In VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10--14, 2000, Cairo, Egypt, A. E. Abbadi, M. L. Brodie, S. Chakravarthy, U. Dayal, N. Kamel, G. Schlageter, and K.-Y. Whang, Eds. Morgan Kaufmann, San Francisco, CA, 329--338.]]"},{"key":"e_1_2_1_2_1","volume-title":"Byte-aligned bitmap compression. Tech. rep","author":"Antoshenkov G.","unstructured":"Antoshenkov , G. 1994. Byte-aligned bitmap compression. Tech. rep . Oracle Corp., Redwood Shores, CA. U.S. Patent number 5,363,098.]] Antoshenkov, G. 1994. Byte-aligned bitmap compression. Tech. rep. Oracle Corp., Redwood Shores, CA. U.S. Patent number 5,363,098.]]"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050026"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276336"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304201"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/248603.248616"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/36.6.579"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/125187.125200"},{"key":"e_1_2_1_10_1","volume-title":"6th International Conference, CISMOD'95","author":"Furuse K.","year":"1995","unstructured":"Furuse , K. , Asada , K. , and Iizawa , A . 1995. Implementation and performance evaluation of compressed bit-sliced signature files. In Information Systems and Data Management , 6th International Conference, CISMOD'95 , Bombay, India, November 15--17 , 1995 , Proceedings, S. Bhalla, Ed. Lecture Notes in Computer Science, vol. 1006. Springer, Berlin, Germany, 164--177.]] Furuse, K., Asada, K., and Iizawa, A. 1995. Implementation and performance evaluation of compressed bit-sliced signature files. In Information Systems and Data Management, 6th International Conference, CISMOD'95, Bombay, India, November 15--17, 1995, Proceedings, S. Bhalla, Ed. Lecture Notes in Computer Science, vol. 1006. Springer, Berlin, Germany, 164--177.]]"},{"key":"e_1_2_1_11_1","unstructured":"Gailly J. and Adler M. 1998. zlib 1.1.3 manual. Source code available online at http:\/\/-www.info-zip.org\/pub\/-infozip\/zlib.]]  Gailly J. and Adler M. 1998. zlib 1.1.3 manual. Source code available online at http:\/\/-www.info-zip.org\/pub\/-infozip\/zlib.]]"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170076"},{"key":"e_1_2_1_13_1","volume-title":"VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7--10","author":"Johnson T.","year":"1999","unstructured":"Johnson , T. 1999. Performance measurements of compressed bitmap indices . In VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7--10 , 1999 , Edinburgh, Scotland, UK, M. P. Atkinson, M. E. Orlowska, P. Valduriez, S. B. Zdonik, and M. L. Brodie, Eds. Morgan Kaufmann , San Francisco, CA, 278--289. A longer version appeared as AT&T report number AMERICA112.]] Johnson, T. 1999. Performance measurements of compressed bitmap indices. In VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7--10, 1999, Edinburgh, Scotland, UK, M. P. Atkinson, M. E. Orlowska, P. Valduriez, S. B. Zdonik, and M. L. Brodie, Eds. Morgan Kaufmann, San Francisco, CA, 278--289. A longer version appeared as AT&T report number AMERICA112.]]"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Workshop on Design and Management of Data Warehouses, DMDW'99","author":"J\u00fcrgens M.","year":"1999","unstructured":"J\u00fcrgens , M. and Lenz , H . -J. 1999. Tree based indexes vs. bitmap indexes---a performance study . In Proceedings of the International Workshop on Design and Management of Data Warehouses, DMDW'99 , Heidelberg, Germany , June 14-15, 1999 , S. Gatziu, M. A. Jeusfeld, M. Staudt, and Y. Vassiliou, Eds.]] J\u00fcrgens, M. and Lenz, H.-J. 1999. Tree based indexes vs. bitmap indexes---a performance study. In Proceedings of the International Workshop on Design and Management of Data Warehouses, DMDW'99, Heidelberg, Germany, June 14-15, 1999, S. Gatziu, M. A. Jeusfeld, M. Staudt, and Y. Vassiliou, Eds.]]"},{"key":"e_1_2_1_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 , Reading, MA .]] Knuth, D. E. 1998. The Art of Computer Programming, 2nd ed. Vol. 3. Addison Wesley, Reading, MA.]]","edition":"2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/354756.354819"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.390248"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/133160.133210"},{"key":"e_1_2_1_19_1","volume-title":"2nd International Workshop in High Performance Transaction Systems","volume":"359","author":"O'Neil P.","year":"1987","unstructured":"O'Neil , P. 1987 . Model 204 architecture and performance . In 2nd International Workshop in High Performance Transaction Systems , Asilomar, CA. Lecture Notes in Computer Science , vol. 359 . Springer-Verlag, Berlin, Germany, 40--59.]] O'Neil, P. 1987. Model 204 architecture and performance. In 2nd International Workshop in High Performance Transaction Systems, Asilomar, CA. Lecture Notes in Computer Science, vol. 359. Springer-Verlag, Berlin, Germany, 40--59.]]"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/556451"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253268"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/211990.212001"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.1999.787637"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/648313.755683"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/583890.583901"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of 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 VLDB 85 ( Stockholm, Sweden). 448--457.]] Wong, H. K. T., Liu, H.-F., Olken, F., Rotem, D., and Wong, L. 1985. Bit transposed files. In Proceedings of VLDB 85 (Stockholm, Sweden). 448--457.]]"},{"key":"e_1_2_1_27_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_1_28_1","volume-title":"Proceedings of the Fourteenth International Conference on Data Engineering (February 23--27","author":"Wu M.-C.","unstructured":"Wu , M.-C. and Buchmann , A. P . 1998. Encoded bitmap indexing for data warehouses . In Proceedings of the Fourteenth International Conference on Data Engineering (February 23--27 , Orlando, FL). IEEE Computer Society, ACM Press, Los Alamitos, CA, 220--230.]] Wu, M.-C. and Buchmann, A. P. 1998. Encoded bitmap indexing for data warehouses. In Proceedings of the Fourteenth International Conference on Data Engineering (February 23--27, Orlando, FL). IEEE Computer Society, ACM Press, Los Alamitos, CA, 220--230.]]"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.2003.1214955"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/502585.502689"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.2002.1029710"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the Thirtieth International Conference on Very Large Data Bases","author":"Wu K.","year":"2004","unstructured":"Wu , K. , Otoo , E. J. , and Shoshani , A . 2004. On the performance of bitmap indices for high-cardinality attributes . In Proceedings of the Thirtieth International Conference on Very Large Data Bases , Toronto, Canada, August 31- September 3, 2004 , M. A. Nascimento, M. T. \u00d6zsu, D. Kossmann, R. J. Miller, J. A. Blakeley, and K. B. Schiefer, Eds. Morgan Kaufmann, San Francisco, CA, 24--35.]] Wu, K., Otoo, E. J., and Shoshani, A. 2004. On the performance of bitmap indices for high-cardinality attributes. In Proceedings of the Thirtieth International Conference on Very Large Data Bases, Toronto, Canada, August 31-September 3, 2004, M. A. Nascimento, M. T. \u00d6zsu, D. Kossmann, R. J. Miller, J. A. Blakeley, and K. B. Schiefer, Eds. Morgan Kaufmann, San Francisco, CA, 24--35.]]"},{"key":"e_1_2_1_33_1","unstructured":"Wu K. Otoo E. J. Shoshani A. and Nordberg H. 2001b. Notes on design and implementation of compressed bit vectors. Tech. rep. LBNL\/PUB-3161. Lawrence Berkeley National Laboratory Berkeley CA.]]  Wu K. Otoo E. J. Shoshani A. and Nordberg H. 2001b. Notes on design and implementation of compressed bit vectors. Tech. rep. LBNL\/PUB-3161. Lawrence Berkeley National Laboratory Berkeley CA.]]"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132863.1132864","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132863.1132864","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:13Z","timestamp":1750259173000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132863.1132864"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1145\/1132863.1132864"],"URL":"https:\/\/doi.org\/10.1145\/1132863.1132864","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,3]]},"assertion":[{"value":"2006-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}