Ariadne: Online Provenance for Big Graph Analytics

Summary: Ariadne provides online provenance capture and querying for vertex-centric graph analytics, where provenance can explode beyond the input graph due to iteration. A Datalog-based declarative language enables inline querying and execution monitoring, achieving ~1.3x overhead versus 8x for traditional approaches and enabling performance-aware analytics. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5684
Venue: SIGMOD
Year: 2019
Pagerank: 5.093636e-05
Overall Rank: 11,842 | 18.76%
DOI: 10.1145/3299869.3300091

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Vicky Papavasileiou (University of California San Diego)
2. Ken Yocum (Intuit; University of California San Diego)
3. Alin Deutsch (University of California San Diego)

BibTeX Citation

@inproceedings{papavasileiou_sigmod19,
        title = {{Ariadne: Online Provenance for Big Graph Analytics}},
        author = {Papavasileiou, Vicky and Yocum, Ken and Deutsch, Alin},
        series = {{SIGMOD} '19},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3299869.3300091},
        url = {https://dl.acm.org/doi/10.1145/3299869.3300091},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
17	Provenance Semirings	2007	PODS	0.00059843817
20	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00056944564
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
264	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00022980015
455	Differential dataflow	2013	CIDR	0.00018133241
585	Lineage Tracing for General Data Warehouse Transformations	2001	VLDB	0.00016139897
1,617	Titian: Data Provenance Support in Spark	2016	VLDB	0.00010209397
1,786	Putting Lipstick on Pig: Enabling Database-style Workflow Provenance	2012	VLDB	9.7690421e-05
1,912	Querying Data Provenance	2010	SIGMOD	9.4946756e-05
2,594	Big Data Analytics with Datalog Queries on Spark	2016	SIGMOD	8.3646367e-05
3,675	RAMP: A System for Capturing and Tracing Provenance in MapReduce Workflows	2011	VLDB	7.2096638e-05
4,845	Explaining Outputs in Modern Data Analytics	2016	VLDB	6.4818607e-05
5,570	Debugging Big Data Analytics in Spark with BigDebug	2017	SIGMOD	6.1693312e-05
7,171	FrogWild! – Fast PageRank Approximations on Graph Engines	2015	VLDB	5.6839455e-05
9,748	Graft: A Debugging Tool For Apache Giraph	2015	SIGMOD	5.227679e-05
9,749	Auto-Approximation of Graph Computing	2014	VLDB	5.227679e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,509	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD
2	1,366	Provenance for Generalized Map and Reduce Workflows	2011	CIDR
3	8,318	Optimizing Declarative Graph Queries at Large Scale	2019	SIGMOD
4	8,976	Computing How-Provenance for SPARQL Queries via Query Rewriting	2021	VLDB
5	436	Trinity: A Distributed Graph Engine on a Memory Cloud	2013	SIGMOD
6	1,871	Efficient Lineage Tracking For Scientific Workflows	2008	SIGMOD
7	2,807	Data Provenance at Internet Scale: Architecture, Experiences, and the Road Ahead	2017	CIDR
8	1,912	Querying Data Provenance	2010	SIGMOD
9	11,860	Ursprung: Provenance for Large-Scale Analytics Environments	2019	SIGMOD
10	8,950	OneProvenance: Efficient Extraction of Dynamic Coarse-Grained Provenance From Database Query Event Logs	2023	VLDB