Search

A novel index distribution protocol based on single-particle state is proposed in this paper. Compared with the existing index distribution scheme, this protocol is not limited by the dimension of the quantum system. Based on the proposed index distribution protocol, we also propose a new quantum anonymous ranking protocol. This protocol can complete multi-user and multi-data anonymous ranking tasks in low-dimensional quantum systems. Security analysis shows that eavesdroppers cannot secretly obtain user's private information without being discovered. In addition, we analyze and compare the protocol of this article with the existing anonymous ranking protocols. For different practical conditions, we give the general criteria of how to choose an appropriate anonymous ranking protocol. [ABSTRACT FROM AUTHOR]

Parallel sorting algorithms are widely studied nowadays. After the introduction of parallel processors such as graphics processing unit (GPU) and easy to use parallel programming languages such as CUDA and OpenCL, literature on parallel sorting algorithms has become vast and richer with new ideas and techniques applied to solve the famous problem of sorting. This paper presents a survey of GPU based sorting algorithms. Four sorting algorithms have been selected for this survey: Radix sort, Merge sort, Sample sort and Quick sort. Methods used in those algorithms are described in brief. The performance of these algorithms as claimed by their authors is also presented. A comparative analysis based on the literature is depicted. [ABSTRACT FROM AUTHOR]

We discuss a proof of the correctness of two sorting algorithms: Counting sort and Radix sort. The semi-automated proof is formalized in the state-of-the-art theorem prover KeY. [ABSTRACT FROM AUTHOR]

The sort operation is a core part of many critical applications (e.g., database management systems). Despite the large efforts to parallelize it, the fact that it suffers from high data-dependencies vastly limits its performance. Multithreaded architectures are emerging as the most demanding technology in leading-edge processors. These architectures include simultaneous multithreading, chip multiprocessors, and machines combining different multithreading technologies. In this paper, we analyze the memory behavior and improve the performance of the most recent parallel radix and quick integer sort algorithms on modern multithreaded architectures. We achieve speedups up to 4.69× for radix sort and up to 4.17× for quicksort on a machine with 4 multithreaded processors compared to single threaded versions, respectively. We find that since radix sort is CPU-intensive, it exhibits better results on chip multiprocessors where multiple CPUs are available. While quicksort is accomplishing speedups on all types of multithreading processers due to its ability to overlap memory miss latencies with other useful processing. [ABSTRACT FROM AUTHOR]

The problem of our interest takes as input a database of m sequences from an alphabet Σ and an integer k. The goal is to report all the pairs of sequences that have a matching subsequence of length at least k. We employ two algorithms to solve this problem. The first algorithm is based on sorting and the second is based on generalized suffix trees. We provide experimental data comparing the performances of these algorithms. The generalized suffix tree based algorithm performs better than the sorting based algorithm. [ABSTRACT FROM AUTHOR]

We present an efficient technique for parallel manipulation of data structures that avoids memory access conflicts. That is, this technique works on the Exclusive Read/Exclusive Write (EREW) model of computation, which is the weakest shared memory, MIMD machine model. It is used in a new parallel radix sort algorithm that is optimal for keys whose values are over a small range. Using the radix sort and known results for parallel prefix on linked lists, we develop parallel algorithms that efficiently solve various computations on trees and 'unicycular graphs.' Finally, we develop parallel algorithms for connected components, spanning trees, minimum spanning trees, and other graph problems. All of the graph algorithms achieve linear speedup for all but the sparsest graphs. [ABSTRACT FROM AUTHOR]