Redirigiendo al acceso original de articulo en 15 segundos...
Inicio  /  Algorithms  /  Vol: 14 Par: 6 (2021)  /  Artículo
ARTÍCULO
TITULO

Storing Set Families More Compactly with Top ZDDs

Kotaro Matsuda    
Shuhei Denzumi and Kunihiko Sadakane    

Resumen

Zero-suppressed Binary Decision Diagrams (ZDDs) are data structures for representing set families in a compressed form. With ZDDs, many valuable operations on set families can be done in time polynomial in ZDD size. In some cases, however, the size of ZDDs for representing large set families becomes too huge to store them in the main memory. This paper proposes top ZDD, a novel representation of ZDDs which uses less space than existing ones. The top ZDD is an extension of the top tree, which compresses trees, to compress directed acyclic graphs by sharing identical subgraphs. We prove that navigational operations on ZDDs can be done in time poly-logarithmic in ZDD size, and show that there exist set families for which the size of the top ZDD is exponentially smaller than that of the ZDD. We also show experimentally that our top ZDDs have smaller sizes than ZDDs for real data.

 Artículos similares

       
 
T. Astakhova,S. Zueva,S. Krivonogov,A. Romanova     Pág. 103 - 108
The paper describes the design of a device for analyzing the release of propane vapors for vehicles running on gas engine fuel. The paper identifies the shortcomings of gas equipment, provides a rationale for the development, formulates the relevance, se... ver más

 
Dmitry Molchanov,Valentina Baranyuk     Pág. 55 - 59
The volumes of processed, analyzed and used data are increasing with the development of information technologies. In this regard, the issue of storing information is becoming more and more urgent.There are many possibilities for transferring, loading and... ver más

 
Hung Vo-Trung     Pág. 25 - 32
Currently, the Internet has given people the opportunity to access to human knowledge quickly and conveniently through various channels such as Web pages, social networks, digital libraries, portals... However, with the process of exchanging and updating... ver más

 
Denis Zolotariov     Pág. 47 - 55
The article is devoted to theoretical research and development of a distributed system of automated calculations and analysis based on cloud infrastructure. The subject of the research is theoretical and practical principles of building automated calcula... ver más

 
Athanasios Alexopoulos, Georgios Drakopoulos, Andreas Kanavos, Phivos Mylonas and Gerasimos Vonitsanos    
At the dawn of the 10V or big data data era, there are a considerable number of sources such as smart phones, IoT devices, social media, smart city sensors, as well as the health care system, all of which constitute but a small portion of the data lakes ... ver más
Revista: Algorithms