{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T08:48:46Z","timestamp":1779353326584,"version":"3.51.4"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2004,10,1]],"date-time":"2004-10-01T00:00:00Z","timestamp":1096588800000},"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. Inf. Syst."],"published-print":{"date-parts":[[2004,10]]},"abstract":"<jats:p>Search engines need to evaluate queries extremely fast, a challenging task given the quantities of data being indexed. A significant proportion of the queries posed to search engines involve phrases. In this article we consider how phrase queries can be efficiently supported with low disk overheads. Our previous research has shown that phrase queries can be rapidly evaluated using nextword indexes, but these indexes are twice as large as conventional inverted files. Alternatively, special-purpose phrase indexes can be used, but it is not feasible to index all phrases. We propose combinations of nextword indexes and phrase indexes with inverted files as a solution to this problem. Our experiments show that combined use of a partial nextword, partial phrase, and conventional inverted index allows evaluation of phrase queries in a quarter the time required to evaluate such queries with an inverted file alone; the additional space overhead is only 26% of the size of the inverted file.<\/jats:p>","DOI":"10.1145\/1028099.1028102","type":"journal-article","created":{"date-parts":[[2005,1,26]],"date-time":"2005-01-26T16:35:53Z","timestamp":1106757353000},"page":"573-594","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":56,"title":["Fast phrase querying with combined indexes"],"prefix":"10.1145","volume":"22","author":[{"given":"Hugh E.","family":"Williams","sequence":"first","affiliation":[{"name":"RMIT University, Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Justin","family":"Zobel","sequence":"additional","affiliation":[{"name":"RMIT University, Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dirk","family":"Bahle","sequence":"additional","affiliation":[{"name":"RMIT University, Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2004,10]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval","author":"Anh V. N.","unstructured":"Anh , V. N. , de Kretser , O. , and Moffat , A . 2001. Vector-space ranking with effective early termination . In Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval ( New Orleans, LA), W. B. Croft, D. J. Harper, D. H. Kraft, and J. Zobel, Eds. ACM Press, New York, NY, 35--42. 10.1145\/383952.383957 Anh, V. N., de Kretser, O., and Moffat, A. 2001. Vector-space ranking with effective early termination. In Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval (New Orleans, LA), W. B. Croft, D. J. Harper, D. H. Kraft, and J. Zobel, Eds. ACM Press, New York, NY, 35--42. 10.1145\/383952.383957"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the String Processing and Information Retrieval Symposium","author":"Bahle D.","unstructured":"Bahle , D. , Williams , H. E. , and Zobel , J . 2001a. Compaction techniques for nextword indexes . In Proceedings of the String Processing and Information Retrieval Symposium ( San Rafael, Chile). IEEE Computer Society Press, Los Alamitos, CA, 33--45. Bahle, D., Williams, H. E., and Zobel, J. 2001a. Compaction techniques for nextword indexes. In Proceedings of the String Processing and Information Retrieval Symposium (San Rafael, Chile). IEEE Computer Society Press, Los Alamitos, CA, 33--45."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Australasian Computer Science Conference, M. Oudshoorn, Ed. Conferences in Research and Practice in Information Technology. Australian Computer Society","author":"Bahle D.","unstructured":"Bahle , D. , Williams , H. E. , and Zobel , J . 2001b. Optimised phrase querying and browsing in text databases . In Proceedings of the Australasian Computer Science Conference, M. Oudshoorn, Ed. Conferences in Research and Practice in Information Technology. Australian Computer Society , Gold Coast, Australia, 11--19. Bahle, D., Williams, H. E., and Zobel, J. 2001b. Optimised phrase querying and browsing in text databases. In Proceedings of the Australasian Computer Science Conference, M. Oudshoorn, Ed. Conferences in Research and Practice in Information Technology. Australian Computer Society, Gold Coast, Australia, 11--19."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4573(02)00084-5"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Fifth RIAO International Conference \"Recherche d'Information Assistee par Ordinateur\" (Montreal P.Q., Canada). 388--400","author":"Clarke C. L.","unstructured":"Clarke , C. L. , Cormack , G. V. , and Tudhope , E. A . 1997. Relevance ranking for one- to three-term queries . In Proceedings of the Fifth RIAO International Conference \"Recherche d'Information Assistee par Ordinateur\" (Montreal P.Q., Canada). 388--400 . Clarke, C. L., Cormack, G. V., and Tudhope, E. A. 1997. Relevance ranking for one- to three-term queries. In Proceedings of the Fifth RIAO International Conference \"Recherche d'Information Assistee par Ordinateur\" (Montreal P.Q., Canada). 388--400."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval","author":"Croft W. B.","unstructured":"Croft , W. B. , Turtle , H. R. , and Lewis , D. D . 1991. The use of phrases and structured queries in information retrieval . In Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval ( Chicago, IL), A. Bookstein, Y. Chiaramella, G. Salton, and V. V. Raghavan, Eds. ACM Press, New York, NY, 32--45. 10.1145\/122860.122864 Croft, W. B., Turtle, H. R., and Lewis, D. D. 1991. The use of phrases and structured queries in information retrieval. In Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval (Chicago, IL), A. Bookstein, Y. Chiaramella, G. Salton, and V. V. Raghavan, Eds. ACM Press, New York, NY, 32--45. 10.1145\/122860.122864"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval","author":"de Lima E. F.","unstructured":"de Lima , E. F. and Pedersen , J. O . 1999. Phrase recognition and expansion for short, precision-biased queries based on a query log . In Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval ( Berkeley, CA), M. Hearst, F. Gey, and R. Tong, Eds. ACM Press, New York, NY, 145--152. 10.1145\/312624.312669 de Lima, E. F. and Pedersen, J. O. 1999. Phrase recognition and expansion for short, precision-biased queries based on a query log. In Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval (Berkeley, CA), M. Hearst, F. Gey, and R. Tong, Eds. ACM Press, New York, NY, 145--152. 10.1145\/312624.312669"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Gutwin C. Paynter G. Witten I. Nevill-Manning C. and Frank E. 1998. Improving browsing in digital libraries with keyphrase indexes. Decis. Supp. Syst. 27 1\/2 81--104. 10.1016\/S0167-9236(99)00038-X   Gutwin C. Paynter G. Witten I. Nevill-Manning C. and Frank E. 1998. Improving browsing in digital libraries with keyphrase indexes. Decis. Supp. Syst. 27 1\/2 81--104. 10.1016\/S0167-9236(99)00038-X","DOI":"10.1016\/S0167-9236(99)00038-X"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0306-4573(94)00047-7","article-title":"Overview of the second text retrieval conference (TREC-2)","volume":"31","author":"Harman D.","year":"1995","unstructured":"Harman , D. 1995 . Overview of the second text retrieval conference (TREC-2) . Inform. Process. Manage. 31 , 3, 271 -- 289 . Harman, D. 1995. Overview of the second text retrieval conference (TREC-2). Inform. Process. Manage. 31, 3, 271--289.","journal-title":"Inform. Process. Manage."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-4571(2000)9999:9999%3C::AID-ASI1607%3E3.3.CO;2-6"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval","author":"Lewis D. D.","unstructured":"Lewis , D. D. and Croft , W. B . 1990. Term clustering of syntactic phrases . In Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval ( Brussels, Belgium), J.-L. Vidick, Ed. ACM, New York, NY, 385--404. 10.1145\/96749.98244 Lewis, D. D. and Croft, W. B. 1990. Term clustering of syntactic phrases. In Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval (Brussels, Belgium), J.-L. Vidick, Ed. ACM, New York, NY, 385--404. 10.1145\/96749.98244"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/237496.237497"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the ACM Digital Libraries","author":"Paynter G. W.","unstructured":"Paynter , G. W. , Witten , I. H. , Cunningham , S. J. , and Buchanan , G . 2000. Scalable browsing for large collections: A case study . In Proceedings of the ACM Digital Libraries ( San Antonio, CA). ACM Press, New York, NY, 215--223. 10.1145\/336597.336666 Paynter, G. W., Witten, I. H., Cunningham, S. J., and Buchanan, G. 2000. Scalable browsing for large collections: A case study. In Proceedings of the ACM Digital Libraries (San Antonio, CA). ACM Press, New York, NY, 215--223. 10.1145\/336597.336666"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-4571(199610)47:10%3C749::AID-ASI3%3E3.3.CO;2-U"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval","author":"Saraiva P. C.","unstructured":"Saraiva , P. C. , Moura , E. S. , Ziviani , N. , Fonseca , R. , Meira , W. , Murta , C. , and Ribeiro-Neto , B . 2001. Rank-preserving two-level caching for scalable search engines . In Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval ( New Orleans, LA), W. B. Croft, D. J. Harper, D. H. Kraft, and J. Zobel, Eds. ACM Press, New York, NY, 51--58. 10.1145\/383952.383959 Saraiva, P. C., Moura, E. S., Ziviani, N., Fonseca, R., Meira, W., Murta, C., and Ribeiro-Neto, B. 2001. Rank-preserving two-level caching for scalable search engines. In Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval (New Orleans, LA), W. B. Croft, D. J. Harper, D. H. Kraft, and J. Zobel, Eds. ACM Press, New York, NY, 51--58. 10.1145\/383952.383959"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval","author":"Soboroff I.","year":"2002","unstructured":"Soboroff , I. 2002 . Does WT10g look like the Web? In Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval ( Tampere, Finland), M. Beaulieu, R. Baeza-Yates, S. H. Myaeng, and K. J\u00e4velin, Eds. ACM Press, New York, NY, 423--424. 10.1145\/564376.564475 Soboroff, I. 2002. Does WT10g look like the Web? In Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval (Tampere, Finland), M. Beaulieu, R. Baeza-Yates, S. H. Myaeng, and K. J\u00e4velin, Eds. ACM Press, New York, NY, 423--424. 10.1145\/564376.564475"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-4571(2000)9999:9999%3C::AID-ASI1591%3E3.3.CO;2-I"},{"key":"e_1_2_1_19_1","first-page":"1","article-title":"Selected results from a large study of Web searching: The Excite study","volume":"6","author":"Spink A.","year":"2000","unstructured":"Spink , A. and Xu , J. 2000 . Selected results from a large study of Web searching: The Excite study . Informat. Res. 6 , 1 . Available online at: http:\/\/InformationR.net\/ir\/6-1\/paper90.html. Spink, A. and Xu, J. 2000. Selected results from a large study of Web searching: The Excite study. Informat. Res. 6, 1. Available online at: http:\/\/InformationR.net\/ir\/6-1\/paper90.html.","journal-title":"Informat. Res."},{"key":"e_1_2_1_20_1","volume-title":"Overview of TREC 2001. In The Tenth Text REtrieval Conference (TREC","author":"Voorhees E. M.","year":"2001","unstructured":"Voorhees , E. M. and Harman , D. K . 2001 . Overview of TREC 2001. In The Tenth Text REtrieval Conference (TREC 2001 ), E. M. Voorhees and D. K. Harman, Eds. NIST Spec. pub. 500-250. National Institute of Standards and Technology, Gaithersburg, MD, 1--15. Voorhees, E. M. and Harman, D. K. 2001. Overview of TREC 2001. In The Tenth Text REtrieval Conference (TREC 2001), E. M. Voorhees and D. K. Harman, Eds. NIST Spec. pub. 500-250. National Institute of Standards and Technology, Gaithersburg, MD, 1--15."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1093\/comjnl\/42.3.193","article-title":"Compressing integers for fast file access","volume":"42","author":"Williams H. E.","year":"1999","unstructured":"Williams , H. E. and Zobel , J. 1999 . Compressing integers for fast file access . Comput. J. 42 , 3, 193 -- 201 . Williams, H. E. and Zobel, J. 1999. Compressing integers for fast file access. Comput. J. 42, 3, 193--201.","journal-title":"Comput. J."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Australasian Database Conference","author":"Williams H. E.","unstructured":"Williams , H. E. , Zobel , J. , and Anderson , P . 1999. What's next? Index structures for efficient phrase querying . In Proceedings of the Australasian Database Conference ( Auckland, New Zealand), M. Orlowska, Ed. Springer-Verlag, Berlin, Germany, 141--152. Williams, H. E., Zobel, J., and Anderson, P. 1999. What's next? Index structures for efficient phrase querying. In Proceedings of the Australasian Database Conference (Auckland, New Zealand), M. Orlowska, Ed. Springer-Verlag, Berlin, Germany, 141--152."},{"key":"e_1_2_1_23_1","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","author":"Witten I. H.","year":"1999","unstructured":"Witten , I. H. , Moffat , A. , and Bell , T. C . 1999 . Managing Gigabytes: Compressing and Indexing Documents and Images , 2 nd ed. Morgan Kaufmann, San Francisco , CA. Witten, I. H., Moffat, A., and Bell, T. C. 1999. Managing Gigabytes: Compressing and Indexing Documents and Images, 2nd ed. Morgan Kaufmann, San Francisco, CA.","edition":"2"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/281250.281256"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00239-3"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1028099.1028102","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1028099.1028102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:31:16Z","timestamp":1750264276000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1028099.1028102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,10]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,10]]}},"alternative-id":["10.1145\/1028099.1028102"],"URL":"https:\/\/doi.org\/10.1145\/1028099.1028102","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"value":"1046-8188","type":"print"},{"value":"1558-2868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,10]]},"assertion":[{"value":"2004-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}