{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:52:27Z","timestamp":1773481947972,"version":"3.50.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,6]]},"abstract":"\n Pointwise order dependencies (PODs) are dependencies that specify ordering semantics on attributes of tuples. POD discovery refers to the process of identifying the set \u03a3 of valid and minimal PODs on a given data set\n D.<\/jats:italic>\n In practice\n D<\/jats:italic>\n is typically large and keeps changing, and it is prohibitively expensive to compute \u03a3 from scratch every time. In this paper, we make a first effort to study the incremental POD discovery problem, aiming at computing changes \u0394\u03a3 to \u03a3 such that \u03a3 \u2295 \u0394\u03a3 is the set of valid and minimal PODs on\n D<\/jats:italic>\n with a set \u0394\n D<\/jats:italic>\n of tuple insertion updates. (1) We first propose a novel indexing technique for inputs \u03a3 and\n D.<\/jats:italic>\n We give algorithms to build and choose indexes for \u03a3 and\n D<\/jats:italic>\n , and to update indexes in response to \u0394\n D.<\/jats:italic>\n We show that POD violations\n w.r.t.<\/jats:italic>\n \u03a3 incurred by \u0394\n D<\/jats:italic>\n can be efficiently identified by leveraging the proposed indexes, with a cost dependent on\n log<\/jats:italic>\n (|\n D<\/jats:italic>\n |). (2) We then present an effective algorithm for computing \u0394\u03a3, based on \u03a3 and identified violations caused by \u0394\n D.<\/jats:italic>\n The PODs in \u03a3 that become invalid on\n D<\/jats:italic>\n + \u0394\n D<\/jats:italic>\n are efficiently detected with the proposed indexes, and further new valid PODs on\n D<\/jats:italic>\n + \u0394\n D<\/jats:italic>\n are identified by refining those invalid PODs in \u03a3 on\n D<\/jats:italic>\n + \u0394\n D.<\/jats:italic>\n (3) Finally, using both real-life and synthetic datasets, we experimentally show that our approach outperforms the batch approach that computes from scratch, up to orders of magnitude.\n <\/jats:p>","DOI":"10.14778\/3401960.3401965","type":"journal-article","created":{"date-parts":[[2021,3,10]],"date-time":"2021-03-10T19:15:14Z","timestamp":1615403714000},"page":"1669-1681","source":"Crossref","is-referenced-by-count":13,"title":["Fast incremental discovery of pointwise order dependencies"],"prefix":"10.14778","volume":"13","author":[{"given":"Zijing","family":"Tan","sequence":"first","affiliation":[{"name":"Fudan University and ShanghaiKey Laboratory of Data Science"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ai","family":"Ran","sequence":"additional","affiliation":[{"name":"Fudan University and ShanghaiKey Laboratory of Data Science"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuai","family":"Ma","sequence":"additional","affiliation":[{"name":"Beihang University and Beijing Advanced Innovation Center for Big Data and Brain Computing"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sheng","family":"Qin","sequence":"additional","affiliation":[{"name":"Fudan University and ShanghaiKey Laboratory of Data Science"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,3,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0389-y"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3054772"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816721"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157800"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/645925.671357"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536262"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544847"},{"key":"e_1_2_1_9_1","first-page":"409","volume-title":"EDBT","author":"Consonni C.","year":"2019"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2371176"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366103"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.154"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196916"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364332"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90084-1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5929"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687693"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453900"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732240.2732248"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000045"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00013"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2831360.2831362"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0441-6"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3192965.3192968"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0412-3"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368293"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_1_28_1","first-page":"552","volume-title":"ECML PKDD 2018","author":"Rammelaere J.","year":"2018"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342638"},{"key":"e_1_2_1_30_1","first-page":"253","volume-title":"EDBT","author":"Schirmer P.","year":"2019"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/235968.233320"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000824.2000826"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3067421.3067422"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0510-0"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350241"},{"key":"e_1_2_1_36_1","first-page":"2014","article-title":"Business-intelligence queries with order dependencies in DB2","author":"Szlichta J.","year":"2014","journal-title":"EDBT"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556568"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3070647"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-18576-3_10"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3401960.3401965","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:10:46Z","timestamp":1672225846000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3401960.3401965"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":39,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["10.14778\/3401960.3401965"],"URL":"https:\/\/doi.org\/10.14778\/3401960.3401965","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,6]]}}}