This paper presents a strictly time- and communication-optimal distributed sorting algorithm in a line network. A strictly time-optimal distributed sorting algorithm in a line network has already been designed. However, its communication complexity is not strictly optimal and it seems to be difficult to extend it to other problems, such as that related to multiple elements in a process, and also the dynamic sorting problem where the number of elements each process should have as its solution is not the same as that in the initial state. Therefore, the algorithm in this paper was designed by an alternative approach to make it strictly time- and communication-optimal. Moreover, an extension to the dynamic sorting problem is described.

This paper defines the distributed arrangement selection problem in a line network in a distributed context and describes the design of a strictly-time-optimal algorithm which solves the problem with a limited local memory space. The problem is regarded as a combined distributed sorting and k-selection problem, namely a problem of sorting elements that are not larger than the kth minimum element in predetermined processes. The algorithm also provides a solution to a resource allocation problem in a line network in a strictly-optimal time.

We propose new lossless medical image compression method based on hierarchical sorting technique. Hierarchical sorting is a technique to achieve high compression ratio by detecting the regions where image pattern varies abruptly and sorting pixel order by its value to increase predictability. In this method, we can control sorting accuracy along with size and complexity. As the result, we can reduce the sizes of the permutation-tables and reuse the tables to other image regions. Comparison using experimental implementation of this method shows better performance for medical image set measured by X-ray CT and MRI instruments where similar sub-block patterns appear frequently. This technique applies quad-tree division method to divide an image to blocks in order to support progressive decoding and fast preview of large images.

Topological sorting is, given with a directed acyclic graph G=(V,E), to find a total ordering of the vertices such that if (u,v)E then u is ordered before v. Instead of topological sorting, we are interested in how many total orderings exist in a given directed acyclic graph. We call such a total ordering as legal sequence and the problem of finding total number of legal sequences as legal sequence number problem. In this paper, we firstly give necessary definitions and known results obtained in our previous research. Then we give a method how to obtain legal sequence number for a class of directed acyclic graphs, extended 2-b-SPGs. Finally we discuss the complexity of legal sequence number problem for extended 2-b-SPGs.

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 a sliding dictionary, and the other uses suffix sorting. The former is suitable for small dictionaries and it significantly improves the speed of gzip, which uses a naive hashing algorithm. The latter is suitable for large dictionaries which improve compression ratio for large files. We also experiment on the compression ratio and the speed of block sorting compression, which uses suffix sorting in its compression algorithm. The results show that the LZ77 using the two-level hash is suitable for small dictionaries, the LZ77 using suffix sorting is good for large dictionaries when fast decompression speed and efficient use of memory are necessary, and block sorting is good for large dictionaries.

In this paper the performance of the Block Sorting algorithm proposed by Burrows and Wheeler is evaluated theoretically. It is proved that the Block Sorting algorithm is asymptotically optimal for stationary ergodic finite order Markov sources. Our proof is based on the facts that symbols with the same Markov state (or context) in an original data sequence are grouped together in the output sequence obtained by Burrows-Wheeler transform, and the codeword length of each group can be bounded by a function described with the frequencies of symbols included in the group.

This paper describes a new method for learning bilingual collocations from sentence-aligned parallel corpora. Our method comprises two steps: (1) extracting useful word chunks (n-grams) in each language by word-level sorting and (2) constructing bilingual collocations by combining the word-chunks acquired in stage (1). We apply the method to a two kinds of Japanese-English texts; (1) scientific articles that comprise relatively literal translations and (2) more challenging texts: a stock market bulletin in Japanese and its abstract in English. In both cases, domain specific collocations are well captured even if they were not contained in the dictionaries of specialized terms.

Topological sorting is, given with a directed acyclic graph G = (V, E), to find a total ordering of the vertices such that if (u, v) E then u is ordered before v. Instead of finding total orderings, we wish to find out how many total orderings exist in a given directed acyclic graph G = (V, E). Here we call a total ordering as legal sequence and the problem as legal sequence number problem. In this paper, we first propose theorems on equivalent transformation of graphs with respect to legal sequence number. Then we give a formula to calculate legal sequence number of basic series-parallel digraphs and a way of the calculation for general series-parallel digraphs. Finally we apply our results to show how to obtain legal sequence number for a class of extended series-parallel digraphs.

The polymer matrix for the number of N in-puts/outputs, N stages and 2x2-switches is denoted as the 1-D Spanke-Benes (SB) network. Throughout the paper, the 1-D SB-network, which equals the diamond cellular array, is extended to arbitrary dimensions by a mathematical transformation (a 1-D network provides the interconnection of 1-D data). This transformation determines the multistage architecture completely by providing size, location, geometry and wiring of the switches as well as it preserves properties of the networks, e.g., the capability of sorting. The SB-networks of dimension 3 are analysed and sorting is applied.

This paper provides an architectural study of optical ring trunk-transmission networks using either Time Division Multiplexing (TDM) or Wavelength Division Multiplexing (WDM). A timeslot arrangement algorithm for distributed controlled TDM rings is proposed that minimizes the number of slots (wavelengths) required in bi-directional ring networks. This algorithm is applied in a straightforward manner to wavelength arrangement in WDM ring networks. The technique, characterized by timeslot (or wavelength) conversion, realizes common add/drop procedures in all Add/Drop Multiplexers (ADMs) when they are connected logically in a mesh topology. A self-healing algorithm is also proposed for network restoration. It offers good performance in terms of protection line-capacity, restoration delay, and survivability against multiple failures.

This paper proposes a new lossless data compression method, which utilizes a context sorting algorithm. Every symbol in the data can be predicted by taking its immediately preceding characters, or context, into account. The context sorting algorithm sorts a set of all the previous contexts to find the most similar context to the current one. It then predicts the next symbol by sorting previous symbol-context pairs in an order of context similarity. The codeword for the next symbol represents the rank of the symbol in this sorted sequence. The compression performance is evaluated both analytically and empirically. Although the proposed method operates character by character, with no probability distribution used to make a prediction, it has comparable compression performance to the best known data compression utilities.

This paper presents a parallel sorting algorithm which sorts n elements on O(n/w+n log n/p) time using p(n) processors arranged in a 1-dimensional grid with w(n1-ε) buses for every fixed ε>0. Furthermore, it is shown that np elements can be sorted in O(n/w+n log n/p) time on pp (pn) processors arranged in a 2-dimensional grid with w(n1-ε) buses in each column and in each row. These algorithms are optimal because their time complexities are equal to the lower bounds.