{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:40:03Z","timestamp":1750221603729,"version":"3.41.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,1,4]],"date-time":"2017-01-04T00:00:00Z","timestamp":1483488000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Emerging Leaders in the Americas Program, Government of Canada"},{"name":"Fondecyt","award":["1-140796"],"award-info":[{"award-number":["1-140796"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2017,7,31]]},"abstract":"<jats:p>We introduce a new representation of the inverted index that performs faster ranked unions and intersections while using similar space. Our index is based on the treap data structure, which allows us to intersect\/merge the document identifiers while simultaneously thresholding by frequency, instead of the costlier two-step classical processing methods. To achieve compression, we represent the treap topology using different alternative compact data structures. Further, the treap invariants allow us to elegantly encode differentially both document identifiers and frequencies. We also show how to extend this representation to support incremental updates over the index. Results show that, under the tf-idf scoring scheme, our index uses about the same space as state-of-the-art compact representations, while performing up to 2--20 times faster on ranked single-word, union, or intersection queries. Under the BM25 scoring scheme, our index may use up to 40% more space than the others and outperforms them less frequently but still reaches improvement factors of 2--20 in the best cases. The index supporting incremental updates poses an overhead of 50%--100% over the static variants in terms of space, construction, and query time.<\/jats:p>","DOI":"10.1145\/3007186","type":"journal-article","created":{"date-parts":[[2017,1,4]],"date-time":"2017-01-04T17:02:36Z","timestamp":1483549356000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Inverted Treaps"],"prefix":"10.1145","volume":"35","author":[{"given":"Roberto","family":"Konow","sequence":"first","affiliation":[{"name":"Universidad Diego Portales and University of Chile, Santiago, Chile"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"University of Chile, Santiago, Chile"}]},{"given":"Charles L. A.","family":"Clarke","sequence":"additional","affiliation":[{"name":"University of Waterloo, ON, Canada"}]},{"given":"Alejandro","family":"L\u00f3pez-Ort\u00edz","sequence":"additional","affiliation":[{"name":"University of Waterloo, ON, Canada"}]}],"member":"320","published-online":{"date-parts":[[2017,1,4]]},"reference":[{"volume-title":"Proc. 2nd Annual European Symposium on Algorithms (ESA) (LNCS 855)","author":"Andersson A.","key":"e_1_2_1_1_1","unstructured":"A. Andersson and S. Nilsson . 1994. Faster searching in tries and quadtrees - an analysis of level compression . In Proc. 2nd Annual European Symposium on Algorithms (ESA) (LNCS 855) . 82--93. A. Andersson and S. Nilsson. 1994. Faster searching in tries and quadtrees - an analysis of level compression. In Proc. 2nd Annual European Symposium on Algorithms (ESA) (LNCS 855). 82--93."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/383952.383957"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:INRT.0000048490.99518.5c"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148235"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972900.9"},{"key":"e_1_2_1_6_1","unstructured":"N. Asadi and J. Lin. 2013. Fast incremental inverted indexing in main memory for web-scale collections. CoRR abs\/1305.0699 (2013). Retrieved from http:\/\/arxiv.org\/abs\/1305.0699. N. Asadi and J. Lin. 2013. Fast incremental inverted indexing in main memory for web-scale collections. CoRR abs\/1305.0699 (2013). Retrieved from http:\/\/arxiv.org\/abs\/1305.0699."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0005-6_7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"R. Baeza-Yates and B. Ribeiro-Neto. 2011. Modern Information Retrieval (2nd ed.). Addison-Wesley. R. Baeza-Yates and B. Ribeiro-Neto. 2011. Modern Information Retrieval (2nd ed.). Addison-Wesley.","DOI":"10.1145\/2009916.2010172"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_2"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498698.1564507"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/10719839_9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222017"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_10"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/277651.277660"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2012.08.003"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956944"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.149"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321440.1321546"},{"key":"e_1_2_1_20_1","volume-title":"Information Retrieval: Implementing and Evaluating Search Engines","author":"B\u00fcttcher S.","year":"2010","unstructured":"S. B\u00fcttcher , C. L. A. Clarke , and G. Cormack . 2010 . Information Retrieval: Implementing and Evaluating Search Engines . MIT Press . S. B\u00fcttcher, C. L. A. Clarke, and G. Cormack. 2010. Information Retrieval: Implementing and Evaluating Search Engines. MIT Press."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2012.42"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2507860"},{"key":"e_1_2_1_23_1","volume-title":"Search Engines: Information Retrieval in Practice. Pearson Education.","author":"Croft B.","year":"2009","unstructured":"B. Croft , D. Metzler , and T. Strohman . 2009 . Search Engines: Information Retrieval in Practice. Pearson Education. B. Croft, D. Metzler, and T. Strohman. 2009. Search Engines: Information Retrieval in Practice. Pearson Education."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75530-2_13"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_1"},{"volume-title":"Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 743--752","author":"Demaine E.","key":"e_1_2_1_26_1","unstructured":"E. Demaine , A. L\u00f3pez-Ortiz , and J. I. Munro . 2000. Adaptive set intersections, unions, and differences . In Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 743--752 . E. Demaine, A. L\u00f3pez-Ortiz, and J. I. Munro. 2000. Adaptive set intersections, unions, and differences. In Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 743--752."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2010048"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779759"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_28"},{"key":"e_1_2_1_30_1","volume-title":"Poster Proc.","volume":"38","author":"Gonz\u00e1lez R.","unstructured":"R. Gonz\u00e1lez , Sz. Grabowski , V. M\u00e4kinen , and G. Navarro . 2005. Practical implementation of rank and select queries . In Poster Proc. Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA). 27-- 38 . R. Gonz\u00e1lez, Sz. Grabowski, V. M\u00e4kinen, and G. Navarro. 2005. Practical implementation of rank and select queries. In Poster Proc. Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA). 27--38."},{"volume-title":"Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 841--850","author":"Grossi R.","key":"e_1_2_1_31_1","unstructured":"R. Grossi , A. Gupta , and J. Vitter . 2003. High-order entropy-compressed text indexes . In Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 841--850 . R. Grossi, A. Gupta, and J. Vitter. 2003. High-order entropy-compressed text indexes. In Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 841--850."},{"volume-title":"Information Retrieval\u2014Computational and Theoretical Aspects","author":"Heaps H.","key":"e_1_2_1_32_1","unstructured":"H. Heaps . 1978. Information Retrieval\u2014Computational and Theoretical Aspects . Academic Press . H. Heaps. 1978. Information Retrieval\u2014Computational and Theoretical Aspects. Academic Press."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34109-0_31"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2013.43"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484028.2484088"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2203"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2808194.2809477"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274812"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214021"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62034-6_35"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31265-6_2"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16321-0_33"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600428.2609615"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-4571(199610)47:10%3C749::AID-ASI3%3E3.0.CO;2-2"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2537734.2537744"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.7"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/564376.564416"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940876"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-4571(2000)9999:9999%3C::AID-ASI1591%3E3.0.CO;2-R"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063627"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277741.1277774"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2682862.2682870"},{"volume-title":"SIGIR 2012 Workshop on Open Source Information Retrieval. 40--47","author":"Trotman A.","key":"e_1_2_1_55_1","unstructured":"A. Trotman , X. Jia , and M. Crane . 2012. Towards an efficient and effective search engine . In SIGIR 2012 Workshop on Open Source Information Retrieval. 40--47 . A. Trotman, X. Jia, and M. Crane. 2012. Towards an efficient and effective search engine. In SIGIR 2012 Workshop on Open Source Information Retrieval. 40--47."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433409"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/358841.358852"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2009934"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.3.193"},{"key":"e_1_2_1_60_1","unstructured":"I. Witten A. Moffat and T. Bell. 1999. Managing Gigabytes (2nd ed.). Morgan Kaufmann. I. Witten A. Moffat and T. Bell. 1999. Managing Gigabytes (2nd ed.). Morgan Kaufmann."},{"volume-title":"Proc. 29th International Conference on Data Engineering (ICDE). 482--493","author":"Wu L.","key":"e_1_2_1_61_1","unstructured":"L. Wu , W. Lin , X. Xiao , and Y. Xu . 2013. LSII: An indexing structure for exact real-time search on microblogs . In Proc. 29th International Conference on Data Engineering (ICDE). 482--493 . L. Wu, W. Lin, X. Xiao, and Y. Xu. 2013. LSII: An indexing structure for exact real-time search on microblogs. In Proc. 29th International Conference on Data Engineering (ICDE). 482--493."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526764"},{"volume-title":"Human Behaviour and the Principle of Least Effort","author":"Zipf G.","key":"e_1_2_1_63_1","unstructured":"G. Zipf . 1949. Human Behaviour and the Principle of Least Effort . Addison-Wesley . G. Zipf. 1949. Human Behaviour and the Principle of Least Effort. Addison-Wesley."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132956.1132959"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3007186","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3007186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:41Z","timestamp":1750220621000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3007186"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,4]]},"references-count":63,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7,31]]}},"alternative-id":["10.1145\/3007186"],"URL":"https:\/\/doi.org\/10.1145\/3007186","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"type":"print","value":"1046-8188"},{"type":"electronic","value":"1558-2868"}],"subject":[],"published":{"date-parts":[[2017,1,4]]},"assertion":[{"value":"2016-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}