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: ha13e3c5b5cf005ef
Venue: SIGMOD
Year: 2019
Pagerank: 5.0623376e-05
Overall Rank: 10,196 | 31.45%
DOI: 10.1145/3299869.3300091

Incoming Non-self Citations Over Time

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 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,828	Toward Temporal Attribution Analytics in Dataflows	2026	VLDB	4.9793485e-05

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.0012092602
17	Provenance Semirings	2007	PODS	0.00059752575
22	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00055962491
67	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038009523
239	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.000235107
442	Differential dataflow	2013	CIDR	0.00018210463
591	Lineage Tracing for General Data Warehouse Transformations	2001	VLDB	0.00015888097
1,564	Titian: Data Provenance Support in Spark	2016	VLDB	0.00010222394
1,765	Putting Lipstick on Pig: Enabling Database-style Workflow Provenance	2012	VLDB	9.6955585e-05
1,827	Querying Data Provenance	2010	SIGMOD	9.5545888e-05
2,635	Big Data Analytics with Datalog Queries on Spark	2016	SIGMOD	8.1965216e-05
3,725	RAMP: A System for Capturing and Tracing Provenance in MapReduce Workflows	2011	VLDB	7.0702061e-05
4,940	Explaining Outputs in Modern Data Analytics	2016	VLDB	6.345789e-05
5,696	Debugging Big Data Analytics in Spark with BigDebug	2017	SIGMOD	6.033093e-05
7,297	FrogWild! – Fast PageRank Approximations on Graph Engines	2015	VLDB	5.5618017e-05
9,896	Graft: A Debugging Tool For Apache Giraph	2015	SIGMOD	5.1125679e-05
9,897	Auto-Approximation of Graph Computing	2014	VLDB	5.1125679e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,485	Optimizing Declarative Graph Queries at Large Scale	2019	SIGMOD
2	8,330	Computing How-Provenance for SPARQL Queries via Query Rewriting	2021	VLDB
3	444	Trinity: A Distributed Graph Engine on a Memory Cloud	2013	SIGMOD
4	10,828	Toward Temporal Attribution Analytics in Dataflows	2026	VLDB
5	1,913	Efficient Lineage Tracking For Scientific Workflows	2008	SIGMOD
6	2,843	Data Provenance at Internet Scale: Architecture, Experiences, and the Road Ahead	2017	CIDR
7	1,827	Querying Data Provenance	2010	SIGMOD
8	10,879	Computing Why-Provenance for Property Graph Queries	2026	VLDB
9	12,160	Ursprung: Provenance for Large-Scale Analytics Environments	2019	SIGMOD
10	8,583	OneProvenance: Efficient Extraction of Dynamic Coarse-Grained Provenance From Database Query Event Logs	2023	VLDB