Rapidash: Efficient Detection of Constraint Violations

Summary: Reduces denial-constraint (DC) violation detection to orthogonal range search and introduces Rapidash, achieving near-linear time and space (vs prior quadratic worst-case). Validations on large open-source and production datasets show up to 84× speedups and markedly better scalability. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13436
Venue: VLDB
Year: 2024
Pagerank: 4.4993203e-05
Overall Rank: 8,470 | 41.14%
DOI: 10.14778/3659437.3659454

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,480	Incremental Detection of Denial Constraint Violations	2025	VLDB	4.3300131e-05

Outgoing Citations (Sorted by Pagerank)

Showing 24 of 24 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032118946
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
192	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00035692958
242	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00031093647
556	Discovering Denial Constraints	2013	VLDB	0.00020214701
890	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015542177
1,403	Detecting Data Errors: Where are we and what needs to be done?	2016	VLDB	0.00012180046
1,556	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	0.00011383141
2,258	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	9.1804145e-05
2,298	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0746479e-05
2,484	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6737275e-05
3,009	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	7.7230513e-05
3,259	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3101573e-05
3,278	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.2858181e-05
3,473	Data Profiling – A Tutorial	2017	SIGMOD	7.0623537e-05
3,575	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB	6.9509846e-05
3,834	Kamino: Constraint-Aware Differentially Private Data Synthesis	2021	VLDB	6.713066e-05
4,271	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	6.2943273e-05
5,728	Conjunctive Queries with Comparisons	2022	SIGMOD	5.350072e-05
6,431	Fundamentals of Order Dependencies	2012	VLDB	5.058289e-05
6,470	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0439835e-05
6,691	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	4.9573939e-05
7,607	Conformance Constraint Discovery: Measuring Trust in Data-Driven Systems	2021	SIGMOD	4.6931274e-05
7,666	Fast Detection of Denial Constraint Violations	2022	VLDB	4.6792751e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,714	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	4.1905499e-05
10,493	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD	4.1905499e-05
3,034	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	7.6737281e-05
9,480	Incremental Detection of Denial Constraint Violations	2025	VLDB	4.3300131e-05
9,647	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD	4.3067693e-05
8,836	Fast Approximate Denial Constraint Discovery	2023	VLDB	4.4350633e-05
2,258	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	9.1804145e-05
2,484	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6737275e-05
7,666	Fast Detection of Denial Constraint Violations	2022	VLDB	4.6792751e-05
6,470	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0439835e-05