{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T09:15:54Z","timestamp":1790846154713,"version":"4.1.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>\n                    We study\n                    <jats:italic>sequential dependencies<\/jats:italic>\n                    that express the semantics of data with ordered domains and help identify quality problems with such data. Given an interval\n                    <jats:italic>g<\/jats:italic>\n                    , we write\n                    <jats:italic>X<\/jats:italic>\n                    \u2192\n                    <jats:sub>g<\/jats:sub>\n                    <jats:italic>Y<\/jats:italic>\n                    to denote that the difference between the\n                    <jats:italic>Y<\/jats:italic>\n                    -attribute values of any two consecutive records, when sorted on\n                    <jats:italic>X<\/jats:italic>\n                    , must be in\n                    <jats:italic>g.<\/jats:italic>\n                    For example,\n                    <jats:italic>time<\/jats:italic>\n                    \u2192\n                    <jats:sub>(0,\u221e)<\/jats:sub>\n                    <jats:italic>sequence_number<\/jats:italic>\n                    indicates that sequence numbers are strictly increasing over time, whereas\n                    <jats:italic>sequence_number<\/jats:italic>\n                    \u2192\n                    <jats:sub>[4, 5]<\/jats:sub>\n                    <jats:italic>time<\/jats:italic>\n                    means that the time \"gaps\" between consecutive sequence numbers are between 4 and 5. Sequential dependencies express relationships between ordered attributes, and identify missing (gaps too large), extraneous (gaps too small) and out-of-order data.\n                  <\/jats:p>\n                  <jats:p>To make sequential dependencies applicable to real-world data, we relax their requirements and allow them to hold approximately (with some exceptions) and conditionally (on various subsets of the data). This paper proposes the notion of conditional approximate sequential dependencies and provides an efficient framework for discovering pattern tableaux, which are compact representations of the subsets of the data (i.e., ranges of values of the ordered attributes) that satisfy the underlying dependency. We present analyses of our proposed algorithms, and experiments on real data demonstrating the efficiency and utility of our framework.<\/jats:p>","DOI":"10.14778\/1687627.1687693","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T08:17:57Z","timestamp":1403597877000},"page":"574-585","source":"Crossref","is-referenced-by-count":76,"title":["Sequential dependencies"],"prefix":"10.14778","volume":"2","author":[{"given":"Lukasz","family":"Golab","sequence":"first","affiliation":[{"name":"AT&amp;T Labs--Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Howard","family":"Karloff","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs--Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Flip","family":"Korn","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs--Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avishek","family":"Saha","sequence":"additional","affiliation":[{"name":"University of Utah"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Divesh","family":"Srivastava","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs--Research"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/645480.655281"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.03.057"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1016028.1016032"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367920"},{"key":"e_1_2_1_5_1","first-page":"243","article-title":"Extending dependencies with conditions","volume":"2007","author":"Bravo L.","unstructured":"L. Bravo , W. Fan , and S. Ma . Extending dependencies with conditions . VLDB 2007 , 243 -- 254 . L. Bravo, W. Fan, and S. Ma. Extending dependencies with conditions. VLDB 2007, 243--254.","journal-title":"VLDB"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.032"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453980"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/582353.582375"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.208"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90103-X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90084-1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/588058.588098"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453900"},{"key":"e_1_2_1_14_1","volume-title":"SODA","author":"Gopalan P.","year":"2007","unstructured":"P. Gopalan , T. Jayram , R. Krauthgamer , and R. Kumar . Estimating the sortedness of a data stream . SODA 2007 , 318--327. P. Gopalan, T. Jayram, R. Krauthgamer, and R. Kumar. Estimating the sortedness of a data stream. SODA 2007, 318--327."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/232616.232692"},{"key":"e_1_2_1_16_1","first-page":"253","volume-title":"SODA","author":"Gupta A.","year":"2003","unstructured":"A. Gupta and F. Zane . Counting inversions in lists . SODA 2003 , pages 253 -- 254 . A. Gupta and F. Zane. Counting inversions in lists. SODA 2003, pages 253--254."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.2.100"},{"key":"e_1_2_1_18_1","volume-title":"The Computational complexity of machine learning","author":"Kearns M.","year":"1989","unstructured":"M. Kearns . The Computational complexity of machine learning . MIT Press , 1989 . M. Kearns. The Computational complexity of machine learning. MIT Press, 1989."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00028-U"},{"key":"e_1_2_1_20_1","first-page":"536","article-title":"Checks and balances: monitoring data quality problems in network traffic databases","volume":"2003","author":"Korn F.","unstructured":"F. Korn , S. Muthukrishnan , and Y. Zhu . Checks and balances: monitoring data quality problems in network traffic databases . VLDB 2003 , 536 -- 547 . F. Korn, S. Muthukrishnan, and Y. Zhu. Checks and balances: monitoring data quality problems in network traffic databases. VLDB 2003, 536--547.","journal-title":"VLDB"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009748302351"},{"key":"e_1_2_1_22_1","first-page":"697","article-title":"Streaming pattern discovery in multiple time-series","volume":"2005","author":"Papadimitriou S.","unstructured":"S. Papadimitriou , J. Sun , and C. Faloutsos . Streaming pattern discovery in multiple time-series . VLDB 2005 , 697 -- 708 . S. Papadimitriou, J. Sun, and C. Faloutsos. Streaming pattern discovery in multiple time-series. VLDB 2005, 697--708.","journal-title":"VLDB"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.1"},{"key":"e_1_2_1_24_1","volume-title":"Temporal dependencies with order constraints. Technical report","author":"Wijsen J.","year":"1999","unstructured":"J. Wijsen . Temporal dependencies with order constraints. Technical report , TimeCenter TR- 47, 1999 . J. Wijsen. Temporal dependencies with order constraints. Technical report, TimeCenter TR-47, 1999."},{"key":"e_1_2_1_25_1","first-page":"358","article-title":"Statstream: Statistical monitoring of thousands of data streams in real time","volume":"2002","author":"Zhu Y.","unstructured":"Y. Zhu and D. Shasha . Statstream: Statistical monitoring of thousands of data streams in real time . VLDB 2002 , 358 -- 369 . Y. Zhu and D. Shasha. Statstream: Statistical monitoring of thousands of data streams in real time. VLDB 2002, 358--369.","journal-title":"VLDB"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687693","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T06:29:50Z","timestamp":1672208990000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687693"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687693"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687693","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}