乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T23:11:44Z","timestamp":1723072304700},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"European Union\u2019s Horizon 2020 research and innovation","award":["682588"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2020,9,30]]},"abstract":"We consider the problem of incrementally maintaining the triangle queries with arbitrary free variables under single-tuple updates to the input relations.<\/jats:p>\n We introduce an approach called IVM\u03f5 that exhibits a trade-off between the update time, the space, and the delay for the enumeration of the query result, such that the update time ranges from the square root to linear in the database size while the delay ranges from constant to linear time.<\/jats:p>\n IVM\u03f5 achieves Pareto worst-case optimality in the update-delay space conditioned on the Online Matrix-Vector Multiplication conjecture. It is strongly Pareto optimal for the triangle queries with no or three free variables and weakly Pareto optimal for the remaining triangle queries with one or two free variables.<\/jats:p>\n IVM\u03f5 recovers prior work such as the suboptimal classical view maintenance approach that uses delta query processing and the worst-case optimal approach that computes all triangles in a static database.<\/jats:p>","DOI":"10.1145\/3396375","type":"journal-article","created":{"date-parts":[[2020,7,7]],"date-time":"2020-07-07T12:33:48Z","timestamp":1594125228000},"page":"1-46","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Maintaining Triangle Queries under Updates"],"prefix":"10.1145","volume":"45","author":[{"given":"Ahmet","family":"Kara","sequence":"first","affiliation":[{"name":"University of Zurich, Switzerland"}]},{"given":"Hung Q.","family":"Ngo","sequence":"additional","affiliation":[{"name":"RelationalAI, Inc., Berkeley, CA"}]},{"given":"Milos","family":"Nikolic","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, UK"}]},{"given":"Dan","family":"Olteanu","sequence":"additional","affiliation":[{"name":"University of Zurich, Switzerland"}]},{"given":"Haozhe","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}]}],"member":"320","published-online":{"date-parts":[[2020,8,26]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545464"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839490.1839494"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_2_2_7_1","first-page":"1","article-title":"Answering UCQs under updates and in the presence of integrity constraints","volume":"8","author":"Berkholz Christoph","year":"2018","unstructured":"Christoph Berkholz , Jens Keppeler , and Nicole Schweikardt . 2018 . Answering UCQs under updates and in the presence of integrity constraints . In Proceedings of the ICDT. 8 : 1 \u2013 8 :19. DOI:10.4230\/LIPIcs.ICDT.2018.8 10.4230\/LIPIcs.ICDT.2018.8 Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2018. Answering UCQs under updates and in the presence of integrity constraints. In Proceedings of the ICDT. 8:1\u20138:19. DOI:10.4230\/LIPIcs.ICDT.2018.8","journal-title":"Proceedings of the ICDT."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_19"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0036-4"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2480856"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382577.2382581"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.06.020"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196979"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3381089.3381092"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the CSL. 189--202","author":"Durand Arnaud","year":"2011","unstructured":"Arnaud Durand and Yann Strozecki . 2011 . Enumeration complexity of logical query problems with second-order variables . In Proceedings of the CSL. 189--202 . DOI:10.4230\/LIPIcs.CSL.2011.189 10.4230\/LIPIcs.CSL.2011.189 Arnaud Durand and Yann Strozecki. 2011. Enumeration complexity of logical query problems with second-order variables. In Proceedings of the CSL. 189--202. DOI:10.4230\/LIPIcs.CSL.2011.189"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.44"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11533719_72"},{"key":"e_1_2_2_23_1","volume-title":"Counting triangles under updates in worst-case optimal time. CoRR abs\/1804.02780","author":"Kara Ahmet","year":"2018","unstructured":"Ahmet Kara , Hung Q. Ngo , Milos Nikolic , Dan Olteanu , and Haozhe Zhang . 2018. Counting triangles under updates in worst-case optimal time. CoRR abs\/1804.02780 ( 2018 ). Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2018. Counting triangles under updates in worst-case optimal time. CoRR abs\/1804.02780 (2018)."},{"key":"e_1_2_2_24_1","first-page":"1","article-title":"Counting triangles under updates in worst-case optimal time","volume":"4","author":"Kara Ahmet","year":"2019","unstructured":"Ahmet Kara , Hung Q. Ngo , Milos Nikolic , Dan Olteanu , and Haozhe Zhang . 2019 a. Counting triangles under updates in worst-case optimal time . In Proceedings of the ICDT. 4 : 1 \u2013 4 :18. DOI:10.4230\/LIPIcs.ICDT.2019.4 10.4230\/LIPIcs.ICDT.2019.4 Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2019a. Counting triangles under updates in worst-case optimal time. In Proceedings of the ICDT. 4:1\u20134:18. DOI:10.4230\/LIPIcs.ICDT.2019.4","journal-title":"Proceedings of the ICDT."},{"key":"e_1_2_2_25_1","volume-title":"Maintaining triangle queries under updates. CoRR abs\/2004.03716","author":"Kara Ahmet","year":"2020","unstructured":"Ahmet Kara , Hung Q. Ngo , Milos Nikolic , Dan Olteanu , and Haozhe Zhang . 2020. Maintaining triangle queries under updates. CoRR abs\/2004.03716 ( 2020 ). Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2020. Maintaining triangle queries under updates. CoRR abs\/2004.03716 (2020)."},{"key":"e_1_2_2_26_1","volume-title":"Trade-offs in static and dynamic evaluation of hierarchical queries. CoRR abs\/1907.01988","author":"Kara Ahmet","year":"2019","unstructured":"Ahmet Kara , Milos Nikolic , Dan Olteanu , and Haozhe Zhang . 2019b. Trade-offs in static and dynamic evaluation of hierarchical queries. CoRR abs\/1907.01988 ( 2019 ). Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2019b. Trade-offs in static and dynamic evaluation of hierarchical queries. CoRR abs\/1907.01988 (2019)."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0348-4"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2012.625260"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21840-3_39"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/646717.701895"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/3217510"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1949-09320-5"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902283"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183758"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_54"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2948896.2948899"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.72"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1283383.1283490"},{"key":"e_1_2_2_41_1","first-page":"3431","article-title":"On some fine-grained questions in algorithms and complexity","volume":"3","author":"Williams Virginia Vassilevska","year":"2018","unstructured":"Virginia Vassilevska Williams . 2018 . On some fine-grained questions in algorithms and complexity . In Proceedings of the ICM , Vol. 3. 3431 -- 3472 . DOI:10.1142\/9789813272880_0188 10.1142\/9789813272880_0188 Virginia Vassilevska Williams. 2018. On some fine-grained questions in algorithms and complexity. In Proceedings of the ICM, Vol. 3. 3431--3472. DOI:10.1142\/9789813272880_0188","journal-title":"Proceedings of the ICM"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194274133"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.04.005"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3396375","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T12:47:57Z","timestamp":1672577277000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3396375"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,26]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9,30]]}},"alternative-id":["10.1145\/3396375"],"URL":"https:\/\/doi.org\/10.1145\/3396375","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,26]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}