In this paper, we prove that the odd-even transposition sort is size-optimal and depth-optimal among stable standard sorting networks. While the best known lower bound on the size of stable sorting networks with n inputs is Ω( n log n ), the odd-even transposition sort uses Θ( n 2 ) comparators, leaving an asymptotic gap. Our result provides a partial resolution of this gap by establishing optimality within stable standard sorting networks, a restricted class of stable sorting networks in which all comparators have a consistent orientation. This result follows from a structural characterization of this class, showing that such networks can be reduced to primitive sorting networks up to the removal of redundant comparisons. The proof is elementary and relies on the 0–1 principle.

Erdős and West (Discrete Mathematics’85) considered the class of n vertex intersection graphs which have a d-dimensional t-representation (also called a t,d −intersection representation), that is, each vertex of a graph in the class has an associated set consisting of at most t d -dimensional axis-parallel boxes. In particular, for a graph G and for each d ≥ 1, they consider i d ( G ) to be the minimum t for which G has such a representation. For fixed t and d , they consider the class of n vertex labeled graphs for which i d ( G ) ≤ t , and prove an upper bound of $\left( {2nt + \frac{1}{2}} \right)d\log n - \left( {n - \frac{1}{2}} \right)d\log (4\pi t)$ on the logarithm of size of the class. In this work, for fixed t and d we consider the class of n vertex unlabeled graphs which have a d -dimensional t -representation, denoted by ${\mathcal{G}_{t,d}}$ . We address the problem of designing a succinct data structure for the class ${\mathcal{G}_{t,d}}$ in an attempt to generalize the relatively recent results on succinct data structures for interval graphs (Algorithmica’21). Let ${\mathcal{G}_t}{\text{and}}{\mathcal{G}_d}$ be the class of graphs with bounded interval number and bounded boxicity obtained by setting d = 1 and t = 1 in ${\mathcal{G}_{t,d}}$ , respectively. We have the following results:

We propose a space-efficient index, called τλ-index, for locating rare patterns among similar strings, which has potential usage in drug discovery. Experiments are conducted on real data to compare our index with the state-of-the-art r-index.

Given a string S over an alphabet of size $\sigma$, we consider practical implementations of extended compressed RAM on S, which supports access, replace, lnsert, and delete operations on S while maintaining S in compressed form. In this paper, we proposed two implementations where each of them is based on the compressed RAM of Jansson et al. [ICALP 2012], and Grossi et al. [ICALP 2013], respectively. Experimental results show that our implementations support the operations efficiently while keeping the space proportional to the entropy of the input during the updates.

We consider the problem of designing space-efficient data structures for unlabelled path graphs with$n$vertices while supporting basic navigational queries such as degree, adjacency, and neighborhood queries efficiently. We provide two solutions for this problem. Our first data structure is succinct and occupies$n\log n+o(n\log n)$bits while answering adjacency query in$O(\log n)$time, and neighborhood and degree queries in$O(d\log^{2}n)$time where$d$is the degree of the queried vertex. Our second data structure answers all these queries faster at the expense of slightly more space. More specifically, it consumes$O(n\log^{2}n)$bits while answering adjacency and degree queries in constant time and neighborhood query in$O(d\log n)$time. Central to our data structures is the usage of the classical heavy path decomposition, followed by a careful bookkeeping using an orthogonal range search data structure among others, which may be of independent interest for designing succinct data structures for other graphs.

The run-length compressed Burrows-Wheeler transform (RLBWT) used in conjunction with the backward search introduced in the FM index is the centerpiece of most com-pressed indexes working on highly-repetitive data sets like biological sequences. Compared to grammar indexes, the size of the RLBWT is often much bigger, but queries like counting the occurrences of long patterns can be done much faster than on any existing grammar index so far. In this paper, we combine the virtues of a grammar with the RLBWT by building the RLBWT on top of a special grammar based on induced suffix sorting. Our experiments reveal that our hybrid approach outperforms the classic RLBWT with respect to the index sizes, and with respect to query times on biological data sets for sufficiently long patterns, which could be interesting for aligning long reads in bioinformatics.

We consider the problem of designing succinct encodings for some intersection graphs on a circle, which include graph classes such as circle graphs, k-polygon-circle graphs, circle-trapezoid graphs among others. More specifically, we first prove a general counting lower bound, which is of independent interest, for these intersection graph classes, and then present a uniform encoding approach that lets us obtain matching lower and upper bounds for their succinct representation.

Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic tractability. In this paper we design a succinct data structure for graphs on$n$vertices whose clique-width is at most$k \leq \epsilon \sqrt{\log n / \log \log n}$for some constant$0<\epsilon<1$, along with supporting degree, adjacency, neighborhood queries efficiently. This resolves an open problem of Kamali (Algorithmica-2018).

We study node similarity in labeled networks, using the label sequences found in paths of bounded length q leading to the nodes. (This recalls the q-grams employed in document resemblance, based on the Jaccard distance.) When applied to networks, the challenge is two-fold: the number of q-grams generated from labeled paths grows exponentially with q, and their frequency should be taken into account: this leads to a variation of the Jaccard index known as Bray-Curtis index for multisets. We describe nSimGram, a suite of fast algorithms for node similarity with q-grams, based on a novel blend of color coding, probabilistic counting, sketches, and string algorithms, where the universe of elements to sample is exponential. We provide experimental evidence that our measure is effective and our running times scale to deal with large real-world networks.

We introduce succinct representations of a d-dimensional point set supporting orthogonal range searching under two circumstances. First, we discuss this problem under the assumption that each coordinate of points takes a real number and we cannot change its encoding. In this case, it is usual to convert the point set into rank space. In this paper, we present a data structure using dn lg n + o(n lg n) bits, where n denotes the number of points in P, and supporting reporting queries in O((n(d-2)/d+ occ) lgn/lglgn) time, and counting queries in O(n(d-2)/dlg n/ lg lg n) time, where occ denotes the number of point to report. Secondly, we consider orthogonal range searching under the condition that each coordinate takes an integer in [U]1and we can change its encoding. In this case, we propose a succinct representation of the point set which requires dn lg U + o(n lg n) bits while supporting these queries in the same time complexity as that in rank space.

We show that both the Lempel-Ziv-77 and the Lempel-Ziv-78 factorization of a text of length n on an integer alphabet of size σ can be computed in O(n lg lg σ) time (linear time if we allow randomization) using O(n lg σ) bits of working space. Given that a compressed representation of the suffix tree is loaded into RAM, we can compute both factorizations in linear time using O(n) space.

The de Bruijn graph GK of a set of strings Sis a key data structure in genome assembly that represents overlaps between all the K-length substrings of S. Construction and navigation of the graph is a space and time bottleneck in practice and the main hurdle for assembling large genomes. This problem is compounded because state-of-the-art assemblers do not build the de Bruijn graph for a single order (value of K) but for multiple values of K: they builddde Bruijn graphs, each with a specific order, i.e., GK1, GK2, GKd. Al-though, this paradigm increases the quality of the assembly produce but it greatly increases runtime, because of the need to construct graphs instead of one. In this paper, we show how to augment a succinct de Bruijn graph representation by Bowe et al. (Proc. WABI, 2012) to support new operations that let us change order on the fly, effectively representing all de Bruijn graphs of order up to some maximum Kin a single data structure. Our experiments show our variable-order de Bruijn graph only modestly increases space usage, construction time, and navigation time compared to a single order graph.

Query autocompletion is an important feature saving users many keystrokes from typing the entire query. In this paper we study the problem of query autocompletion that tolerates errors in users' input using edit distance constraints. Previous approaches index data strings in a trie, and continuously maintain all the prefixes of data strings whose edit distance from the query are within the threshold. The major inherent problem is that the number of such prefixes is huge for the first few characters of the query and is exponential in the alphabet size. This results in slow query response even if the entire query approximately matches only few prefixes. In this paper, we propose a novel neighborhood generation-based algorithm, IncNGTrie, which can achieve up to two orders of magnitude speedup over existing methods for the error-tolerant query autocompletion problem. Our proposed algorithm only maintains a small set of active nodes, thus saving both space and time to process the query. We also study efficient duplicate removal which is a core problem in fetching query answers. In addition, we propose optimization techniques to reduce our index size, as well as discussions on several extensions to our method. The efficiency of our method is demonstrated against existing methods through extensive experiments on real datasets.

This paper investigates how to index a text which is subject to updates. The best solution in the literature (P.Ferragina, et al., 1998) is based on suffix tree using O(n log n) bits of storage, where n is the length of the text. It supports finding all occurrences of a pattern P in O(|P|+occ) time, where occ is the number of occurrences. Each text update consists of inserting or deleting a substring of length y and can be supported in O(y+/spl radic/(n)) time. In this paper, we initiate the study of compressed index using only O(n log |/spl Sigma/|) bits of space, where /spl Sigma/ denotes the alphabet. Our solution supports finding all occurrences of a pattern P in O(|P| Iog/sup 2/n(log/sup /spl epsi//n+log|/spl Sigma/|)+occlog/sup 1+/spl epsi//n) time, while insertion or deletion of a substring of length y can be done in O((y+/spl radic/(n)) Iog/sup 2+/spl epsi// n) amortized tune, where 0

The context tree weighting method is a universal compression algorithm for FSMX sources. Though we expect that it will have a good compression ratio in practice, it is difficult to implement it and in many cases the implementation is only for estimating compression ratio. Though Willems and Tjalkens (1997) showed a practical implementation using not block probabilities but conditional probabilities, it is used for only binary alphabet sequences. We extend the method for multi-alphabet sequences and show a simple implementation using PPM techniques. We also propose a method to optimize a parameter of the context tree weighting for binary alphabet case. Experimental results on texts and DNA sequences show that the performance of PPM can be improved by combining the context tree weighting and that DNA sequences can be compressed in less than 2.0 bpc.

Summary form only given. The suffix array is a memory-efficient data structure for searching any substring of a text. It is also used for defining the Burrows-Wheeler transformation (BWT), which is the core of block sorting. When a compressed text is decoded, the inverse of BWT, which is faster than forward transformation, is performed and in the process the suffix array of the text is also obtained. This means that we can compress and transfer a text and its suffix array by simply using block sorting. This fact can be used for creating large full-text databases. We propose a modified Burrows-Wheeler transformation. By using our transformation, we obtain a suffix array from a compressed text which can be used for case-insensitive searches. An exact query can be done from the result of a case-insensitive search because we can decode the original text from the compressed text. It is available for case-insensitive and more general character conversions. We call the conversion unification and the text after conversion unified text. The proposed transformation is defined by the suffix array of the unified text. Our transformation is not a permutation of an alphabet followed by the original transformation but a combination of unification and the original transformation. From a compressed text using our transformation we can obtain the original text and the suffix array of the unified text. After decoding we can perform ambiguous searches like case-insensitive search by using the suffix array. Experimental results show that our transformation decreases the compression ratio very little. Though decompression and search takes more time than decoding of the original block sorting plus grep command, finding positions of keywords is quite fast which is available for advanced searches.

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 a suffix array and it is a memory efficient alternative of the suffix tree. Sorting suffixes is also used for the Burrows-Wheeler (see Technical Report 124, Digital SRC Research Report, 1994) transformation in the block sorting text compression, therefore fast sorting algorithms are desired. We compare algorithms for making suffix arrays of Bentley-Sedgewick (see Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, p.360-9, 1997), Andersson-Nilsson (see 35th Symp. on Foundations of Computer Science, p.714-21, 1994) and Karp-Miller-Rosenberg (1972) and making suffix trees of Larsson (see Data Compression Conference, p.190-9, 1996) on the speed and required memory and propose a new algorithm which is fast and memory efficient by combining them. We also define a measure of difficulty of sorting suffixes: average match length. Our algorithm is effective when the average match length of a text is large, especially for large databases.

Summary form only given. Block sorting uses the Burrows-Wheeler transformation (BWT) which permutes an input string. The permutation is defined by the lexicographic order of contexts of symbols. If we assume that symbol probability is defined by preceding k symbols called context, symbols whose contexts are the same are collected in consecutive regions after the BWT. Sadakane (1997) proposed a variant of the block sorting and it is asymptotically optimal for any finite-order Markov source if permutation of symbols whose contexts are the same is random. However, the variant encodes 1 symbols as a block and therefore it is not practical because 1 is large. We propose two compression schemes not using blocks but encoding symbols one by one by using arithmetic codes. The move-to-front transformation is not used. The former encodes symbols by different codes defined by symbol frequencies in contexts. It is asymptotically optimal for k-th order Markov sources. However, it is available only if the order k of the source is already known. The latter divides 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 asymptotically optimal for any finite-order Markov source. The permutation in the BWT is not completely random. However, we conjecture that the permuted string is memoryless and our schemes work.