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: 13435
Venue: VLDB
Year: 2024
Pagerank: 4.5036378e-05
Overall Rank: 8,472 | 41.07%
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,478	Incremental Detection of Denial Constraint Violations	2025	VLDB	4.3341665e-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.0032169493
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
192	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00035728858
242	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00031110894
555	Discovering Denial Constraints	2013	VLDB	0.00020254908
894	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015556428
1,557	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	0.00011392493
1,612	Detecting Data Errors: Where are we and what needs to be done?	2016	VLDB	0.00011142794
2,253	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	9.1937209e-05
2,296	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0776226e-05
2,483	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6864916e-05
3,006	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	7.7299363e-05
3,255	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3160522e-05
3,275	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.2897998e-05
3,467	Data Profiling – A Tutorial	2017	SIGMOD	7.069081e-05
3,571	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB	6.9580858e-05
3,831	Kamino: Constraint-Aware Differentially Private Data Synthesis	2021	VLDB	6.7181688e-05
4,273	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	6.3003864e-05
5,718	Conjunctive Queries with Comparisons	2022	SIGMOD	5.3552123e-05
6,437	Fundamentals of Order Dependencies	2012	VLDB	5.0631488e-05
6,477	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0488285e-05
6,690	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	4.9621556e-05
7,202	Conformance Constraint Discovery: Measuring Trust in Data-Driven Systems	2021	SIGMOD	4.8023314e-05
7,667	Fast Detection of Denial Constraint Violations	2022	VLDB	4.683767e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,706	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	4.1945683e-05
10,483	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD	4.1945683e-05
3,036	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	7.6735171e-05
9,478	Incremental Detection of Denial Constraint Violations	2025	VLDB	4.3341665e-05
9,646	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD	4.3109001e-05
8,836	Fast Approximate Denial Constraint Discovery	2023	VLDB	4.4393184e-05
2,253	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	9.1937209e-05
2,483	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	8.6864916e-05
7,667	Fast Detection of Denial Constraint Violations	2022	VLDB	4.683767e-05
6,477	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0488285e-05