Cited By
View all- Denzumi S(2018)Sequence Sentential Decision DiagramsCombinatorial Optimization and Applications10.1007/978-3-030-04651-4_40(592-606)Online publication date: 15-Dec-2018
Sequence binary decision diagram
Pages 61 - 80
Abstract
The manipulation of large sequence data is one of the most important problems in string processing. In this paper, we discuss a new data structure for storing and manipulating sets of strings, called Sequence Binary Decision Diagrams (sequence BDDs), which has recently been introduced by Loekito etal. (2010) as a descendant of both acyclic DFAs (ADFAs) and binary decision diagrams (BDDs). Sequence BDDs can compactly represent sets of sequences similarly to minimal ADFAs, and allow efficient set operations inherited from BDDs. We study fundamental properties of sequence BDDs, such as the characterization of minimal sequence BDDs by reduced sequence BDDs, non-trivial relationships between sizes of minimal sequence BDDs and minimal ADFAs, the complexities of minimization, Boolean set operations, and sequence BDD construction. We also show experimental results for real and artificial data sets.
References
[1]
A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
[2]
P. Beame, F.E. Fich, Optimal bounds for the predecessor problem and related problems, J. Comput. System Sci., 65 (2002) 38-72.
[3]
A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M.T. Chen, J.I. Seiferas, The smallest automaton recognizing the subwords of a text, Theoret. Comput. Sci., 40 (1985) 31-55.
[4]
R.E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Trans. Comput., 35 (1986) 677-691.
[5]
J. Bubenzer, Minimization of acyclic DFAs, in: Proceedings of the Prague Stringology Conference 2011, (PSC'11), Czech Technical University in Prague, 2011, pp. 132-146.
[6]
M. Crochemore, Transducers and repetitions, Theoret. Comput. Sci., 45 (1986) 63-86.
[7]
M. Crochemore, C. Hancart, T. Lecroq, Algorithms on Strings, Cambridge University Press, 2007.
[8]
M. Crochemore, W. Rytter, Jewels of Stringology, World Scientific, 2002.
[9]
J. Daciuk, S. Mihov, B.W. Watson, R. Watson, Incremental construction of minimal acyclic finite state automata, Comput. Linguist., 26 (2000) 3-16.
[10]
S. Denzumi, H. Arimura, S. Minato, Substring Indices Based on Sequence BDDs, Technical Report, TCS Technical Report Series A, TCS-TR-A-10-40, Division of Computer Science, Hokkaido University, 2010.
[11]
S. Denzumi, H. Arimura, S.i. Minato, Implementation of sequence bdds in erlang, in: Proceedings of the 10th ACM SIGPLAN Workshop on Erlang, Erlang'11, ACM, New York, NY, USA, 2011, pp. 90-91.
[12]
S. Denzumi, R. Yoshinaka, H. Arimura, S. ichi Minato, Notes on sequence binary decision diagrams: Relationship to acyclic automata and complexities of binary set operations, in: Proceedings of the Prague Stringology Conference, Czech Technical University in Prague, 2011, pp. 147-161.
[13]
S. Denzumi, R. Yoshinaka, H. Arimura, S. Minato, Efficient Algorithms on Sequence Binary Decision Diagrams for Manipulating Sets of Strings, Technical Report, TCS Technical Report Series A, TCS-TR-A-11-53, Division of Computer Science, Hokkaido University, 2011.
[14]
J.R. Driscoll, N. Sarnak, D. Sleator, R. Tarjan, Making data structures persistent, J. of Computer and System Science, 38 (1989) 38-86.
[15]
R. Giegerich, S. Kurtz, J. Stoye, Efficient implementation of lazy suffix trees, Softw. - Pract. Exp., 33 (2003) 1035-1049.
[16]
D. Gusfield, Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.
[17]
J.E. Hopcroft, An n log n algorithm for minimizing states in a finite automaton, Theory Mach. Comput. (1971) 189-196.
[18]
J.E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2006.
[19]
S. Inenaga, H. Hoshino, A. Shinohara, M. Takeda, S. Arikawa, Construction of the CDAWG for a trie, in: Proceedings of the Prague Stringology Conference 2001 (PSC'01), Czech Technical University, 2001, pp. 37-48.
[20]
H. Kaplan, Persistent data structures, in: Handbook on Data Structures and Applications, CRC Press, 2005.
[21]
H. Kaplan, C. Okasaki, R.E. Tarjan, Simple confluently persistent catenable lists, SIAM J. Comput., 30 (2000) 965-977.
[22]
D.E. Knuth, The Art of Computer Programming, vol. 4, fascicle 1, Bitwise Tricks & Techniques; Binary Decision Diagrams, Addison-Wesley, 2009.
[23]
J. Larson, Erlang for concurrent programming, Commun. ACM, 52 (2009) 48-56.
[24]
E. Loekito, J. Bailey, J. Pei, A binary decision diagram based approach for mining frequent subsequences, Knowl. Inf. Syst., 24 (2010) 235-268.
[25]
C.L. Lucchesi, T. Kowaltowski, Applications of finite automata representing large vocabularies, Softw. - Pract. Exp., 23 (1993) 15-30.
[26]
C.L. Lucchesi, T. Kowaltowski, J. Stolfi, Minimization of binary finite automata, J. Braz. Comput. Soc., 1 (1995) 5-11.
[27]
U. Manber, E.W. Myers, Suffix arrays: A new method for on-line string searches, SIAM J. Comput., 22 (1993) 935-948.
[28]
E.M. McCreight, A space-economical suffix tree construction algorithm, J. ACM, 23 (1976) 262-272.
[29]
S. Minato, Zero-suppressed BDDs and their applications, Softw. Tools Technol. Transf., 3 (2001) 156-170.
[30]
S. Minato, SAPPORO BDD Package, Division of Computer Science, Hokkaido University, 2011.
[31]
S. Minato, H. Arimura, Frequent pattern mining and knowledge indexing based on zero-suppressed BDDs, in: LNCS, vol. 4747, Springer, 2006, pp. 152-169.
[32]
M. Mohri, P. Moreno, E. Weinstein, Factor automata of automata and applications, in: LNCS, vol. 4783, Springer, 2007, pp. 168-179.
[33]
M. Mohri, M. Riley, R. Sproat, Algorithms for speech recognition and language processing, in: Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics, Morgan Kaufmann/ACL, 1996, pp. 231-238.
[34]
D. Perrin, Finite automata, in: Formal Models and Semantics, vol. B, Elsevier, 1990, pp. 1-57.
[35]
C.E. Shannon, A symbolic analysis of relay and switching circuits, Electr. Engrg., 57 (1938) 713-723.
[36]
Y. Tian, S. Tata, R.A. Hankins, J.M. Patel, Practical methods for constructing suffix trees, VLDB J., 14 (2005) 281-299.
[37]
B.W. Watson, A Taxonomy of Finite Automata Construction Algorithms, Technical Report, Computing Science Report 93/43, Department of Computing Science, Eindhoven University of Technology, 1993.
[38]
I. Wegener, Branching Programs and Binary Decision Diagrams-Theory and Applications, SIAM Monographs on Discrete Mathematics and Applications, SIAM, 2000.
[39]
R. Yoshinaka, J. Kawahara, S. Denzumi, H. Arimura, S. Minato, Counter Examples to the Conjecture on the Complexity of BDD Binary Operations, Technical Report, TCS Technical Report Series A, TCS-TR-A-11-52, Division of Computer Science, Hokkaido University, 2011.
- Sequence binary decision diagram
Recommendations
A binary decision diagram based approach for mining frequent subsequences
Sequential pattern mining is an important problem in data mining. State of the art techniques for mining sequential patterns, such as frequent subsequences, are often based on the pattern-growth approach, which recursively projects conditional ...
An nlogn algorithm for hyper-minimizing a (minimized) deterministic automaton
We improve a recent result [A. Badr, Hyper-minimization in O(n^2), Internat. J. Found. Comput. Sci. 20 (4) (2009) 735-746] for hyper-minimized finite automata. Namely, we present an O(nlogn) algorithm that computes for a given deterministic finite ...
Implementation of sequence BDDs in Erlang
Erlang '11: Proceedings of the 10th ACM SIGPLAN workshop on ErlangIn this paper, we present an implementation of Erlang of an efficient index structure, called Sequence Binary Decision Diagrams (SeqBDDs), for knowledge discovery in large sequence data. Recently, Loekito, Bailey, and Pei (KAIS, 2009) proposed SeqBDD. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier B.V.
Publisher
Elsevier Science Publishers B. V.
Netherlands
Publication History
Published: 30 October 2016
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 09 Mar 2025
Other Metrics
Citations
Cited By
View all- Denzumi S(2018)Sequence Sentential Decision DiagramsCombinatorial Optimization and Applications10.1007/978-3-030-04651-4_40(592-606)Online publication date: 15-Dec-2018