{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T08:20:02Z","timestamp":1767860402369,"version":"3.49.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"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":["SIGMOD Rec."],"published-print":{"date-parts":[[2023,6,7]]},"abstract":"<jats:p>Threshold queries are an important class of queries that only require computing or counting answers up to a specified threshold value. To the best of our knowledge, threshold queries have been largely disregarded in the research literature, which is surprising considering how common they are in practice. We explore how such queries appear in practice and present a method that can be used to significantly improve the asymptotic bounds of their state-of-the-art evaluation algorithms. Our experimental evaluation of these methods shows order-of-magnitude performance improvements.<\/jats:p>","DOI":"10.1145\/3604437.3604452","type":"journal-article","created":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T22:22:01Z","timestamp":1686262921000},"page":"64-73","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Threshold Queries"],"prefix":"10.1145","volume":"52","author":[{"given":"Angela","family":"Bonifati","sequence":"first","affiliation":[{"name":"Lyon 1 Univ., Liris CNRS"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefania","family":"Dumbrava","sequence":"additional","affiliation":[{"name":"ENSIIE &amp; IP Paris"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Fletcher","sequence":"additional","affiliation":[{"name":"Eindhoven Univ. of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Hidders","sequence":"additional","affiliation":[{"name":"Birkbeck, Univ. of London"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Hofer","sequence":"additional","affiliation":[{"name":"University of Bayreuth"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[{"name":"University of Bayreuth"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Filip","family":"Murlak","sequence":"additional","affiliation":[{"name":"Univ. of Warsaw"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joshua","family":"Shinavier","sequence":"additional","affiliation":[{"name":"LinkedIn"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Slawek","family":"Staworko","sequence":"additional","affiliation":[{"name":"RelationalAI &amp; Univ. of Lille"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominik","family":"Tomaszuk","sequence":"additional","affiliation":[{"name":"Univ. of Bialystok"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Database Theory. Open source at https:\/\/github.com\/pdm-book\/community","author":"Arenas M.","year":"2022","unstructured":"M. Arenas , P. Barcel\u00b4o , L. Libkin , W. Martens , and A. Pieris . Database Theory. Open source at https:\/\/github.com\/pdm-book\/community , 2022 . M. Arenas, P. Barcel\u00b4o, L. Libkin, W. Martens, and A. Pieris. Database Theory. Open source at https:\/\/github.com\/pdm-book\/community, 2022."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1145\/3406325.3451014","volume-title":"Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021","author":"Arenas M.","year":"2021","unstructured":"M. Arenas , L. A. Croquevielle , R. Jayaram , and C. Riveros . When is approximate counting for conjunctive queries tractable? In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 , pages 1015 -- 1027 , New York, NY, USA , 2021 . Association for Computing Machinery. M. Arenas, L. A. Croquevielle, R. Jayaram, and C. Riveros. When is approximate counting for conjunctive queries tractable? In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 1015--1027, New York, NY, USA, 2021. Association for Computing Machinery."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1109\/C-CODE.2017.7918927","volume-title":"2017 International Conference on Communication, Computing and Digital Systems (C-CODE)","author":"Asif R.","year":"2017","unstructured":"R. Asif and M. A. Qadir . Enhancing the Nobel Prize schema . In 2017 International Conference on Communication, Computing and Digital Systems (C-CODE) , pages 193 -- 198 , Islamabad,Pakistan , 2017 . IEEE. R. Asif and M. A. Qadir. Enhancing the Nobel Prize schema. In 2017 International Conference on Communication, Computing and Digital Systems (C-CODE), pages 193--198, Islamabad,Pakistan, 2017. IEEE."},{"key":"e_1_2_1_4_1","first-page":"208","volume-title":"Proc. CSL 2007","volume":"4646","author":"Bagan G.","year":"2007","unstructured":"G. Bagan , A. Durand , and E. Grandjean . On acyclic conjunctive queries and constant delay enumeration . In Proc. CSL 2007 , volume 4646 of LNCS, pages 208 -- 222 , Berlin, Heidelberg , 2007 . Springer. G. Bagan, A. Durand, and E. Grandjean. On acyclic conjunctive queries and constant delay enumeration. In Proc. CSL 2007, volume 4646 of LNCS, pages 208--222, Berlin, Heidelberg, 2007. Springer."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_6_1","first-page":"1","volume-title":"Proc. MFCS 2019","volume":"138","author":"Berkholz C.","year":"2019","unstructured":"C. Berkholz and N. Schweikardt . Constant delay enumeration with fpt-preprocessing for conjunctive queries of bounded submodular width . In Proc. MFCS 2019 , volume 138 of LIPIcs, pages 58: 1 -- 58 :15, Dagstuhl, Germany , 2019 . Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik. C. Berkholz and N. Schweikardt. Constant delay enumeration with fpt-preprocessing for conjunctive queries of bounded submodular width. In Proc. MFCS 2019, volume 138 of LIPIcs, pages 58:1--58:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3510397.3510407"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313472"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","DOI":"10.1007\/s00778-019-00558-9","article-title":"An analytical study of large SPARQL query logs","author":"Bonifati A.","year":"2020","unstructured":"A. Bonifati , W. Martens , and T. Timm . An analytical study of large SPARQL query logs . VLDB J., 29(2--3):655--679 , 2020 . A. Bonifati, W. Martens, and T. Timm. An analytical study of large SPARQL query logs. VLDB J., 29(2--3):655--679, 2020.","journal-title":"VLDB J., 29(2--3):655--679"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253302"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/358769.358784"},{"key":"e_1_2_1_12_1","first-page":"263","volume-title":"SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, June 1--3, 1999","volume":"28","author":"Chaudhuri S.","year":"1999","unstructured":"S. Chaudhuri , R. Motwani , and V. R. Narasayya . On random sampling over joins. In A. Delis, C. Faloutsos, and S. Ghandeharizadeh, editors , SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, June 1--3, 1999 , Philadelphia, Pennsylvania, USA , volume 28 , pages 263 -- 274 , New York, NY, USA, 1999 . Association for Computing Machinery. S. Chaudhuri, R. Motwani, and V. R. Narasayya. On random sampling over joins. In A. Delis, C. Faloutsos, and S. Ghandeharizadeh, editors, SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, June 1--3, 1999, Philadelphia, Pennsylvania, USA, volume 28, pages 263--274, New York, NY, USA, 1999. Association for Computing Machinery."},{"key":"e_1_2_1_13_1","volume-title":"COVID-19 Knowledge Graph","year":"2021","unstructured":"CovidGraph. COVID-19 Knowledge Graph , 2021 . https:\/\/covidgraph.org\/. CovidGraph. COVID-19 Knowledge Graph, 2021. https:\/\/covidgraph.org\/."},{"key":"e_1_2_1_14_1","volume-title":"The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci., 329(1--3):315--323","author":"Dalmau V.","year":"2004","unstructured":"V. Dalmau and P. Jonsson . The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci., 329(1--3):315--323 , 2004 . V. Dalmau and P. Jonsson. The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci., 329(1--3):315--323, 2004."},{"key":"e_1_2_1_15_1","first-page":"307","volume-title":"Proc. PODS 2018","author":"Deep S.","year":"2018","unstructured":"S. Deep and P. Koutris . Compressed representations of conjunctive query results. In J. V. den Bussche and M. Arenas, editors , Proc. PODS 2018 , pages 307 -- 322 , New York, NY, USA , 2018 . ACM. S. Deep and P. Koutris. Compressed representations of conjunctive query results. In J. V. den Bussche and M. Arenas, editors, Proc. PODS 2018, pages 307--322, New York, NY, USA, 2018. ACM."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9543-y"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559890"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703427203"},{"key":"e_1_2_1_19_1","first-page":"3","volume-title":"Treewidth and hypertree width","author":"Gottlob G.","year":"2014","unstructured":"G. Gottlob , G. Greco , and F. Scarcello . Treewidth and hypertree width . In L. Bordeaux, Y. Hamadi, and P. Kohli, editors, Tractability : Practical Approaches to Hard Problems, pages 3 -- 38 . Cambridge University Press , 2014 . G. Gottlob, G. Greco, and F. Scarcello. Treewidth and hypertree width. In L. Bordeaux, Y. Hamadi, and P. Kohli, editors, Tractability: Practical Approaches to Hard Problems, pages 3--38. Cambridge University Press, 2014."},{"key":"e_1_2_1_20_1","first-page":"657","volume-title":"ACM Symposium on Theory of Computing (STOC)","author":"Grohe M.","year":"2001","unstructured":"M. Grohe , T. Schwentick , and L. Segoufin . When is the evaluation of conjunctive queries tractable ? In ACM Symposium on Theory of Computing (STOC) , pages 657 -- 666 , New York, NY, USA , 2001 . Association for Computing Machinery. M. Grohe, T. Schwentick, and L. Segoufin. When is the evaluation of conjunctive queries tractable? In ACM Symposium on Theory of Computing (STOC), pages 657--666, New York, NY, USA, 2001. Association for Computing Machinery."},{"key":"e_1_2_1_21_1","unstructured":"ICIJ. The Offshore Leaks Database 2022. https: \/\/github.com\/ICIJ\/offshoreleaks-data-packages.  ICIJ. The Offshore Leaks Database 2022. https: \/\/github.com\/ICIJ\/offshoreleaks-data-packages."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0128-2"},{"key":"e_1_2_1_23_1","first-page":"1","volume-title":"21st International Conference on Database Theory","volume":"98","author":"Kara A.","year":"2018","unstructured":"A. Kara and D. Olteanu . Covers of query results. In B. Kimelfeld and Y. Amsterdamer, editors , 21st International Conference on Database Theory , volume 98 of LIPIcs, pages 16: 1 -- 16 :22, Vienna, Austria , 2018 . Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik. A. Kara and D. Olteanu. Covers of query results. In B. Kimelfeld and Y. Amsterdamer, editors, 21st International Conference on Database Theory, volume 98 of LIPIcs, pages 16:1--16:22, Vienna, Austria, 2018. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik."},{"key":"e_1_2_1_24_1","volume-title":"Lyon","author":"Kr\u00a8otzsch M.","year":"2018","unstructured":"M. Kr\u00a8otzsch . Practical linked data access via SPARQL: The case of wikidata. In LDOW@ WWW, pages 1--10 , Lyon , France , 2018 . CEUR Workshop Proceedings. M. Kr\u00a8otzsch. Practical linked data access via SPARQL: The case of wikidata. In LDOW@ WWW, pages 1--10, Lyon, France, 2018. CEUR Workshop Proceedings."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0480-7"},{"key":"e_1_2_1_26_1","first-page":"376","volume-title":"International Semantic Web Conference (ISWC)","author":"Malyshev S.","year":"2018","unstructured":"S. Malyshev , M. Kr\u00a8otzsch , L. Gonz\u00b4alez , J. Gonsior , and A. Bielefeldt . Getting the most out of wikidata: Semantic technology usage in wikipedia's knowledge graph . In International Semantic Web Conference (ISWC) , pages 376 -- 394 , Cham , 2018 . Springer. S. Malyshev, M. Kr\u00a8otzsch, L. Gonz\u00b4alez, J. Gonsior, and A. Bielefeldt. Getting the most out of wikidata: Semantic technology usage in wikipedia's knowledge graph. In International Semantic Web Conference (ISWC), pages 376--394, Cham, 2018. Springer."},{"key":"e_1_2_1_27_1","volume-title":"Efficient top-k aggregation of ranked inputs. ACM Transactions on Database Systems (TODS), 32(3):19--es","author":"Mamoulis N.","year":"2007","unstructured":"N. Mamoulis , M. L. Yiu , K. H. Cheng , and D. W. Cheung . Efficient top-k aggregation of ranked inputs. ACM Transactions on Database Systems (TODS), 32(3):19--es , 2007 . N. Mamoulis, M. L. Yiu, K. H. Cheng, and D. W. Cheung. Efficient top-k aggregation of ranked inputs. ACM Transactions on Database Systems (TODS), 32(3):19--es, 2007."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1145\/3315507.3330196","volume-title":"Proceedings of the 17th ACM SIGPLAN International Symposium on Database Programming Languages, DBPL 2019","author":"Murlak F.","year":"2019","unstructured":"F. Murlak , J. Posiadala , and P. Susicki . On the semantics of Cypher's implicit group-by. In A. Cheung and K. Nguyen, editors , Proceedings of the 17th ACM SIGPLAN International Symposium on Database Programming Languages, DBPL 2019 , Phoenix, AZ, USA , June 23, 2019 , pages 59 -- 69 . ACM, 2019. F. Murlak, J. Posiadala, and P. Susicki. On the semantics of Cypher's implicit group-by. In A. Cheung and K. Nguyen, editors, Proceedings of the 17th ACM SIGPLAN International Symposium on Database Programming Languages, DBPL 2019, Phoenix, AZ, USA, June 23, 2019, pages 59--69. ACM, 2019."},{"key":"e_1_2_1_29_1","first-page":"281","volume-title":"VLDB","author":"Natsev A.","year":"2001","unstructured":"A. Natsev , Y.-C. Chang , J. R. Smith , C.-S. Li , and J. S. Vitter . Supporting incremental join queries on ranked inputs . In VLDB , volume 1 , pages 281 -- 290 , San Francisco, CA , USA, 2001 . Morgan Kaufmann A. Natsev, Y.-C. Chang, J. R. Smith, C.-S. Li, and J. S. Vitter. Supporting incremental join queries on ranked inputs. In VLDB, volume 1, pages 281--290, San Francisco, CA, USA, 2001. Morgan Kaufmann"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.012"},{"issue":"2","key":"e_1_2_1_32_1","first-page":"19","article-title":"TPC releases benchmark results on 65 systems","volume":"19","author":"Shanley K.","year":"1991","unstructured":"K. Shanley . TPC releases benchmark results on 65 systems . SIGMETRICS Perform. Evaluation Rev. , 19 ( 2 ): 19 -- 23 , 1991 . K. Shanley. TPC releases benchmark results on 65 systems. SIGMETRICS Perform. Evaluation Rev., 19(2):19--23, 1991.","journal-title":"SIGMETRICS Perform. Evaluation Rev."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.92917"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.1145\/2187980.2188242","volume-title":"Proceedings of the 21st International Conference on World Wide Web, WWW '12 Companion","author":"Vrandeci\u00b4c D.","year":"2012","unstructured":"D. Vrandeci\u00b4c . Wikidata : A new platform for collaborative data collection . In Proceedings of the 21st International Conference on World Wide Web, WWW '12 Companion , pages 1063 -- 1064 , New York, NY, USA , 2012 . Association for Computing Machinery. D. Vrandeci\u00b4c. Wikidata: A new platform for collaborative data collection. In Proceedings of the 21st International Conference on World Wide Web, WWW '12 Companion, pages 1063--1064, New York, NY, USA, 2012. Association for Computing Machinery."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355749"},{"key":"e_1_2_1_36_1","first-page":"82","volume-title":"Proc. VLDB 1981","author":"Yannakakis M.","year":"1981","unstructured":"M. Yannakakis . Algorithms for acyclic database schemes . In Proc. VLDB 1981 , pages 82 -- 94 , Cannes, France , 1981 . IEEE Computer Society. M. Yannakakis. Algorithms for acyclic database schemes. In Proc. VLDB 1981, pages 82--94, Cannes, France, 1981. IEEE Computer Society."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183739"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604437.3604452","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3604437.3604452","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:19Z","timestamp":1750178839000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604437.3604452"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,7]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6,7]]}},"alternative-id":["10.1145\/3604437.3604452"],"URL":"https:\/\/doi.org\/10.1145\/3604437.3604452","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2023,6,7]]},"assertion":[{"value":"2023-06-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}