超簡潔データ構造 Ultra-succinct Data Structures
-
- 定兼 邦彦 SADAKANE Kunihiko
- 九州大学大学院システム情報科学研究院情報工学部門 Graduate School of Information Science and Electrical Engineering, Kyushu University
この論文をさがす
著者
-
- 定兼 邦彦 SADAKANE Kunihiko
- 九州大学大学院システム情報科学研究院情報工学部門 Graduate School of Information Science and Electrical Engineering, Kyushu University
抄録
様々な種類の大規模データを活用するには,それを効率良く格納し,かつ高速な読込みと検索が行える必要があるが,これまでの格納方法ではすべてを満足することはできなかった.近年開発された簡潔データ構造により,データをコンパクトに格納し,かつ高速な問合せを行うことができるようになった.また,それを更に発展させ,様々なデータをある種のエントロピー限界まで圧縮しつつ同様のことができる超簡潔データ構造も提案された.これらについて,理論と応用に興味のある方を対象に,その定義と実現法を解説する.
収録刊行物
-
- 電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers
-
電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers 92(2), 97-104, 2009-02-01
一般社団法人電子情報通信学会
参考文献: 26件中 1-26件 を表示
-
1
- Linear pattern matching Algorithms
-
WEINER P.
Proceedings of the 14th IEEE Symposium on Switching and Automata Theory, 1973, 1-11, 1973
被引用文献1件
-
2
- Compressed suffix arrays and suffix trees with applications to text indexing and string matching
-
GROSSI R.
SIAM J. Comput. 35(2), 378-407, 2005
被引用文献1件
-
3
- Engineering the louds succinct tree representation
-
DELPRATT O.
Proc. WEA, 2006, 134-145, 2006
被引用文献1件
-
4
- Representing trees of higher degree
-
BENOIT D
Algorithmica 43(4), 275-292, 2005
被引用文献1件
-
5
- Ultrasuccinct representation of ordered trees
-
JANSSON J.
Proc. ACM-SIAM SODA, 2007, 575-584, 2007
被引用文献1件
-
6
- Succinct indexable dictionaries with applications to encoding k-aray trees and multisets
-
RAMAN R.
Proc. ACM-SIAM SODA, 2002, 233-242, 2002
被引用文献1件
-
7
- Binary trees having a given number of nodes with 0, 1 and 2 children
-
ROTE G.
Semin. Lothar. Comb., no. B 38(38b), 6, 1996
被引用文献1件
-
8
- Squeezing succinct data structures into entropy bounds
-
SADAKANE K.
Proc. ACM-SIAM SODA, 2006, 1230-1239, 2006
被引用文献1件
-
9
- A simple storage scheme for strings achieving entropy bounds
-
FERRAGINA P.
Theor. Comput. Sci. 372(1), 115-121, 2007
被引用文献1件
-
10
- New text indexing functionalities of the compressed suffix arrays
-
SADAKANE K.
J. Algorithms 48(2), 294-313, 2003
被引用文献1件
-
11
- High-order entropy-compressed text indexes
-
GROSSI R.
Proc. ACM-SIAM SODA, 2003, 841-850, 2003
被引用文献1件
-
12
- An alphabet-friendly FM-index
-
FERRAGINA P.
Proc. SPIRE, 2004, 150-160, 2004
被引用文献1件
-
13
- Compressed representations of sequences and full-text indexes
-
FERRAGINA P.
ACM Trans. Algorithms 3(2), 20, 2006
被引用文献1件
-
14
- Practical entropy-compressed rank/select dictionary
-
OKANOHARA D.
Proc. of Workshop on Algorithm Engineering and Experiments (ALENEX), 2007, 60-70, 2007
被引用文献1件
-
15
- Succinct representations of functions
-
MUNRO J. I.
Proceedings of ICALP, 2004, 1006-1015, 2004
被引用文献1件
-
16
- Dynamic entropy-compressed sequences and full-text indexes
-
MAKINEN V.
ACM Trans. Algorithms 4(3), 32, 2008
被引用文献1件
-
17
- The input/output complexity of sorting and related problems
-
AGGARWAL A.
Commun. ACM 31(9), 1116-1127, 1988
被引用文献3件
-
18
- Suffix arrays : a new method for on-line string searches
-
MANBER U.
SIAM J. Computing 22(5), 935-948, 1993
被引用文献57件
-
19
- Tables
-
MUNRO J. I.
Proceedings of the 16th Conference on Foundations of Software Technology and Computer Science (FSTTCS '96), 1996
被引用文献8件
-
20
- Succinct representation of balanced parentheses and static trees
-
MUNRO J. I.
SIAM Journal on Computing 31(3), 762-776, 2001
被引用文献19件
-
21
- Space-efficient Static Trees and Graphs
-
JACOBSON G.
Proc. IEEE FOCS, 1989, 1989
被引用文献18件
-
22
- A universal algorithm for data compression
-
ZIV J.
IEEE Trans. Inf. Theory IT-23(3), 337-343, 1977
DOI 被引用文献153件
-
23
- Compression of Individual Sequences via Variable Rate Coding
-
ZIV J.
IEEE Trans. Inform. Theory IT - 24, 5, 530-536, 1978
DOI 被引用文献144件
-
24
- Indexing compressed texts
-
FERRAGINA P.
Journal of ACM 52(4), 552-581, 2005
DOI 被引用文献9件
-
25
- DNA配列に適した圧縮全文索引
-
定兼 邦彦
電子情報通信学会技術研究報告. COMP, コンピュテーション 107(537), 33-37, 2008-03-03
参考文献12件 被引用文献1件
-
26
- 括弧列の簡単・簡潔な表現法
-
定兼 邦彦
電子情報通信学会技術研究報告. COMP, コンピュテーション 108(237), 33-40, 2008-10-03
参考文献28件 被引用文献2件
被引用文献: 1件中 1-1件 を表示
-
1
- 長期間のネットワーク計測のための高効率トラフィックデータ管理システム
-
有馬 亮 , 佐藤 彰洋 , 笹井 一人 , 北形 元 , 木下 哲男
電子情報通信学会技術研究報告. IN, 情報ネットワーク 109(189), 117-120, 2009-09-03
参考文献4件