Estimating the sortedness of a sequence has found applications in, e.g., sorting algorithms, database management and webpage ranking. As the data volume in many of these applications is massive, recent research has been focusing on estimating sortedness in the data stream model. In this thesis, we extend the study of this problem to a number of directions. One common measurement of sortedness is the edit distance to monotonicity. Given a stream of items drawn from a totally ordered set, its edit distance to monotonicity is the minimum number of items to remove so that the remaining items are non-decreasing. The space complexity of estimating the edit distance to monotonicity of a data stream is becoming well-understood over the past few years. Motivated by applications on network quality monitoring, we extend the study to estimating the edit distance to monotonicity of a sliding window covering the w most recent items in the stream for any w _ 1. We give a deterministic algorithm which can return an estimate within a factor of (4 + _) using O( 1 _2 log2(_w)) space. We further extend the study in two directions. First, we consider a stream where each item is associated with a value from a partially ordered set. We give a randomized (4+_)-approximate algorithm using O( 1_2 log _2w log w) space. Second, we consider an out-of-order stream where each item is associated with a creation time and a numerical value, and items may be out of order with respect to their creation times. The goal is to estimate the edit distance to monotonicity with respect to the numerical value of items arranged in the order of creation times. We show that any randomized constant-approximate algorithm requires linear space. Finally, we revisit the classical problem of estimating the length of the longest increasing subsequence (LIS) of a data stream. Previous work shows that any deterministic algorithm requires ?(pN) space through a communication problem Hidden-IS, where N is the number of items in the stream. But the randomized space complexity of LIS is open [2]. [23] has given an efficient randomized protocol for Hidden-IS, showing that Hidden-IS may be significantly easier than LIS. We give an even simpler and more efficient randomized protocol for the Hidden-IS problem, indicating that it is unlikely that this communication problem can lead to a polynomial randomized space lower bound for the LIS problem. On the positive side, we propose a new communication problem which we conjecture to be hard enough to lead to a super polylogarithmic randomized space lower bound for the LIS problem. / published_or_final_version / Computer Science / Master / Master of Philosophy

Thesis (Ph. D.)--University of Wisconsin--Madison, 1981. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references (leaves 179-182).

In this thesis existing models of adaptive computer architecture were modified to adapt actual sorting problems to "divide 'n' conquer" (DQ) coordinator type configuration in which the children processors were expanded from three to four. Two hire/fire strategies, one using packets waiting in queue and the other using the average turn around time, were applied to maintain the hierarchical tree structure. More than 1200 simulation runs were analyzed and compared, finding that the first strategy was best at fast packet arrival rate and the second strategy was best at slow packets arrival rate. Comparing the hire/fire signal generation policies, the "fc-root" was best and the "root-fp" was worst. While comparing the effect of variable weighting factors in processors, using smaller weighting factor in either "partitioner" for the first strategy or "f-computer" for the second strategy may improve the system performance. (Abstract shortened with permission of author.)

Qian Zhengfeng. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 127-129). / Abstracts in English and Chinese. / Chapter Chapter 1 --- Groundwork --- p.1 / Chapter 1.1 --- Introduction --- p.1 / Chapter 1.2 --- Exchange Patterns --- p.5 / Chapter 1.3 --- Multistage Networks --- p.9 / Chapter 1.3.1 --- Multistage Networks --- p.9 / Chapter 1.3.2 --- Banyan-type Networks --- p.11 / Chapter 1.4 --- Networks of Sorting Cells --- p.15 / Chapter 1.5 --- Symbolic Representation and Matrix Representation --- p.19 / Chapter 1.5.1 --- Symbolic Representation of a Multistage Interconnection Network --- p.19 / Chapter 1.5.2 --- Symbolic Representation of a Network of Sorting Cells --- p.21 / Chapter 1.5.3 --- Matrix Representation of a Network of Sorting Cells --- p.22 / Chapter 1.6 --- Summary --- p.24 / Chapter Chapter 2 --- Construction of Generalized Bitonic Sorters by Merging Rotated Monotonic Sequences --- p.25 / Chapter 2.1 --- Merging Networks --- p.25 / Chapter 2.1.1 --- Recursive 2-stage Construction --- p.26 / Chapter 2.1.2 --- UC/CU Non-blocking Switches --- p.35 / Chapter 2.1.3 --- Circular Sorters and Merging Networks --- p.41 / Chapter 2.2 --- Construction of Generalized Bitonic Sorters --- p.48 / Chapter 2.2.1 --- Bitonic Ar-sorters and Bitonic Dr-sorters --- p.48 / Chapter 2.2.2 --- Algorithms for Construction of Generalized Bitonic Sorters by Merging Rotated Monotonic Sequences --- p.51 / Chapter 2.3 --- Summary --- p.73 / Chapter Chapter 3 --- Construction of Generalized Bitonic Sorters by Cross-k Cell Rearrangement --- p.74 / Chapter 3.1 --- Cross-k Cell Rearrangement on a Multistage Network --- p.74 / Chapter 3.1.1 --- Intra-stage Cell Rearrangement --- p.74 / Chapter 3.1.2 --- Equivalence of Networks --- p.77 / Chapter 3.1.3 --- Cross-k Cell Rearrangement --- p.80 / Chapter 3.2 --- Construction of Generalized Bitonic Sorters --- p.85 / Chapter 3.3 --- Summary --- p.99 / Chapter Chapter 4 --- Redundancy of the Bitonic Network --- p.100 / Chapter 4.1 --- Counting of Identified Generalized Bitonic Sorters --- p.100 / Chapter 4.2 --- Redundancy of the Bitonic Network --- p.110 / Epilogue --- p.112 / Appendix C Program for Exhaustive Search of 8×8 Generalized Bitonic Sorters --- p.113 / References --- p.127

A method to parallelize external sorts on a shared memory multiprocessing system is presented in this thesis. The main goal of the thesis is to develop a sorting package that is scale able and efficient. No prior knowledge of the nature, source or size of the data is assumed for this work. A dynamic load-balancing architecture is used with no static allocation of tasks to processes. The package consists of an interface and a kernel. The interface provides the sort with the following - the sort input, output and temporary work spaces as abstract data types (ADTs), memory available, number of processes available, compare routine to compare records, etc. Only the interface needs to be changed to suit different environments. The kernel implements the parallel sort algorithm. The traditional sort merge technique is used for the external sort as opposed to a distributive sorting technique. Memory-sized runs are first generated and later merged. Parallel binary merges is the technique used for both the run generation and the merge phase. A forecasting table is used to read ahead in the merge phase.

Thesis (M. Phil.)--University of Hong Kong, 2005. / Title proper from title frame. Also available in printed format.

published_or_final_version / abstract / Computer Science / Master / Master of Philosophy

No description available.

No description available.

The function of a Content-Addressable Memory (CAM) is to efficiently search the information stored in the memory, by using hardware rather than software with a corresponding improvement in searching speed. This hardware allows a parallel search by matching the data stored in memory to a search key rather than sequentially searching address by address as is done in a Random Access Memory. Although existing CAMs are more efficient in finding relevant information than RAM, there are additional improvements that can be made to further improve its efficiency. For example, previous CAMs use a word parallel searching scheme that can only identify exact matches. To find the best (closest) match, previous CAMs had to use bit serial approaches. Although still more efficient than RAM searching, these CAMs were limited by the word size (bit width) of the memory. Responding to this inefficiency, the CAM described in this thesis improves best-fit searching by using analog design in combination with digital design. This design retains a mismatch line to collect the result of the comparison of each bit of a word which is decoded by a simple flash A/D. This means that after a single operation the best-fit plus all words with zero to three bits of mismatch, are determined. This word/bit parallel searching makes this CAM more efficient than existing CAMs. The best-fit function of this CAM is good for database retrieval, communications and error correction circuitry. By using the high speed searching and the inexact match feature, this CAM also provides efficient sorting and set operations. The accumulated searching time is shortened when compared to regular CAM and RAM. The inexact CAM in this thesis is designed using mixed analog/digital design in a 2~ CMOS technology.