{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:50:27Z","timestamp":1773481827843,"version":"3.50.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,8,29]]},"abstract":"<jats:p>Nowadays Web search engines are experiencing significant performance challenges caused by a huge amount of Web pages and increasingly larger number of Web users. The key issue for addressing these challenges is to design a compact structure which can index Web documents with low space and meanwhile process keyword search very fast. Unfortunately, the current solutions typically separate the space optimization from the search improvement. As a result, such solutions either save space yet with search inefficiency, or allow fast keyword search but with huge space requirement. In this paper, to address the challenges, we propose a novel structure bitlist with both low space requirement and supporting fast keyword search. Specifically, based on a simple and yet very efficient encoding scheme, bitlist uses a single number to encode a set of integer document IDs for low space, and adopts fast bitwise operations for very efficient boolean-based keyword search. Our extensive experimental results on real and synthetic data sets verify that bitlist outperforms the recent proposed solution, inverted list compression [23, 22] by spending 36.71% less space and 61.91% faster processing time, and achieves comparable running time as [8] but with significantly lower space.<\/jats:p>","DOI":"10.14778\/2536258.2536264","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1522-1533","source":"Crossref","is-referenced-by-count":8,"title":["Bitlist"],"prefix":"10.14778","volume":"6","author":[{"given":"Weixiong","family":"Rao","sequence":"first","affiliation":[{"name":"School of Software Engineering, Tongji University, China and Department of Comp. Sci., University of Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Comp. Sci. and Eng., Hong Kong University of Sci.and Tech."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pan","family":"Hui","sequence":"additional","affiliation":[{"name":"Department of Comp. Sci. and Eng., Hong Kong University of Sci.and Tech. and Telekom Innovation Laboratories, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sasu","family":"Tarkoma","sequence":"additional","affiliation":[{"name":"Department of Comp. Sci., University of Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/data.linkedin.com\/opensource\/kamikaze.  http:\/\/data.linkedin.com\/opensource\/kamikaze."},{"key":"e_1_2_1_2_1","unstructured":"http:\/\/sna-projects.com\/kamikaze\/.  http:\/\/sna-projects.com\/kamikaze\/."},{"issue":"1","key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1023\/B:INRT.0000048490.99518.5c","article-title":"Inverted index compression using word-aligned binary codes","volume":"8","author":"Anh V. N.","year":"2005","unstructured":"V. N. Anh and A. Moffat . Inverted index compression using word-aligned binary codes . Inf. Retr. , 8 ( 1 ): 151 - 166 , 2005 . V. N. Anh and A. Moffat. Inverted index compression using word-aligned binary codes. Inf. Retr., 8(1):151-166, 2005.","journal-title":"Inf. Retr."},{"key":"e_1_2_1_4_1","first-page":"739","volume-title":"ISAAC","author":"Bille P.","year":"2007","unstructured":"P. Bille , A. Pagh , and R. Pagh . Fast evaluation of union-intersection expressions . In ISAAC , pages 739 - 750 , 2007 . P. Bille, A. Pagh, and R. Pagh. Fast evaluation of union-intersection expressions. In ISAAC, pages 739-750, 2007."},{"issue":"4","key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1007\/s10791-006-6614-y","article-title":"Tsp and cluster-based solutions to the reassignment of document identifiers","volume":"9","author":"Blanco R.","year":"2006","unstructured":"R. Blanco and A. Barreiro . Tsp and cluster-based solutions to the reassignment of document identifiers . Inf. Retr. , 9 ( 4 ): 499 - 517 , 2006 . R. Blanco and A. Barreiro. Tsp and cluster-based solutions to the reassignment of document identifiers. Inf. Retr., 9(4):499-517, 2006.","journal-title":"Inf. Retr."},{"key":"e_1_2_1_6_1","first-page":"342","volume-title":"DCC","author":"Blandford D. K.","year":"2002","unstructured":"D. K. Blandford and G. E. Blelloch . Index compression through document reordering . In DCC , pages 342 - 351 , 2002 . D. K. Blandford and G. E. Blelloch. Index compression through document reordering. In DCC, pages 342-351, 2002."},{"key":"e_1_2_1_7_1","first-page":"743","volume-title":"SODA","author":"Demaine E. D.","year":"2000","unstructured":"E. D. Demaine , A. L\u00f3pez-Ortiz , and J. I. Munro . Adaptive set intersections, unions, and differences . In SODA , pages 743 - 752 , 2000 . E. D. Demaine, A. L\u00f3pez-Ortiz, and J. I. Munro. Adaptive set intersections, unions, and differences. In SODA, pages 743-752, 2000."},{"issue":"4","key":"e_1_2_1_8_1","first-page":"255","article-title":"Fast set intersection in memory","volume":"4","author":"Ding B.","year":"2011","unstructured":"B. Ding and A. C. K\u00f6nig . Fast set intersection in memory . PVLDB , 4 ( 4 ): 255 - 266 , 2011 . B. Ding and A. C. K\u00f6nig. Fast set intersection in memory. PVLDB, 4(4):255-266, 2011.","journal-title":"PVLDB"},{"key":"e_1_2_1_9_1","first-page":"311","volume-title":"WWW","author":"Ding S.","year":"2010","unstructured":"S. Ding , J. Attenberg , and T. Suel . Scalable techniques for document identifier assignment ininverted indexes . In WWW , pages 311 - 320 , 2010 . S. Ding, J. Attenberg, and T. Suel. Scalable techniques for document identifier assignment ininverted indexes. In WWW, pages 311-320, 2010."},{"issue":"4","key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1016\/S0022-0000(03)00026-6","article-title":"Optimal aggregation algorithms for middleware","volume":"66","author":"Fagin R.","year":"2003","unstructured":"R. Fagin , A. Lotem , and M. Naor . Optimal aggregation algorithms for middleware . J. Comput. Syst. Sci. , 66 ( 4 ): 614 - 656 , 2003 . R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci., 66(4):614-656, 2003.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_11_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman , 1979 . M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979."},{"issue":"1","key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1137\/0201004","article-title":"A simple algorithm for merging two disjoint linearly-ordered sets","volume":"1","author":"Hwang F. K.","year":"1972","unstructured":"F. K. Hwang and S. Lin . A simple algorithm for merging two disjoint linearly-ordered sets . SIAM J. Comput. , 1 ( 1 ): 31 - 39 , 1972 . F. K. Hwang and S. Lin. A simple algorithm for merging two disjoint linearly-ordered sets. SIAM J. Comput., 1(1):31-39, 1972.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_14_1","first-page":"13","volume-title":"VLDB","author":"Johnson D. S.","year":"2004","unstructured":"D. S. Johnson , S. Krishnan , J. Chhugani , S. Kumar , and S. Venkatasubramanian . Compressing large boolean matrices using reordering techniques . In VLDB , pages 13 - 23 , 2004 . D. S. Johnson, S. Krishnan, J. Chhugani, S. Kumar, and S. Venkatasubramanian. Compressing large boolean matrices using reordering techniques. In VLDB, pages 13-23, 2004."},{"issue":"11","key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1145\/361219.361225","article-title":"A note on the set basis problem related to the compaction of character sets","volume":"18","author":"Kou L. T.","year":"1975","unstructured":"L. T. Kou and C. K. Wong . A note on the set basis problem related to the compaction of character sets . Commun. ACM , 18 ( 11 ): 656 - 557 , 1975 . L. T. Kou and C. K. Wong. A note on the set basis problem related to the compaction of character sets. Commun. ACM, 18(11):656-557, 1975.","journal-title":"Commun. ACM"},{"issue":"5","key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","article-title":"On the hardness of approximating minimization problems","volume":"41","author":"Lund C.","year":"1994","unstructured":"C. Lund and M. Yannakakis . On the hardness of approximating minimization problems . J. ACM , 41 ( 5 ): 960 - 981 , 1994 . C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. J. ACM, 41(5):960-981, 1994.","journal-title":"J. ACM"},{"issue":"1","key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1023\/A:1013002601898","article-title":"Binary interpolative coding for effective index compression","volume":"3","author":"Moffat A.","year":"2000","unstructured":"A. Moffat and L. Stuiver . Binary interpolative coding for effective index compression . Inf. Retr. , 3 ( 1 ): 25 - 47 , 2000 . A. Moffat and L. Stuiver. Binary interpolative coding for effective index compression. Inf. Retr., 3(1):25-47, 2000.","journal-title":"Inf. Retr."},{"issue":"1","key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0306-4573(02)00020-1","article-title":"Inverted file compression through document identifier reassignment","volume":"39","author":"Shieh W.-Y.","year":"2003","unstructured":"W.-Y. Shieh , T.-F. Chen , J. J.-J. Shann , and C.-P. Chung . Inverted file compression through document identifier reassignment . Inf. Process. Manage. , 39 ( 1 ): 117 - 131 , 2003 . W.-Y. Shieh, T.-F. Chen, J. J.-J. Shann, and C.-P. Chung. Inverted file compression through document identifier reassignment. Inf. Process. Manage., 39(1):117-131, 2003.","journal-title":"Inf. Process. Manage."},{"issue":"2","key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1137\/0403025","article-title":"On approximate solutions for combinatorial optimization problems","volume":"3","author":"Simon H.-U.","year":"1990","unstructured":"H.-U. Simon . On approximate solutions for combinatorial optimization problems . SIAM J. Discrete Math. , 3 ( 2 ): 294 - 310 , 1990 . H.-U. Simon. On approximate solutions for combinatorial optimization problems. SIAM J. Discrete Math., 3(2):294-310, 1990.","journal-title":"SIAM J. Discrete Math."},{"key":"e_1_2_1_22_1","first-page":"147","volume-title":"SIGIR","author":"Yan H.","year":"2009","unstructured":"H. Yan , S. Ding , and T. Suel . Compressing term positions in web indexes . In SIGIR , pages 147 - 154 , 2009 . H. Yan, S. Ding, and T. Suel. Compressing term positions in web indexes. In SIGIR, pages 147-154, 2009."},{"key":"e_1_2_1_23_1","first-page":"401","volume-title":"WWW","author":"Yan H.","year":"2009","unstructured":"H. Yan , S. Ding , and T. Suel . Inverted index compression and query processing with optimized document ordering . In WWW , pages 401 - 410 , 2009 . H. Yan, S. Ding, and T. Suel. Inverted index compression and query processing with optimized document ordering. In WWW, pages 401-410, 2009."},{"key":"e_1_2_1_24_1","first-page":"387","volume-title":"WWW","author":"Zhang J.","year":"2008","unstructured":"J. Zhang , X. Long , and T. Suel . Performance of compressed inverted list caching in search engines . In WWW , pages 387 - 396 , 2008 . J. Zhang, X. Long, and T. Suel. Performance of compressed inverted list caching in search engines. In WWW, pages 387-396, 2008."},{"key":"e_1_2_1_25_1","volume-title":"ICDE, page 59","author":"Zukowski M.","year":"2006","unstructured":"M. Zukowski , S. H\u00e9man , N. Nes , and P. A. Boncz . Super-scalar ram-cpu cache compression . In ICDE, page 59 , 2006 . M. Zukowski, S. H\u00e9man, N. Nes, and P. A. Boncz. Super-scalar ram-cpu cache compression. In ICDE, page 59, 2006."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2536258.2536264","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:35:10Z","timestamp":1672223710000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2536258.2536264"}},"subtitle":["new full-text index for low space cost and efficient keyword search"],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":22,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2013,8,29]]}},"alternative-id":["10.14778\/2536258.2536264"],"URL":"https:\/\/doi.org\/10.14778\/2536258.2536264","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,8]]}}}