{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,14]],"date-time":"2026-10-14T06:41:09Z","timestamp":1791960069118,"version":"4.3.4"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:p>Denial Constraint (DC) is a well-established formalism that captures a wide range of integrity constraints commonly encountered, including candidate keys, functional dependencies, and ordering constraints, among others. Given their significance, there has been considerable research interest in achieving fast detection of DC violations, especially to support activities related to data exploration and preparation. Despite the significant advancements in the field, prior work exhibits notable limitations when confronted with large-scale datasets: the current state-of-the-art algorithm demonstrates a quadratic (worst-case) time and space complexity relative to the dataset's number of rows. In this paper, we establish a connection between orthogonal range search and DC violation detection. We then introduce Rapidash, a novel algorithm that demonstrates near-linear time and space complexity, representing a theoretical improvement over prior work. To validate the effectiveness of our algorithm, we conduct comprehensive evaluations on both open-source and real-world production datasets, with our production datasets notably being an order of magnitude larger than the datasets employed in prior studies. Our results reveal that Rapidash achieves up to 84\u00d7 faster performance compared to state-of-the-art approaches while also exhibiting superior scalability.<\/jats:p>","DOI":"10.14778\/3659437.3659454","type":"journal-article","created":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T12:22:27Z","timestamp":1717158147000},"page":"2009-2021","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Rapidash: Efficient Detection of Constraint Violations"],"prefix":"10.14778","volume":"17","author":[{"given":"Zifan","family":"Liu","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shaleen","family":"Deep","sequence":"additional","affiliation":[{"name":"Microsoft"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anna","family":"Fariha","sequence":"additional","affiliation":[{"name":"University of Utah"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fotis","family":"Psallidas","sequence":"additional","affiliation":[{"name":"Microsoft"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ashish","family":"Tiwari","sequence":"additional","affiliation":[{"name":"Microsoft"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avrilia","family":"Floratou","sequence":"additional","affiliation":[{"name":"Microsoft"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994518"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3054772"},{"key":"e_1_2_1_3_1","volume-title":"Data Profiling","author":"Abedjan Ziawasch","year":"2018","unstructured":"Ziawasch Abedjan, Lukasz Golab, Felix Naumann, and Thorsten Papenbrock. 2018. Data Profiling. Morgan & Claypool Publishers. Synthesis Lectures on Data Management (2018)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035315.ch36"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328920"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559929"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/356789.356797"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"e_1_2_1_10_1","unstructured":"Pouya Bisadi and Bradford G Nickerson. 2011. Orthogonal Range Search using a Distributed Computing Model.. In CCCG."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157800"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/290593.290596"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536262"},{"key":"e_1_2_1_14_1","volume-title":"Overmars","author":"de Berg Mark","year":"2008","unstructured":"Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. 2008. Computational geometry: algorithms and applications, 3rd Edition. Springer. https:\/\/www.worldcat.org\/oclc\/227584184","edition":"3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457400"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452795"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3467861.3467876"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00586-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389775"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_21_1","unstructured":"Joseph M. Hellerstein Jeffrey F. Naughton and Avi Pfeffer. 1995. Generalized Search Trees for Database Systems. Morgan Kaufmann. 562--573 pages. http:\/\/www.vldb.org\/conf\/1995\/P562.PDF"},{"key":"e_1_2_1_22_1","volume-title":"Ullman","author":"Hopcroft John E.","year":"1979","unstructured":"John E. Hopcroft and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages and Computation. Addison-Wesley."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00114-3"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564755"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3426865","article-title":"Functional aggregate queries with additive inequalities","volume":"45","author":"Khamis Mahmoud Abo","year":"2020","unstructured":"Mahmoud Abo Khamis, Ryan R Curtin, Benjamin Moseley, Hung Q Ngo, Xuan-Long Nguyen, Dan Olteanu, and Maximilian Schleich. 2020. Functional aggregate queries with additive inequalities. ACM Transactions on Database Systems (TODS) 45, 4 (2020), 1--41.","journal-title":"ACM Transactions on Database Systems (TODS)"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2967101"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2831360.2831362"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00676-3"},{"key":"e_1_2_1_29_1","volume-title":"Rapidash: Efficient Constraint Discovery via Rapid Verification. arXiv preprint arXiv:2309.12436","author":"Liu Zifan","year":"2023","unstructured":"Zifan Liu, Shaleen Deep, Anna Fariha, Fotis Psallidas, Ashish Tiwari, and Avrilia Floratou. 2023. Rapidash: Efficient Constraint Discovery via Rapid Verification. arXiv preprint arXiv:2309.12436 (2023)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594547"},{"key":"e_1_2_1_31_1","volume-title":"The design of dynamic data structures","author":"Overmars Mark H","unstructured":"Mark H Overmars. 1983. The design of dynamic data structures. Vol. 156. Springer Science & Business Media."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915203"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368293"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503595"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 1235--1244","author":"Pena Eduardo HM","year":"2020","unstructured":"Eduardo HM Pena, Edson R Lucas Filho, Eduardo C de Almeida, and Felix Naumann. 2020. Efficient detection of data dependency violations. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 1235--1244."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574254"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137631"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3392778"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350241"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517830"},{"key":"e_1_2_1_41_1","volume-title":"Applications of range query theory to relational data base join and selection operations. journal of computer and system sciences 52, 1","author":"Willard Dan E","year":"1996","unstructured":"Dan E Willard. 1996. Applications of range query theory to relational data base join and selection operations. journal of computer and system sciences 52, 1 (1996), 157--169."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3659437.3659454","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T12:31:41Z","timestamp":1717158701000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3659437.3659454"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4]]},"references-count":41,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["10.14778\/3659437.3659454"],"URL":"https:\/\/doi.org\/10.14778\/3659437.3659454","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,4]]},"assertion":[{"value":"2024-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}