An algorithm SACA-m is proposed to sort all suffixes of a read-only input string of n characters with alphabet size nO(1)in O(n) time and O(n1/2) workspace. It can be applied to sort suffixes of a general alphabet in O(n log n) time and O(n1/2) workspace. This algorithm can be revised to a succinct variant SACA-1 to reuse the space of suffix array for O(1) workspace while keeping O(n) time. The time and space performance of both algorithms are evaluated by experiments on realistic and artificial datasets. These new results give the best time and space complexities for sorting suffixes of big alphabets.

Many efficient open-source suffix sorters using the induced sorting (IS) method to build the fundamental data structure suffix array (SA) for compressing and indexing data have been proposed. To avoid potential faults caused by possible implementation bugs, checking the output SA from any IS sorter without engineering warranty for correctness is a de-facto process. The existing SA checkers commonly perform checking after an SA is built completely, with significant time and space complexities compared with that of builders. This article proposes an efficient solution for building and checking SA simultaneously by enhancing the original IS method with a checking scheme using hash computations to on-the-fly verify the results produced by the last induction phase of IS method. Given an input of constant alphabet, this checking scheme requires linear time and constant RAM space when running on external memory, and its time and space overheads are negligible compared with that for building SA. In our experiments on real-world data, the proposed methods take advantages over the counterparts of existing SA checkers by running faster with less space. This work can help provide a value-added bonus feature for open-source IS sorters to guarantee the correctness of a built SA, and such a feature should be desirable for applications using these sorters.

A number of methods have been proposed for suffix sorting on internal memory of RAM and external memory of hard disks. The current best results for suffix sorting on internal or external memory are achieved by several algorithms using the induced sorting (IS) method in various ways. While these algorithms are efficient, the internal ones are much different from those external in terms of the algorithm designs. A scalable IS method that can be applied for suffix sorting on both internal and external memory is highly desired. This article proposes a blockwise IS method to facilitate pipelined access on internal memory and sequential I/Os on external memory. The detailed algorithm of using this method for a 4-stage pipeline with multiple threads is described, where multiple threads are applied to parallelize not only the pipelined stages of consecutive blocks but also the tasks within each stage wherever possible. This algorithm is evaluated by our experiments on a set of realistic and artificial datasets to achieve better overall time and space performance than the existing best results from pSACAK, pDSS and pKS. Beside sorting suffixes on internal memory in linear time, the proposed method can be ported to external memory for sorting massive suffixes in linear I/O complexity.

Sorting all suffixes of an input string$X$will produce the suffix array that is a fundamental data structure for full-text search on$X$. To utilize the parallel computing power of a multicore machine with shared memory, this article designs a fast linear-time and in-place parallel algorithm called pSACAK, for sorting the suffixes of an input string with a constant alphabet. This algorithm is a parallel variant of the sequential suffix sorting algorithm SACAK which improved the linear-time SAIS to be in-place for constant alphabets, and hence requires only a workspace of$\mathcal {O}(K)$for alphabet size$K$. While our recent work has successfully designed the parallel variant of SAIS on a multicore machine, it remains a challenge to parallelize SACAK due to the strong data dependencies caused by the in-place constraint. A number of new techniques are proposed here to overcome the difficulties for designing pSACAK from the sequential SACAK. An experimental study is conducted to evaluate the performance of pSACAK versus other existing parallel suffix sorting algorithms. Our experimental results show that pSACAK is the most time and space efficient among all in comparison. To the best of our knowledge, pSACAK is the only linear-time and in-place parallel suffix sorting algorithm for constant alphabets reported so far.

For full-text indexing of massive data, the suffix and LCP (longest common prefix) arrays have been recognized as fundamental data structures, and there are at least two needs in practice for checking their correctness, i.e., program debugging and verifying the arrays constructed by probabilistic algorithms. Two probabilistic methods are proposed to check the suffix and LCP arrays of constant or integer alphabets in external memory using a Karp-Rabin fingerprinting technique, where the checking is wrong only with a negligible error probability. The first method checks the lexicographical order and the LCP-value of two suffixes by computing and comparing the fingerprints of their LCPs. This method is general in terms of that it can verify any full or sparse suffix/LCP array of any order. The second method uses less space, it first employs the fingerprinting technique to verify a subset of the given suffix and LCP arrays, from which two new suffix and LCP arrays are induced and compared with the given arrays for verification, where the induced suffix and LCP arrays can be removed for constant alphabets to save space.

Computing the Lempel–Ziv factorization (LZ77) of a string is a key step in many applications. However, at the same time, it constitutes a bottleneck of the entire computation. The investigation of time and space efficient computation of the LZ77 has become an important topic. In this paper, we present a lightweight linear-time algorithm called LZone for computing the LZ77, which is designed by improvements on the existing linear-time space efficient LZ77 algorithm BGone for speed acceleration. For an input string T[1..n] over a constant alphabet size of O(1), LZone requires only n words of workspace in addition to the input string and the output factorization, ⌈logn⌉ bits per word. This is the same space requirement for the algorithm BGone. LZone has two versions, LZoneT and LZoneSA, corresponding to BGoneT and BGoneSA, respectively. Our experimental results show that for computing the LZ77 from an input string T, LZoneT and LZoneSA run at around 26% and 57%, respectively, faster than their counterparts in BGone. Moreover, for computing the LZ77 from the suffix array of T, the speed of LZoneSA is on average twice that of BGoneSA. Copyright © 2015 John Wiley & Sons, Ltd.

We present in this article an external memory algorithm, called disk SA-IS (DSA-IS), to exactly emulate the induced sorting algorithm SA-IS previously proposed for sorting suffixes in RAM. DSA-IS is a new disk-friendly method for sequentially retrieving the preceding character of a sorted suffix to induce the order of the preceding suffix. For a size n string of a constant or integer alphabet, given the RAM capacity Ω (( nW ) 0.5 ), where W is the size of each I/O buffer that is large enough to amortize the overhead of each access to disk, both the CPU time and peak disk use of DSA-IS are O ( n ). Our experimental study shows that on average, DSA-IS achieves the best time and space results of all of the existing external memory algorithms based on the induced sorting principle.

We present a new suffix array construction algorithm that aims to build, in external memory, the suffix array for an input string of length n measured in the magnitude of tens of Giga characters over a constant or integer alphabet. The core of this algorithm is adapted from the framework of the original internal memory SA-DS algorithm that samples fixed-size d-critical substrings. This new external-memory algorithm, called EM-SA-DS, uses novel cache data structures to construct a suffix array in a sequential scanning manner with good data spatial locality: data is read from or written to disk sequentially. On the assumed external-memory model with RAM capacity Ω (( nB ) 0.5 ), disk capacity O ( n ), and size of each I/O block B , all measured in log n -bit words, the I/O complexity of EM-SA-DS is O ( n / B ). This work provides a general cache-based solution that could be further exploited to develop external-memory solutions for other suffix-array-related problems, for example, computing the longest-common-prefix array, using a modern personal computer with a typical memory configuration of 4GB RAM and a single disk.

This article presents an O ( n )-time algorithm called SACA-K for sorting the suffixes of an input string T [0, n -1] over an alphabet A [0, K -1]. The problem of sorting the suffixes of T is also known as constructing the suffix array (SA) for T . The theoretical memory usage of SACA-K is n log K + n log n + K log n bits. Moreover, we also have a practical implementation for SACA-K that uses n bytes + ( n + 256) words and is suitable for strings over any alphabet up to full ASCII, where a word is log n bits. In our experiment, SACA-K outperforms SA-IS that was previously the most time- and space-efficient linear-time SA construction algorithm (SACA). SACA-K is around 33% faster and uses a smaller deterministic workspace of K words, where the workspace is the space needed beyond the input string and the output SA. Given K = O (1), SACA-K runs in linear time and O (1) workspace. To the best of our knowledge, such a result is the first reported in the literature with a practical source code publicly available.

The gap between high throughput demand of Internet traffic and low speed capacity of a router's interface has become a bottleneck for packet forwarding. One way to close the gap is to employ a parallel mechanism, where the route lookups of multiple packets are processed simultaneously, yielding a substantial improvement in the system's throughput. This paper proposes a new pipelined trie-based routing architecture with multiple memory blocks, in which a routing table is organized as a prefix trie and the latter is further decomposed into a main trie and multiple subtries containing the lower-level and higher-level nodes, respectively. Further, the main trie is converted into an index table and the subtries are evenly distributed into all the memory blocks. A storage management technique called random duplicate allocation (RDA) is employed to balance the storage demands among all the memory blocks. Specifically, for each subtrie, the root node is stored in a randomly selected memory block, and the descendant nodes are stored in the subsequent memory blocks level by level, in a circular manner of one block for a level. The results of computer simulation experiments indicate that the routing system's aggregate throughput grows almost linearly proportional to the number of memory blocks.

In this paper, we propose a 3-stage framed packet switch using an internal speedup of 2 to avoid any control loop between any two stages of the switch. The switch segments the arriving variable-length packets at each input port into fixed-size cells and assembles the cells into frames. Then the frames are switched across the shared buffers to their destined output ports, and the cells are reassembled into packets before being transmitted to the next hop. We have designed a broad class of work-conserving scheduling algorithms for the proposed switch, and they are analyzed to be stable, i.e. achieving 100% throughput, under any admissible traffic. To gain more insights into the switch practical performance, an extensive performance evaluation study is conducted using computer simulations. Our results demonstrate that the worst-case performance can be bounded. In addition, we are able to achieve a high throughput-delay performance comparable to that of the padded frame switch which uses a much more complicated scheduling algorithm.

The Sort Transform (ST) can significantly speed up the block sorting phase of the Burrows-Wheeler Transform (BWT) by sorting the limited order contexts. However, the best result obtained so far for the inverse ST has a time complexity O ( N log k ) and a space complexity O ( N ), where N and k are the text size and the context order of the transform, respectively. In this article, we present a novel algorithm that can compute the inverse ST for any k -order contexts in an O ( N ) time and space complexity, a linear result independent of k . The main idea behind the design of this linear algorithm is a set of cycle properties of k -order contexts that we explore for this work. These newly discovered cycle properties allow us to quickly compute the Longest Common Prefix (LCP) between any pair of adjacent k -order contexts that may belong to two different cycles, which eventually leads to the proposed linear-time solution.

We present, in this paper, two efficient algorithms for linear time suffix array construction. These two algorithms achieve their linear time complexities, using the techniques of divide-and-conquer, and recursion. What distinguish the proposed algorithms from other linear time suffix array construction algorithms (SACAs) are the variable-length leftmost S-type (LMS) substrings and the fixed-length d-critical substrings sampled for problem reduction, and the simple algorithms for sorting these sampled substrings: the induced sorting algorithm for the variable-length LMS substrings and the radix sorting algorithm for the fixed-length d-critical substrings. The very simple sorting mechanisms render our algorithms an elegant design framework, and, in turn, the surprisingly succinct implementations. The fully functional sample implementations of our proposed algorithms require only around 100 lines of C code for each, which is only 1/10 of the implementation of the KA algorithm and comparable to that of the KS algorithm. The experimental results demonstrate that these two newly proposed algorithms yield the best time and space efficiencies among all the existing linear time SACAs.

We present a linear time and space suffix array (SA) construction algorithm called the SA-IS algorithm.The SA-IS algorithm is novel because of the LMS-substrings used for the problem reduction and the pure induced-sorting (specially coined for this algorithm)used to propagate the order of suffixes as well as that of LMS-substrings, which makes the algorithm almost purely relying on induced sorting at both its crucial steps.The pure induced-sorting renders the algorithm an elegant design and in turn a surprisingly compact implementation which consists of less than 100 lines of C code.The experimental results demonstrate that this newly proposed algorithm yields noticeably better time and space efficiencies than all the currently published linear time algorithms for SA construction.

Let S be an n-character string terminated with an unique smallest sentinel, its suffix array SA(S) is an array of pointers for all the suffixes in S sorted in the lexicographically ascending order. Specially, the Burrows-Wheeler transform for building efficient compression solutions can be quickly computed by fast suffix sorting based on suffix array construction algorithms (SACAs). The existing well-known practical linear SACAs are those two contemporarily reported in 2003 by Karkkainen and Sanders (KS) (J. Karkkaiinen and P. Sanders, 2003) and Ko and Aluru (KA) (P. Ko and S. Aluru, 2003).

Summary form given only. The Schindler transform (ST) can speed up the block sorting phase of the Burrows-Wheeler transform (BWT) by limiting the context sorting to the first k (k E [0, N], where N is the length of the text) positions only. Under the ST's partial sorting scheme, if two rows share the exactly same k-order context, they may not be ordered alphabetically; instead, the relative order between them in the original matrix is preserved in the transformed matrix. A major tradeoff for the ST to achieve the speedup gain over the BWT is that the inverse ST appears to be more complicated than the inverse BWT. To deal with the existence of identical k-order contexts, Schindler suggested a hash based approach in which the text retrieval has to rely on the hash table based context lookup, which in turn has to rely on the complete retrieval of all the k-order contexts. An improved solution proposed by Yokoo uses no hash table; however, it still needs to restore all the k-order contexts, which clearly requires O(kN) for both the time and the space complexities. Recently, Nong and Zhang had proposed an auxiliary vector based framework, which is different from any possible k-order context retrieval based approaches formerly suggested by others, but similar to that used for the inverse BWT. This framework relies on two size-N vectors Tkand Ck(details are omitted due to space limit) to correctly retrieve the true immediate preceding character for a given character, which allows the original text to be recovered directly from the transformed text without statically restoring the complete fc-order contexts. As a consequence, this framework requires only O(N) space. However, its running time remains to be O(kN), for it has to visit each column of the fc-order context matrix to obtain Tkand Ck.Since Tkand Ckcan be deduced from the context switch vector D (the data structure indicating whether each pair of two neighbor rows in the context matrix are the same or not) in linear time, the more efficient the D can be calculated, the faster the ST can be inverted. If two k-order contexts are different, either their first halves are different already, or their second halves are different; furthermore, the second half of the k-order context matrix can be deduced from its first half due to the rotating scheme in ST. Based on this observation, we proposed a dynamic programming approach to quickly calculate D by doubling the steps to reach the fcth column in comparing the fc-order contexts. This "doubling technique" based algorithm requires only O(Nlogk) time to calculate D, thus resulting in an O(N log k) time complexity algorithm to invert ST. The space complexity of the algorithm remains to be O(N). This new algorithm can be used to build efficient compression solutions based on the ST.

The switch architecture with the combined input - crosspoint queueing (CICQ) scheme has been recognized as a practical promising solution for building cost-effective high-performance switches. In an N x N CICQ switch, the switching fabric is a nonblocking buffered crossbar, a large input buffer is provided at each input and a relatively small internal buffer is provided at each crosspoint of the buffered crossbar. Each input buffer is logically organized as N virtual output queues (VOQs). In this paper, we build the queueing model for evaluating the delay performance of a CICQ switch under i.i.d uniform 2-state Markov modulated Bernoulli process (2-MMBP) bursty traffic. The accuracy of the queuing model is examined via computer simulation, by investigating the mean cell delay in a switch as a function of the switch size, the internal buffer size, the mean offered load and the mean burst length. The numerical results show that our queueing model can well analyze the reality.

As an important variant of the Burrows-WheelerTransform (BWT), the Sort Transform (ST) can speed up thetransformation by sorting only a portion of the matrix. However,because the currently known inverse ST algorithms need toretrieve the complete k-order contexts and use hash tables, theyare less efficient than the inverse BWT. In this paper, we proposethree fast and memory-efficient inverse ST algorithms. The firstalgorithm uses two auxiliary vectors to replace the hash tables.The algorithm achieves O(kN) time and space complexities for atext of N characters under the context order k. The second usestwo additional compact "alternate vectors" to further eliminatethe need to restore all the k-order contexts and achieve O(N)space complexity. And the third uses a "doubling technique" tofurther reduce the time complexity to O(N log2 k). The hallmarkof these three algorithms is that they can invert ST in a mannersimilar to inverting BWT in that they all make use of precalculatedauxiliary mapping vectors and require no hash tables.These unifying algorithms can also better explain the connectionbetween the BWT and the ST: their forward components can notonly be performed by the same algorithm framework, but theirrespective inverse components can also be efficiently conductedby the unifying algorithm framework proposed in the presentwork.

Summary form only given. This paper demonstrates how to successfully fit both the Burrows-Wheeler text (BWT) transform method and the Schindler transform (ST) method into a unified algorithm framework and how this can be used to reveal a strong connection between the ST and the BWT as well as that between the inverse ST and the inverse BWT

We present in this paper an efficient medium access control (MAC) protocol called iCSMA/CD for improving the efficiencies of optical wavelength division multiplexing (WDM) networks. The key idea behind the design of iCSMA/CD is similar to the well-known carrier sense multiple access with collision detection (CSMA/CD) MAC protocol for the Ethernet, in the sense that both use the CD technique to resolve contentions for the carrier. However, our proposed protocol is unique in that it exploits some look-ahead method for achieving better delay-throughput performance. Simulation experiments are conducted to evaluate the delay-throughput performance of a WDM ring network controlled by the proposed iCSMA/CD protocol and the results demonstrate the impressive advantages of iCSMA/CD

With a deep understanding on the properties of stable matching in the context of multiple input-queued switches, we propose the efficient schemes to guarantee the QoS of any unicast and multicast traffic with fixed- or variable-length packets in an unified way. Using these schemes, the QoS of fixed- or variable-length unicast and multicast packets can be guaranteed by independently employing suitable service disciplines at the packets' destined outputs like what is being done in an output queueing switch. One of our proposed schemes uses totally 4N input/output buffers, each with an internal speed-up of 2 independent of N, for an N/spl times/N switch to support any fixed- or variable-length multicast and unicast packets with QoS guarantees.

In this letter, we analyze the performance of multiple input-queued asynchronous transfer mode (ATM) switches that use parallel iterative matching (PIM) for scheduling the transmission of head-of-line cells in the input queues. A queueing model of the switch is developed under independently, identically distributed, two-state Markov modulated Bernoulli processes bursty traffic. The underlying Markov chain of the queueing model is a quasi-birth-death (QBD) chain. The QBD chain is solved using an iterative computing method. Interesting performance metrics of the ATM switch such as the throughput, the mean cell delay, and the cell loss probability can be derived from the model. Numerical results from both the analytical model and simulation are presented, and the accuracy of the analysis is briefly discussed.

An analytical model for the performance analysis of a multiple input queued asynchronous transfer mode (ATM) switch is presented. The interconnection network of the ATM switch is internally nonblocking and each input port maintains a separate queue of cells for each output port. The switch uses parallel iterative matching (PIM) to find the maximal matching between the input and output ports of the switch. A closed-form solution for the maximum throughput of the switch under saturated conditions is derived. It is found that the maximum throughput of the switch exceeds 99% with just four iterations of the PIM algorithm. Using the tagged input queue approach, an analytical model for evaluating the switch performance under an independent identically distributed Bernoulli traffic with the cell destinations uniformly distributed over all output ports is developed. The switch throughput, mean cell delay, and cell loss probability are computed from the analytical model. The accuracy of the analytical model is verified using simulation.

An analytical model for the performance analysis of a novel input access scheme for an ATM switch is developed and presented in this paper. The interconnection network of the ATM switch is internally nonblocking and each input port maintains a separate queue for each output port so as to reduce the head-of-line (HOL) blocking of conventional input queuing switches. Each input is allowed to send only one cell per time slot, and each output port is allowed to receive only one cell per time slot. Using a tagged queue approach, an analytical model with an underlying two-dimensional Markov chain with a state space of size (queue capacity/spl times/switch size) is constructed for evaluating the switch performance under i.i.d Bernoulli traffic for different offered traffic loads. The switch throughput, mean cell delay, and cell loss probability are computed from the analytical model. The accuracy of the analytical model is verified using simulation.