English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this paper we introduce the first efficient external-memory algorithm tocompute the bisimilarity equivalence classes of a directed acyclic graph (DAG).DAGs are commonly used to model data in a wide variety of practicalapplications, ranging from XML documents and data provenance models, to webtaxonomies and scientific workflows. In the study of efficient reasoning overmassive graphs, the notion of node bisimilarity plays a central role. Forexample, grouping together bisimilar nodes in an XML data set is the first stepin many sophisticated approaches to building indexing data structures forefficient XPath query evaluation. To date, however, only internal-memorybisimulation algorithms have been investigated. As the size of real-world DAGdata sets often exceeds available main memory, storage in external memorybecomes necessary. Hence, there is a practical need for an efficient approachto 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 graphand Sort(n) is the number of accesses to external memory needed to sort aninput of size n. We also study specializations of this algorithm to commonvariations of bisimulation for tree-structured XML data sets. We empiricallyverify efficient performance of the algorithms on graphs and XML documentshaving billions of nodes and edges, and find that the algorithms can processsuch 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 freelyavailable.

I/O efficient bisimulation partitioning on very large directed acyclic graphs