Stronger Lempel-Ziv Based Compressed Text Indexing ⋆ (2009)
Diego Arroyuelo, Gonzalo Navarro, Kunihiko Sadakane
Abstract. Given a text T[1..u] over an alphabet of size σ, the full-text search problem consists in finding the occ occurrences of a given pattern P[1..m] in T. In indexed text searching we build an...
Fully-Functional Static and Dynamic Succinct Trees (2009)
Sadakane, Kunihiko, Navarro, Gonzalo
We propose new succinct representations of ordinal trees, which have been studied extensively. It is known that any $n$-node static tree can be represented in $2n + \order(n)$ bits and various...
More Efficient Periodic Traversal in Anonymous Undirected Graphs (2009)
Czyzowicz, Jurek, Dobrev, Stefan, Gasieniec, Leszek, Ilcinkas, David, Jansson, Jesper, Klasing, Ralf, ...
We consider the problem of periodic graph exploration in which a mobile entity with (at most) constant memory, an agent, has to visit all $n$ nodes of an arbitrary undirected graph G in a periodic...
More Efficient Periodic Traversal in Anonymous Undirected Graphs (2009)
Czyzowicz, Jurek, Dobrev, Stefan, Gasieniec, Leszek, Ilcinkas, David, Jansson, Jesper, Klasing, Ralf, ...
We consider the problem of periodic graph exploration in which a mobile entity with (at most) constant memory, an agent, has to visit all $n$ nodes of an arbitrary undirected graph G in a periodic...
© 2005 Springer Science+Business Media, Inc. Rooted Maximum Agreement Supertrees 1 (2008)
Jesper Jansson, Kunihiko Sadakane, Wing-kin Sung
Abstract. Given a set T of rooted, unordered trees, where each Ti ∈ T is distinctly leaf-labeled by a set �(Ti) and where the sets �(Ti) may overlap, the maximum agreement supertree problem...
Toshiko Matsumoto, Kunihiko Sadakane, Hiroshi Imai, Takumi Okazaki
Today, more and more DNA sequences are becoming available. The information about DNA sequences are stored in molecular biology databases. The size and importance of these databases will be bigger and...
Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space (2008)
Jesper Jansson, Kunihiko Sadakane, Wing-kin Sung
Abstract. The dynamic trie is a fundamental data structure which finds applications in many areas. This paper proposes a compressed version of the dynamic trie data structure. Our data-structure is...
A Space and Time Efficient Algorithm for Constructing Compressed Suffix Arrays ∗ (2008)
Wing-kai Hon, Tak-wah Lam, Kunihiko Sadakane
With the first human DNA being decoded into a sequence of about 2.8 billion characters, many biological research has been centered on analyzing this sequence. Theoretically speaking, it is now...
Finding Short Right-Hand-on-the-Wall Walks in Graphs (2008)
Stefan Dobrev, Jesper Jansson, Kunihiko Sadakane, Wing-kin Sung
Abstract. We consider the problem of perpetual traversal by a single agent in an anonymous undirected graph G. Our requirements are: (1) deterministic algorithm, (2) each node is visited within O(n)...
The Pre-history and Future of the Block-Sorting Compression Algorithm (2008)
Mike Burrows, David Wheeler, Lee Butterman, Nasir Memon, Paolo Ferragina, Raffaele Giancarlo, ...
2
Kunihiko Sadakane, M. Burrows, D. J. Wheeler, A Block-sorting, Lossless Data, Compression Algorithms, ...
The Burrows-Wheeler Transform [1] (BWT) is the core technique that unifies text search and compression. Many self-indexing text indices use this technique [2, 7, 3]. In spite of its importance, there...
Abstract Dynamic Dictionary Matching and Compressed Suffix Trees (2008)
Ho-leung Chan, Wing-kai Hon, Tak-wah Lam, Kunihiko Sadakane
Recent breakthrough in compressed indexing data structures has reduced the space for indexing a text (or a collection of texts) of length n from O(n log n) bits to O(n) bits, while allowing very...
Indexing Huge Genome Sequences 1 Indexing Huge Genome Sequences for Solving Various Problems (2008)
Kunihiko Sadakane, Tetsuo Shibuya
Because of the increase in the size of genome sequence databases, the importance of indexing the sequences for fast queries grows. Suffix trees and suffix arrays are used for simple queries. However...
Abstract. We propose a fast and memory efficient algorithm for lexicographically sorting the suffixes of a string, a problem that has important applications in data compression as well as string...
Quantum computation in computational geometry (2008)
Kunihiko Sadakane, Norito Sugawara, Takeshi Tokuyama
We discuss applications of quantum computation to geometric data processing such as convex hulls, minimum enclosing balls, linear programming, and intersection problems. Technically, we apply...
Theory of Computing Systems (2008)
Abstract. We introduce new data structures for compressed suffix trees whose size are linear in the text size. The size is measured in bits; thus they occupy only O(n log|A|) bits for a text of...
Abstract. We propose a fast and memory e#cient algorithm for lexicographically sorting the su#xes of a string, a problem that has important applications in data compression as well as string...
Now the Block sorting compression [l] becomes common by its good balance of compression ratio and speed. It has another nice feature, which is the relation between encoding/decoding process and...
Indexing Huge Genome Sequences 1 Indexing Huge Genome Sequences for Solving Various Problems (2007)
Kunihiko Sadakane, Tetsuo Shibuya
Because of the increase in the size of genome sequence databases, the importance of indexing the sequences for fast queries grows. Su#x trees and su#x arrays are used for simple queries. However...
Abstract. We propose a fast and memory e#cient algorithm for lexicographically sorting the su#xes of a string, a problem that has important applications in data compression as well as string...
A compressed text database based on the compressed su#x array is proposed. The compressed su#x array of Grossi and Vitter occupies only O(n) bits for a text of length n; however it also uses the text...
PAPER Fast Algorithms for k-word Proximity Search (2007)
Kunihiko Sadakane, Hiroshi Imai, Regular Member
SUMMARY When we search from a huge amount of documents, we often specify several keywords and use conjunctive queries to narrow the result of the search. Though the searched
Improving the Speed of LZ77 Compression by Hashing and Su#x Sorting (2007)
Kunihiko Sadakane, Hiroshi Imai, Regular Member
SUMMARY Two new algorithms for improving the speed of the LZ77 compression are proposed. One is based on a new hashing algorithm named two-level hashing that enables fast longest match searching from...
Toshiko Matsumoto, Kunihiko Sadakane
Today, more and more DNA sequences are becoming available. The information about DNA sequences are stored in molecular biology databases. The size and importance of these databases will be bigger and...
Finding Meaningful Regions Containing Given Keywords from Large Text Collections (2007)
Kunihiko Sadakane, Hiroshi Imai
Introduction When we search a large text collection for documents we want, we will specify some keywords and we obtain documents containing the keywords. Because the search result contains many...
bits for a text of length n on an alphabet (2007)
We introduce new data structures for compressed su#x trees whose size are linear in the text size. The size is measured in bits; thus they occupy only O(n log
Succinct data structures for flexible text retrieval systems (2007)
University, Fukuoka, Japan. We propose succinct data structures for text retrieval systems supporting docu-ment listing queries and ranking queries based on the tf*idf (term frequency times inverse...
Ultra-succinct representation of ordered trees (2007)
Jesper Jansson, Kunihiko Sadakane, Wing-kin Sung
fixed universe with cardinality L is log L bits There exist two well-known succinct representations of ordered trees: BP (balanced parenthesis) [Munro, Raman 2001] and DFUDS (depth first unary degree...
Practical Entropy-Compressed Rank/Select Dictionary (2006)
Okanohara, Daisuke, Sadakane, Kunihiko
Rank/Select dictionaries are data structures for an ordered set $S \subset \{0,1,...,n-1\}$ to compute $\rank(x,S)$ (the number of elements in $S$ which are no greater than $x$), and $\select(i,S)$...
A Generic Search Strategy for Large-Scale Real-World Networks (2006)
Kurumida, Yuichi, Ogata, Tsukasa, Ono, Hirotaka, Sadakane, Kunihiko, Yamashita, Masafumi, 来見田, 裕一, ...
ACM International Conference Proceeding Series; Vol. 152 : Article No. 2
Reducing the space requirement of LZ-index (2006)
Arroyuelo, Diego, Navarro, Gonzalo, Sadakane, Kunihiko
The LZ-index is a compressed full-text self-index able to represent a text T-1...u, over an alphabet of size sigma = O(polylog(u)) and with k-th order empirical entropy H-k(T), using 4uH(k)(T) + o(u...
K.: Reducing the space requirement of LZ-Index (2006)
Diego Arroyuelo, Gonzalo Navarro, Kunihiko Sadakane
Abstract. The LZ-index is a compressed full-text self-index able to represent atext T 1...u, over an alphabet of size s = O(polylog(u)) and with k-th order em-pirical entropy H k(T), using 4uHk(T) +...
Efficient Algorithms for Constructing a Pyramid from a Terrain (2006)
CHUN, Jinhee, SADAKANE, Kunihiko, TOKUYAMA, Takeshi
In [5], the following pyramid construction problem was proposed: Given nonnegative valued functions ρ and μ in d variables, we consider the optimal pyramid maximizing the total parametric gain of...
Peak-Reducing Fitting of a Curve under the Lp Metric (2005)
Jinhee Chun, Kunihiko Sadakane, Takeshi Tokuyama, Masato Yuki
Given a function y f ðxÞ in one variable, we consider the problem of computing a k-peaked curve y ðxÞ minimizing the Lp distance between them. In other words, ðxÞ has at most k local peaks and...
Neighborhood Composition: A Parallelization of Local Search Algorithms (2004)
Handa, Yuichi, Ono, Hirotaka, Sadakane, Kunihiko, Yamashita, Masafumi, 半田, 祐一, 小野, 廣隆, ...
Recent Advances in Parallel Virtual Machine and Message Passing Interface
Veli Mäkinen, Gonzalo Navarro, Kunihiko Sadakane
Abstract. One of the most relevant succinct suffix array proposals in the literature is the Compressed Suffix Array (CSA) of Sadakane [ISAAC 2000]. The CSA needs n(H0 + O(log log σ)) bits of space,...
Constructing compressed suffix arrays with large alphabets (2003)
Wing-kai Hon, Kunihiko Sadakane
, and Wing-Kin Sung 3 1
Breaking a Time-and-Space Barrier in Constructing Full-Text Indices (2003)
Wing-kai Hon, Kunihiko Sadakane, Wing-kin Sung
Suffix trees and suffix arrays are the most prominent full-text indices, and their construction algorithms are well studied. It has been open for a long time whether these indices can be constructed...
Space-Economical Algorithms for Finding Maximal Unique Matches (2002)
Wing-kai Hon, Kunihiko Sadakane
Abstract. We show space-economical algorithms for finding maximal unique matches (MUM's) between two strings which are important in large scale genome sequence alignment problems. Our algorithms...
Succinct representations of LCP information and improvements in the compressed suffix arrays (2002)
We introduce two succinct data structures to solve various string problems. One is for storing the information of lcp, the longest common prefix, between suffixes in the suffix array, and the other...
A Space and Time Efficient Algorithm for Constructing Compressed Suffix Arrays (2002)
Tak-Wah Lam, Kunihiko Sadakane, Wing-Kin Sung, Siu-Ming Yiu
With the first Human DNA being decoded into a sequence of about 2.8 billion base pairs, many biological research has been centered on analyzing this sequence. Theoretically speaking, it is now...
Implementing the context tree weighting method for text compression (2000)
Kunihiko Sadakane, Takumi Okazaki, Hiroshi Imai
Context tree weighting method is a universal compression algorithm for FSMX sources. Though we expect that it will have good compression ratio in practice, it is di#cult to implement it and in many...
Unifying Text Search and Compression—Suffix Sorting, Block Sorting and Suffix Arrays (2000)
Today many electronic documents are available such as articles of newspapers, dictionaries, books, DNA sequences, etc. and they are stored in databases. We also have many documents on the Internet...
A compressed text database based on the compressed suffix array is proposed. The compressed su#x array of Grossi and Vitter occupies only O(n) bits for a text of length n; however it also uses the...
Text Retrieval by using k-word Proximity Search (1999)
Kunihiko Sadakane, Hiroshi Imai
When we search from a huge amount of documents, we often specify several keywords and use conjunctive queries to narrow the result of the search. Though the
he suffix array of the unified text. Our transformation is not permutation of alphabet followed by the original transformation but a combination of unification and the original transformation. From a...
Kunihiko Sadakane, Hiroshi Imai
A new text database management method for distributed cooperative environments is proposed, which can collect texts in distributed sites through a network of narrow bandwidth and enables fulltext...
On K-Word Proximity Search (1999)
Kunihiko Sadakane, Hiroshi Imai
this paper, we propose two algorithms for finding documents in which all given keywords appear in neighboring places. One is based on plane-sweep algorithm and the other is based on...
A Fast Algorithm for Making Suffix Arrays and for Burrows-Wheeler Transformation (1998)
We propose a fast and memory efficient algorithm for sorting suffixes of a text in lexicographic order. It is important to sort suffixes because an arrayof indexes of suffixes is called suffix array...
A Fast Algorithm for Making Suffix Arrays and for Burrows-Wheeler Transformation (1998)
We propose a fast and memory efficient algorithm for sorting suffixes of a text in lexicographic order. It is important to sort suffixes because an array of indexes of suffixes is called suffix array...
On Optimality of Variants of the Block Sorting Compression (1998)
the permuted string into many parts and encodes symbols using different arithmetic codes by the parts. Each part has symbols whose contexts are the same. If the permutation is random, the scheme is...
Recently block sorting compression scheme was developed and relation to statistical scheme was studied, but theoretical analysis of performance has not been studied well. Context sorting is a...
Comparison among Suffix Array Construction Algorithms (1997)
Introduction 1.1 Suffix array Today large databases become available, such as full text of newspapers or Web pages, and Genome sequences, therefore it is important to store them on memory for quick...
Many data compression schemes are developed nowadays and they are selected according to requirements, such as fast encoding, fast decoding, good compression performance, small amount of required...
this paper, an algorithm using two-level hash is proposed. Since longer strings are searched first, the search space is considerably reduced when they are found in the dictionary. The compression...
Recently block sorting compression scheme was developed and relation to statistical scheme was studied, but theoretical analysis of performance has not been studied well. Context sorting is a...
Output-size Sensitiveness of OBDD Construction Through Maximal Independent Set Problem (1995)
Kazuyoshi Hayase, Kunihiko Sadakane, Seiichiro Tani
. This paper investigates output-size sensitiveness of construction of OBDD by analyzing the maximal independent set problem of a graph, which would give several insights to efficient manipulation of...