{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:40Z","timestamp":1750308820045,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2011,7,1]],"date-time":"2011-07-01T00:00:00Z","timestamp":1309478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["1307"],"award-info":[{"award-number":["1307"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2011,7]]},"abstract":"<jats:p>As shown in a series of recent works, the HYB index is an alternative to the inverted index (INV) that enables very fast prefix searches, which in turn is the basis for fast processing of many other types of advanced queries, including autocompletion, faceted search, error-tolerant search, database-style select and join, and semantic search. In this work we show that HYB can be constructed at least as fast as INV, and often up to twice as fast. This is because HYB, by its nature, requires only a half-inversion of the data and allows an efficient in-place instead of the traditional merge-based index construction. We also pay particular attention to the cache efficiency of the in-memory posting accumulation, an issue that has not been addressed in previous work, and show that our simple multilevel posting accumulation scheme yields much fewer cache misses compared to related approaches. Finally, we show that HYB supports fast dynamic index updates more easily than INV.<\/jats:p>","DOI":"10.1145\/1993036.1993040","type":"journal-article","created":{"date-parts":[[2011,7,21]],"date-time":"2011-07-21T13:27:09Z","timestamp":1311254829000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast construction of the HYB index"],"prefix":"10.1145","volume":"29","author":[{"given":"Hannah","family":"Bast","sequence":"first","affiliation":[{"name":"Albert Ludwigs University, Albert Ludwigs University"}]},{"given":"Marjan","family":"Celikik","sequence":"additional","affiliation":[{"name":"Albert Ludwigs University, Albert Ludwigs University"}]}],"member":"320","published-online":{"date-parts":[[2011,7,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.304010"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868366.1868369"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277741.1277856"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148234"},{"volume-title":"Proceedings of the 3rd Biennial Conference on Innovative Data Systems Research (CIDR'07)","author":"Bast H.","key":"e_1_2_1_5_1"},{"volume-title":"Proceedings of the 18th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'99)","author":"Breslau L.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-007-9042-8"},{"key":"e_1_2_1_8_1","unstructured":"Buttcher S. and Clarke C. L. A. 2005. Memory management strategies for single-pass index construction in text retrieval systems. Tech. rep. School of Computer Science University of Waterloo Canada.  Buttcher S. and Clarke C. L. A. 2005. Memory management strategies for single-pass index construction in text retrieval systems. Tech. rep. School of Computer Science University of Waterloo Canada."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1529282.1529669"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03784-9_19"},{"key":"e_1_2_1_11_1","unstructured":"Cochran W. G. 1977. Sampling Techniques 3rd Ed. John Wiley & Sons Inc. New York NY.  Cochran W. G. 1977. Sampling Techniques 3rd Ed. John Wiley & Sons Inc. New York NY."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0051-5"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2275.357411"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796326"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00028-X"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_2_1_17_1","unstructured":"Grama A. Karypis G. Kumar V. and Gupta A. 2003. Introduction to Parallel Computing 2nd Ed. Addison Wesley Boston MA.   Grama A. Karypis G. Kumar V. and Gupta A. 2003. Introduction to Parallel Computing 2nd Ed. Addison Wesley Boston MA."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-4571(199012)41:8<581::AID-ASI4>3.0.CO;2-U"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/563857.563812"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.10268"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386118.1386125"},{"volume":"56","volume-title":"Proceedings of the 27th Australasian Conference on Computer Science (ACSC'04)","author":"Lester N.","key":"e_1_2_1_22_1"},{"volume-title":"Proceedings of the 1st Annual Symposium on Discrete Algorithms (SODA'90)","author":"Manber U.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","unstructured":"Middleton C. and Baeza-Yates R. 2007. A comparison of open source search engines. Tech. rep. http:\/\/wrg.upf.edu\/WRG\/dctos\/Middleton-Baeza.pdf.  Middleton C. and Baeza-Yates R. 2007. A comparison of open source search engines. Tech. rep. http:\/\/wrg.upf.edu\/WRG\/dctos\/Middleton-Baeza.pdf."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-4571(199508)46:7%3C537::AID-ASI7%3E3.0.CO;2-P"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/237496.237497"},{"volume-title":"Proceedings of the USENIX Annual Technical Conference. IEEE","author":"Popovici F. I.","key":"e_1_2_1_27_1"},{"volume-title":"Proceedings of 4th Annual Symposium on Document Analysis and Information Retrieval (SDAIR'95)","author":"Rogers W.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206331"},{"volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","year":"1999","author":"Witten I. H.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00239-3"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132956.1132959"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/296854.277632"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993036.1993040","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1993036.1993040","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:39Z","timestamp":1750278399000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993036.1993040"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["10.1145\/1993036.1993040"],"URL":"https:\/\/doi.org\/10.1145\/1993036.1993040","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"type":"print","value":"1046-8188"},{"type":"electronic","value":"1558-2868"}],"subject":[],"published":{"date-parts":[[2011,7]]},"assertion":[{"value":"2010-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}