{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:15:09Z","timestamp":1750220109214,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,11,24]],"date-time":"2021-11-24T00:00:00Z","timestamp":1637712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"\u201cAlgorithms, Data Structures and Combinatorics for Machine Learning\u201d","award":["MIUR-PRIN 2017"],"award-info":[{"award-number":["MIUR-PRIN 2017"]}]},{"name":"OK-INSAID"},{"name":"MIUR-PON 2018","award":["ARS01_00917"],"award-info":[{"award-number":["ARS01_00917"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>Modern search services often provide multiple options to rank the search results, e.g., sort \u201cby relevance\u201d, \u201cby price\u201d or \u201cby discount\u201d in e-commerce. While the traditional rank by relevance effectively places the relevant results in the top positions of the results list, the rank by attribute could place many marginally relevant results in the head of the results list leading to poor user experience. In the past, this issue has been addressed by investigating the relevance-aware filtering problem, which asks to select the subset of results maximizing the relevance of the attribute-sorted list. Recently, an exact algorithm has been proposed to solve this problem optimally. However, the high computational cost of the algorithm makes it impractical for the Web search scenario, which is characterized by huge lists of results and strict time constraints. For this reason, the problem is often solved using efficient yet inaccurate heuristic algorithms. In this article, we first prove the performance bounds of the existing heuristics. We then propose two efficient and effective algorithms to solve the relevance-aware filtering problem. First, we propose OPT-Filtering, a novel exact algorithm that is faster than the existing state-of-the-art optimal algorithm. Second, we propose an approximate and even more efficient algorithm, \u03f5-Filtering, which, given an allowed approximation error \u03f5, finds a (1-\u03f5)\u2013optimal filtering, i.e., the relevance of its solution is at least (1-\u03f5) times the optimum. We conduct a comprehensive evaluation of the two proposed algorithms against state-of-the-art competitors on two real-world public datasets. Experimental results show that OPT-Filtering achieves a significant speedup of up to two orders of magnitude with respect to the existing optimal solution, while \u03f5-Filtering further improves this result by trading effectiveness for efficiency. In particular, experiments show that \u03f5-Filtering can achieve quasi-optimal solutions while being faster than all state-of-the-art competitors in most of the tested configurations.<\/jats:p>","DOI":"10.1145\/3477982","type":"journal-article","created":{"date-parts":[[2021,11,24]],"date-time":"2021-11-24T18:26:25Z","timestamp":1637778385000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast Filtering of Search Results Sorted by Attribute"],"prefix":"10.1145","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3183-334X","authenticated-orcid":false,"given":"Franco Maria","family":"Nardini","sequence":"first","affiliation":[{"name":"ISTI-CNR, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6753-3149","authenticated-orcid":false,"given":"Roberto","family":"Trani","sequence":"additional","affiliation":[{"name":"ISTI-CNR, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9830-3936","authenticated-orcid":false,"given":"Rossano","family":"Venturini","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,11,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600428.2609627"},{"key":"e_1_2_1_2_1","volume-title":"Ribeiro-Neto","author":"Baeza-Yates Ricardo A.","year":"2011","unstructured":"Ricardo A. Baeza-Yates and Berthier A . Ribeiro-Neto . 2011 . Modern Information Retrieval - the Concepts and technology behind Search, (2nd. ed.). Pearson Education Ltd ., Harlow, England. Ricardo A. Baeza-Yates and Berthier A. Ribeiro-Neto. 2011. Modern Information Retrieval - the Concepts and technology behind Search, (2nd. ed.). Pearson Education Ltd., Harlow, England."},{"key":"e_1_2_1_3_1","volume-title":"Baeza-Yates","author":"Cambazoglu Berkant Barla","year":"2011","unstructured":"Berkant Barla Cambazoglu and Ricardo A . Baeza-Yates . 2011 . Scalability challenges in web search engines. In Advanced Topics in Information Retrieval. Vol. 33 . Springer , 27\u201350. Berkant Barla Cambazoglu and Ricardo A. Baeza-Yates. 2011. Scalability challenges in web search engines. In Advanced Topics in Information Retrieval. Vol. 33. Springer, 27\u201350."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806471"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052659"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1614191"},{"key":"e_1_2_1_7_1","first-page":"33","article-title":"Book review: Ensemble methods: Foundations and algorithms","volume":"13","author":"den Poel Dirk Van","year":"2012","unstructured":"Dirk Van den Poel . 2012 . Book review: Ensemble methods: Foundations and algorithms . IEEE Intelligent Informatics Bulletin 13 , 1 (2012), 33 \u2013 34 . Dirk Van den Poel. 2012. Book review: Ensemble methods: Foundations and algorithms. IEEE Intelligent Informatics Bulletin 13, 1 (2012), 33\u201334.","journal-title":"IEEE Intelligent Informatics Bulletin"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tele.2017.09.004"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/582415.582418"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600428.2609572"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646032"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2488217"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 23rd Text Retrieval Conference. 500-308","author":"Lin Jimmy","year":"2014","unstructured":"Jimmy Lin , Yulu Wang , Miles Efron , and Garrick Sherman . 2014 . Overview of the TREC-2014 microblog track . In Proceedings of the 23rd Text Retrieval Conference. 500-308 . Jimmy Lin, Yulu Wang, Miles Efron, and Garrick Sherman. 2014. Overview of the TREC-2014 microblog track. In Proceedings of the 23rd Text Retrieval Conference. 500-308."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1561\/1500000016"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766462.2767755"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1416950.1416952"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3331184.3331227"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3240323.3240356"},{"key":"e_1_2_1_19_1","article-title":"Meta search ranking strategies","volume":"976","author":"Patel Mr Biraj","year":"2011","unstructured":"Mr Biraj Patel and Dr Dipti Shah . 2011 . Meta search ranking strategies . International Journal of Information and Computing Technology 976 , 5999 (2011), 24\u201325. Mr Biraj Patel and Dr Dipti Shah. 2011. Meta search ranking strategies. International Journal of Information and Computing Technology 976, 5999 (2011), 24\u201325.","journal-title":"International Journal of Information and Computing Technology"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-009-9123-y"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766462.2767822"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the SIGIR 2018 Workshop on eCommerce Co-located with the 41st International ACM SIGIR Conference on Research and Development in Information Retrieval","volume":"2319","author":"Trotman Andrew","year":"2018","unstructured":"Andrew Trotman , Surya Kallumadi , and Jon Degenhardt . 2018 . High accuracy recall task . In Proceedings of the SIGIR 2018 Workshop on eCommerce Co-located with the 41st International ACM SIGIR Conference on Research and Development in Information Retrieval , Vol. 2319 . Andrew Trotman, Surya Kallumadi, and Jon Degenhardt. 2018. High accuracy recall task. In Proceedings of the SIGIR 2018 Workshop on eCommerce Co-located with the 41st International ACM SIGIR Conference on Research and Development in Information Retrieval, Vol. 2319."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning","volume":"97","author":"Vorobev Aleksandr","year":"2019","unstructured":"Aleksandr Vorobev , Aleksei Ustimenko , Gleb Gusev , and Pavel Serdyukov . 2019 . Learning to select for a predefined ranking . In Proceedings of the 36th International Conference on Machine Learning , Vol. 97 . PMLR, 6477\u20136486. Aleksandr Vorobev, Aleksei Ustimenko, Gleb Gusev, and Pavel Serdyukov. 2019. Learning to select for a predefined ranking. In Proceedings of the 36th International Conference on Machine Learning, Vol. 97. PMLR, 6477\u20136486."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 26th Annual JMLR Conference on Learning Theory. 25\u201354","author":"Wang Yining","year":"2013","unstructured":"Yining Wang , Liwei Wang , Yuanzhi Li , Di He , and Tie-Yan Liu . 2013 . A theoretical analysis of NDCG type ranking measures . In Proceedings of the 26th Annual JMLR Conference on Learning Theory. 25\u201354 . Yining Wang, Liwei Wang, Yuanzhi Li, Di He, and Tie-Yan Liu. 2013. A theoretical analysis of NDCG type ranking measures. In Proceedings of the 26th Annual JMLR Conference on Learning Theory. 25\u201354."}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477982","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3477982","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:38Z","timestamp":1750183838000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477982"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,24]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3477982"],"URL":"https:\/\/doi.org\/10.1145\/3477982","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"type":"print","value":"1046-8188"},{"type":"electronic","value":"1558-2868"}],"subject":[],"published":{"date-parts":[[2021,11,24]]},"assertion":[{"value":"2020-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}