Efficient External-Memory Bisimulation on DAGs

Summary: First external-memory DAG bisimulation algorithm with IO complexity O(Sort(|N|+|E|)). Scales to billions of nodes/edges in XML/provenance; open-source C++ implementation provided for practical use. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h366c6da56efa67da
Venue: SIGMOD
Year: 2012
Pagerank: 6.5985379e-05
Overall Rank: 4,434 | 70.20%
DOI: 10.1145/2213836.2213899

Incoming Non-self Citations Over Time

Authors

1. Jelle Hellings (Hasselt University; Transnational University of Limburg)
2. George H.L. Fletcher (Eindhoven University of Technology)
3. Herman Haverkort (Eindhoven University of Technology)

BibTeX Citation

@inproceedings{hellings_sigmod12,
        title = {{Efficient External-Memory Bisimulation on DAGs}},
        author = {Hellings, Jelle and Fletcher, George H.L. and Haverkort, Herman},
        series = {{SIGMOD} '12},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2213836.2213899},
        url = {https://dl.acm.org/doi/10.1145/2213836.2213899},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
600	Massive Graph Triangulation	2013	SIGMOD	0.00015733864
12,536	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
741	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00014318553
2,526	Path Queries on Compressed XML	2003	VLDB	8.3393779e-05
3,490	Updates for Structure Indexes	2002	VLDB	7.2592618e-05
5,646	A Quest for Beauty and Wealth (or, Business Processes for Database Researchers)	2011	PODS	6.0505202e-05
6,073	Efficient Processing of XML Path Queries Using the Disk-based F&B Index	2005	VLDB	5.8935926e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,747	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS
2	3,509	Keyword Search on External Memory Data Graphs	2008	VLDB
3	6,140	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB
4	7,844	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD
5	1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB
6	2,680	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
7	7,641	Hash-based Subgraph Query Processing Method for Graph-structured XML Documents	2008	VLDB
8	1,555	Efficient Structural Joins on Indexed XML Documents	2002	VLDB
9	12,536	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD
10	3,490	Updates for Structure Indexes	2002	VLDB