Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/14242
Title: | Efficient External-Memory Bisimulation on DAGs | Authors: | HELLINGS, Jelle Fletcher, George H. L. Haverkort, Herman |
Issue Date: | 2012 | Publisher: | ACM | Source: | Selçuk, Candan K.; Chen, Yi; Snodgrass, Richard T.; Gravano, Luis; Fuxman, Ariel (Ed.). SIGMOD'12 Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, p. 553-564 | Abstract: | In this paper we introduce the first efficient external-memory algorithm to compute the bisimilarity equivalence classes of a directed acyclic graph (DAG). DAGs are commonly used to model data in a wide variety of practical applications, ranging from XML documents and data provenance models, to web taxonomies and scientific workflows. In the study of efficient reasoning over massive graphs, the notion of node bisimilarity plays a central role. For example, grouping together bisimilar nodes in an XML data set is the first step in many sophisticated approaches to building indexing data structures for efficient XPath query evaluation. To date, however, only internal-memory bisimulation algorithms have been investigated. As the size of real-world DAG data sets often exceeds available main memory, storage in external memory becomes necessary. Hence, there is a practical need for an efficient approach to computing bisimulation in external memory. Our general algorithm has a worst-case IO-complexity of O(Sort(|N| + |E|)), where |N| and |E| are the numbers of nodes and edges, resp., in the data graph and Sort(n) is the number of accesses to external memory needed to sort an input of size n. We also study specializations of this algorithm to common variations of bisimulation for tree-structured XML data sets. We empirically verify efficient performance of the algorithms on graphs and XML documents having billions of nodes and edges, and find that the algorithms can process such graphs efficiently even when very limited internal memory is available. The proposed algorithms are simple enough for practical implementation and use, and open the door for further study of external-memory bisimulation algorithms. To this end, the full open-source C++ implementation has been made freely available. | Keywords: | bisimulation; graphs; external memory; I/O | Document URI: | http://hdl.handle.net/1942/14242 | ISBN: | 978-1-4503-1247-9 | DOI: | 10.1145/2213836.2213899 | Rights: | Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SIGMOD ’12, May 20–24, 2012, Scottsdale, Arizona, USA. Copyright 2012 ACM 978-1-4503-1247-9/12/05 ...$10.00. | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Show full item record
SCOPUSTM
Citations
15
checked on Sep 2, 2020
Page view(s)
54
checked on Sep 7, 2022
Download(s)
186
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.