Thesis or Dissertation Studies on Decision Diagrams for Efficient Manipulation of Sets and Strings

伝住, 周平

In many real-life problems, we are often faced with manipulating discrete structures.Manipulation of large discrete structures is one of the most important problems in computer science. For this purpose, a family of data structures calleddecision diagrams is used. The origin of the decision diagrams is binary decision diagram (BDD)proposed by Bryant in 1980s. BDD is a data structure to represent and manipulate Boolean functionsefficiently. As a variant of BDD, Minato proposedzero-suppressed binary decision diagram (ZDD). ZDD is a data structure for manipulating families of sets. In 2010, another descendant of BDD, sequence binary decision diagram (sequence BDD), is proposed byLoekito et al. This decision diagram represents sets of strings and allow computing string set operations, too.In this thesis, we study sequence BDD and ZDD. First, we show fundamental properties of sequence BDDs, such as the characterization of minimal sequence BDDs byreduced sequence BDDs, non-trivial relationships between sizes of minimal sequence BDDs and minimal Acyclic Deterministic Finite Automata, the complexities of minimization, Boolean set operations, and sequence BDD construction. Secondly, we alsodefine complete inverted files based on sequence BDD for directed acyclic graphs (DAGs).A complete inverted file is an abstract data type that provides various functions for text retrieval. We propose new complete inverted files calledSeqBDD-FPs for both texts and DAGs. We also present algorithms to construct them and to retrieve occurrence information from them. Thirdly, we pointed out the problem that is to build index for familiesof sets in order to store them compactly and allow fast searching. Then, we introduce DenseZDD, a compressed index for static ZDDs to solve a problem that current techniques for storing ZDDs require a huge amount of memory and membership operations are slow. Our technique not only indexes set families compactly but also executes fast membership operations. We also propose a hybrid method of DenseZDD and ordinaryZDDs to allow for dynamic indices.
Hokkaido University(北海道大学). 博士(情報科学)

Number of accesses :  

Other information