Search

We present parallel algorithms to efficiently permute a sorted array into the level-order binary search tree (BST), level-order B-tree (B-tree), and van Emde Boas (vEB) layouts in-place. We analytically determine the complexity of our algorithms and empirically measure their performance. When considering the total time to permute the data in-place and to perform a series of search queries, the vEB layout provides the best performance on the CPU. Given an input of N=537 million 64-bit integers, the benefits of query performance (compared to binary search) outweigh the cost of in-place permutation when performing as few as 0.37% of N queries. On the GPU, results depend on the particular architecture, with the B-tree and vEB layouts performing the best. The number of queries necessary to reach the break-even point with binary search ranges from 1.3% to 8.9% of N=1,074 million 32-bit integers.

In this paper, we take a closer look at a well-known divide-and-conquer algorithm for finding the closest pair of a set of points in the plane under the Euclidean distance. Particularly, we argue that it is sufficient, and sometimes necessary, to check only the next three points following the current point associated with the y -sorted array in the combine phase of the algorithm. We present experimental results comparing the resulting improved version of the divide-and-conquer algorithm to other known variants in the literature for the planar closest-pair problem.

The process of sorting and selecting by key is a basic procedure in many search systems such as databases and Internet search systems. At the same time, modern computing tools require efficient methods and tools which are connected with associative information processing in the development of software and hardware. Therefore, there is a need for high-speed non-computational (associative) processing of large amounts of information, which requires appropriate organization and improvement of technical means of sorting. The well-known algorithms and means for number sorting make it possible to regulate the intensity of this process and increase its efficiency using parallel devices, but they require significant hardware costs. Therefore, the purpose of further research is to develop new and improve known methods of sorting with an orientation on reducing hardware costs and increasing the speed of this process. In this paper, there has been proposed a block diagram of a sorter as a computational part of an associative processor, which has a regular logical structure and parallel-serial connections between data processing units. This greatly simplifies the "placement" of the sorter in a programmable logic IS (FPGA) chip. In addition, the sorter functionally implements the multifunctionality of processing numerical data arrays due to the formation of the ranks of the input array of elements. This allows determining not only the extreme elements of the numeric array but also the element occupying the average value in the sorted array, which is a necessary condition for high-speed median filtering of images. In the proposed sorter, the sorting process uses fast increment/decrement operations on the counter arrays instead of the time-consuming operation of pairwise comparison in parallel for all arrays of elements with their subsequent re-commutation.

In this paper, a modified version of linked list, called balanced linked list (BaLL), has been proposed. It performs better than standard sorted linked list (SoLL) both theoretically and experimentally for maintaining a sorted sequence of data. The modification in BaLL than SoLL is to maintain a special middle node instead of head, and to maintain the remaining nodes in two sorted lists of almost equal size. Three most basic operations, search, insert and delete, have been considered in BaLL and have been compared with the same set of operations in SoLL. For these three operations, BaLL performs theoretically 50% better and experimentally around 50% better than SoLL.

The fragile complexity of a comparison-based algorithm is f(n) if each input element participates in O(f(n)) comparisons. In this paper, we explore the fragile complexity of algorithms adaptive to various restrictions on the input, i.e., algorithms with a fragile complexity parameterized by a quantity other than the input size n. We show that searching for the predecessor in a sorted array has fragile complexity \(\varTheta (\log k)\), where k is the rank of the query element, both in a randomized and a deterministic setting. For predecessor searches, we also show how to optimally reduce the amortized fragile complexity of the elements in the array. We also prove the following results: Selecting the kth smallest element has expected fragile complexity \(O(\log \log k)\) for the element selected. Deterministically finding the minimum element has fragile complexity \(\varTheta (\log (\mathrm {Inv}))\) and \(\varTheta (\log (\mathrm {Runs}))\), where \(\mathrm {Inv}\) is the number of inversions in a sequence and \(\mathrm {Runs}\) is the number of increasing runs in a sequence. Deterministically finding the median has fragile complexity \(O(\log (\mathrm {Runs}) + \log \log n)\) and \(\varTheta (\log (\mathrm {Inv}))\). Deterministic sorting has fragile complexity \(\varTheta (\log (\mathrm {Inv}))\) but it has fragile complexity \(\varTheta (\log n)\) regardless of the number of runs.

The Standard Competition Ranking (SCR) is a commonly adopted ranking strategy and has been used in a wide range of applications, such as statistics, text mining, image processing, and so on. Though the sequential implementation of the SCR can be executed in linear time, it is not straightforward to design parallel algorithms for the SCR. In this paper, our focus is on the novel use of the parallel prefix computation method for calculating the SCR on a many-core Graphics Processing Unit (GPU). We also design a pthreads-based algorithm on a multi-core CPU which adopts a modified binary search to find the first item’s rank in each partitioned segment. By integrating the modified binary search with the prefix computation, we later design and implement a more efficient hybrid algorithm on the GPU. The experimental results show that, as compared with the sequential execution on the CPU, our pthreads-based algorithm on a 12-core CPU can be roughly 8 times faster, while the hybrid algorithm on the GPU can achieve more than two orders of magnitude speedup.

The quest for efficient sorting is ongoing, and we will explore a graph-based stable sorting strategy, in particular employing comparison graphs. We use the topological sort to map the comparison graph to a linear domain, and we can manipulate our graph such that the resulting topological sort is the sorted array. By taking advantage of the many relations between Hamiltonian paths and topological sorts in comparison graphs, we design a Divide-and-Conquer algorithm that runs in the optimal $O(n \log n)$ time. In the process, we construct a new merge process for graphs with relevant invariant properties for our use. Furthermore, this method is more space-efficient than the famous {\sc MergeSort} since we modify our fixed graph only., 18 pages, 0 figures. Keywords: graph algorithms; topological sort; sorting algorithms; comparison graphs

Merging is the process of constructing a sorted array C from two sorted arrays A and B of lengths $$n_A$$ and $$n_B,$$ respectively, such that array C contains the elements of arrays A and B. The problem is a fundamental subroutine in many applications such as tree reconstruction, database design, and sorting. In this paper, we present a constant-time integer merging algorithm on a shared memory model with a concurrent read operation. No constant-time algorithm for integer merging on this model was designed previously. The algorithm, which is based on cross-rank and address strategy, works when the elements of the inputs belong to the integer domain. The presented algorithm has the following advantages:- (1) running in constant time; (2) stable; (3) simple; (4) optimal when the domain of integers is less than or equal to the size of the inputs and the number of processors is equal to size of the inputs; and (5) deterministic.

Counting sort is one of the basic sorting algorithm in computer science which has a time complexity of $\mathcal{O}(N + K)$ where N is the number of elements and K is the maximum value among those N elements. It is superior when it comes to sort countable objects those come from a discrete set of values, such as bounded integers. But, it fails to provide efficiency if the range of K is significantly greater than N. For this reason, it is less used in practical fields of computer science though it has an extensive use as a sub-routine in other sorting algorithms. Several extension approaches on counting sort algorithm have been proposed in the literature but none of those aims to increase the limit of K. This paper proposed an extension of counting sort algorithm that is named Square Root Counting Sort (SRCS) which has an increased limit of K. Specifically, the proposed approach can handle the maximum value of K2 where the classic one is only able to solve K. The first phase of the approach is to prepare some blocks of elements using square root technique and then sort each of the blocks simultaneously to get final sorted array. The proposed extension of counting sort outperforms than classic counting sort as well as bubble, selection and insertion sort.

Thanks to the advances in hardware (sensors and cameras) the number of points that convex hull algorithms must process is now much greater than when these algorithms were developed. This limitation entails focusing current research in convex hull algorithms on finding approaches capable of processing large sets of points. From the many works proposed in this area, the heuristic by Akl-Toussaint deserves a special mention, with outstanding results in execution times. In this article, we take the basic principles of this heuristic to create a convex hull algorithm, called SymmetricHull, that takes advantage of geometric and symmetric properties of the formed quadrants in 2D spaces. The proposed algorithm achieves better exe-cution times than that heuristic, reducing the basic operations to a series of comparisons between consecutive points in an array lexicographically sorted by its y coordinate. SymmetricHull organizes the set of points by quadrants and, instead of using the orientation function as the main operation, it appends the slope s between the analyzed point and its predecessor as a property of the point structure (without causing numerical errors). Point operations can be summarized as follows: 1) a rapid discard of a point, based on its coordinates and the ones of its neighbors; 2) a simple comparison between the property s of the current point and the one of its predecessor in the sorted array, in order to determine whether the current point is a strong candidate to be a part of the convex hull; 3) the addition of a point to a stack of candidates for the convex hull; and 4) the simple elimination of a point from the stack of candidates by comparing the property s of the current point with its predecessors in the stack. Our experiments show that SymmetricHull optimizations achieve good results, in terms of time and number of operations required (multiplications, sums, pushs and pops), being espe-cially efficient with point sets greater than 10^4.

Digital volume correlation (DVC) is a powerful and widely used technique for measuring the internal 3D deformation field of a wide range of materials. One of the most popular DVC algorithms is the reliability-guided DVC (RG-DVC) which is good at dealing with large continuous deformation. However, RG-DVC requires a manually specified seed from which computation starts, and suffers from the efficiency due to a huge amount of computation and data dependency. This paper proposes a GPU accelerated parallel reliability-guided DVC algorithm (CuSIFT-RGDVC) on CUDA, which leverages 3D scale-invariant feature transform (3D SIFT) to assist seed selection to realize fully automation and improves performance utilizing GPU computing. In CuSIFT-RGDVC, reliability-guided displacement tracking (RGDT) is rewritten using sorted array-based batch processing mechanism which is a globally sequential locally parallel model, and multi-granularity parallelism is adopted to maximize GPU utilization. The empirical result shows that the proposed CuSIFT-RGDVC provides up to 29.1x speedup compared with our multi-threaded implementation and achieves the same level of computation speed as the state-of-the-art path-independent DVC without sacrificing accuracy.

Petri nets represent a convenient and powerful tool for networking protocols verification as a basic task of cybersecurity domain. Composition of clans speeds-up process of protocols verification reduced to solving linear Diophantine systems. Varying minimal clan size brings in certain imbalance when solving a system on parallel architectures using PaAd software. The present paper studies a task of preliminary balancing the clan size via their aggregation represented as a special case of graph partitioning. Variants of the task are considered and solved using heuristic techniques: a fast bin packing with the first fit on a sorted array algorithm and a multi-objective graph partitioning with software package METIS. A case study for the clans aggregation on TCP and IOTP protocols and hypertorus communication structures shows that aggregation of clans brings in an additional 3 times speed-up.

We engineer a GPU implementation of a B-Tree that supports concurrent queries (point, range, and successor) and updates (insertions and deletions). Our B-tree outperforms the state of the art, a GPU log-structured merge tree (LSM) and a GPU sorted array. In particular, point and range queries are significantly faster than in a GPU LSM (the GPU LSM does not implement successor queries). Furthermore, B-Tree insertions are also faster than LSM and sorted array insertions unless insertions come in batches of more than roughly 100k. Because we cache the upper levels of the tree, we achieve lookup throughput that exceeds the DRAM bandwidth of the GPU. We demonstrate that the key limiter of performance on a GPU is contention and describe the design choices that allow us to achieve this high performance.

Let A be the array of n integers in {0, 1, …, n-1}. A tree is constructed in O(nloglogm/p+loglogm) time with p processors based on the trie with all the given integers. Additional nodes (O(nloglogm) of them) are added to the tree. After the tree is construct we can, for any given integer, find the predecessor and successor of this integer, insert or delete the integer in A in O(loglogm) time. This result demonstrates for the searching purpose we need not to sort the input numbers into a sorted array for this would need at least O(logn/loglogn) time while this algorithm for constructing the tree can run in O(loglogm) time with n processors.

To manage and organize large data is imperative in order to formulate the data analysis and data processing efficiency. Therefore, this paper investigates the set of sorting techniques to observe which technique to provide better efficiency. Five types of sorting techniques of static data structure, Bubble, Insertion, Selection with O(n2) complexity and Merge, Quick with O(n log n) complexity have been used and tested on four groups between (100–30000) of dataset. To validate the performance of sorting techniques, three performance metrics which are time complexity, execution time and size of dataset were used. All experimental setups were accomplished using simple linear regression. The experimental results illustrate that Quick sort is more efficiency than other sorting and Selection sort is more efficient than Bubble and Insertion in large data size using array. In addition, Bubble, Insertion and Selection have good performance for small data size using array thus, sorting technique with behaviour O(n log n) is more efficient than sorting technique with behaviour O(n2) using array.

Searching on the web is one of the most progressive and expanding field nowadays. A large amount of information is available on the World Wide Web, motivating the need of efficient text indexing method that support fast text retrieval. In the past, two main indexing techniques: Signature files and Inverted files have been proposed. First require much larger space to store index and are more expensive to construct and update than inverted files. Second has been efficiently implemented using different structures like Sorted array and B-Tree. Sorted array was very expensive in updating the indices while appending a new keyword and B-tree method breaks down if there are many words with the same prefix. This paper presents a modified index structure for text retrieval that keeps a good result to optimize the space needed to store and time to search document. The proposed index is designed using the Wavelet Tree (WT), which was originally designed as wavelet transform for images. Experimental results show that on increasing the query length, the WT based index performs better than others.

We present parallel algorithms to efficiently permute a sorted array into the level-order binary search tree (BST), level-order B-tree (B-tree), and van Emde Boas (vEB) layouts in-place. We analytically determine the complexity of our algorithms and empirically measure their performance. Results indicate that on both CPU and GPU architectures B-tree layouts provide the best query performance. However, when considering the total time to permute the data and to perform a series of search queries, our vEB permutation provides the best performance on the CPU. We show that, given an input of N=500M 64-bit integers, the benefits of query performance (compared to binary search) outweigh the cost of in-place permutation using our algorithms when performing at least 5M queries (1% of N) and 27M queries (6% of N), on our CPU and GPU platforms, respectively.

Indexes are models: a B-Tree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate if a data record exists or not. In this exploratory research paper, we start from this premise and posit that all existing index structures can be replaced with other types of models, including deep-learning models, which we term learned indexes. The key idea is that a model can learn the sort order or structure of lookup keys and use this signal to effectively predict the position or existence of records. We theoretically analyze under which conditions learned indexes outperform traditional index structures and describe the main challenges in designing learned index structures. Our initial results show, that by using neural nets we are able to outperform cache-optimized B-Trees by up to 70% in speed while saving an order-of-magnitude in memory over several real-world data sets. More importantly though, we believe that the idea of replacing core components of a data management system through learned models has far reaching implications for future systems designs and that this work just provides a glimpse of what might be possible.

LazySorted is a Python C extension implementing a partially and lazily sorted list data structure. It solves a common problem faced by programmers, in which they need just part of a sorted list, like its middle element (the median), but sort the entire list to get it. LazySorted presents them with the abstraction that they are working with a fully sorted list, while actually only sorting the list partially with quicksort partitions to return the requested sub-elements. This enables programmers to use naive "sort first" algorithms but nonetheless attain linear run-times when possible. LazySorted may serve as a drop-in replacement for the built-in sorted function in most cases, and can sometimes achieve run-times more than 7 times faster.

We develop a dynamic dictionary data structure for the GPU, supporting fast insertions and deletions, based on the Log Structured Merge tree (LSM). Our implementation on an NVIDIA K40c GPU has an average update (insertion or deletion) rate of 225 M elements/s, 13.5x faster than merging items into a sorted array. The GPU LSM supports the retrieval operations of lookup, count, and range query operations with an average rate of 75 M, 32 M and 23 M queries/s respectively. The trade-off for the dynamic updates is that the sorted array is almost twice as fast on retrievals. We believe that our GPU LSM is the first dynamic general-purpose dictionary data structure for the GPU., 11 pages, accepted to appear on the Proceedings of IEEE International Parallel and Distributed Processing Symposium (IPDPS'18)

Visualizing algorithms, such as drawings, slideshow presentations, animations, videos, and software tools, is a key concept to enhance and support student learning. A typical visualization of an algorithm show the data and then perform computation on the data. For instance, a standard visualization of a standard binary search on an array shows an array of sorted numbers and then illustrate the action of the algorithm in a step-by-step fashion. However, this approachdoes not fully capture the computational environment from the perspective of the algorithm. Specifically, the algorithm does not ”see” the full sorted array, but only the single positionthat it accesses during each step of the computation. To fix this discrepancy we introduce the immersive principle that states that at any point in time, the displayed information should closely match the information accessed by the algorithm. We give several examples of immersive visualizations of basic algorithms and data structures, discuss methods for implementing it, and briefly evaluate it.

Sorting is one of the fundamental operations of Computer Science. Many problems, such as plasma real-time diagnostic, image re-ranking, and suffix array construction, require that we sort several arrays in the form of matrix lines or array segments. We define this type of task as segmented sorting. Considering the importance of this problem, the main goal of this study is to provide insight into different techniques for solving it, while also answering the question "What is the best performing strategy?" for different combinations of array lengths and segment sizes. In order to perform segmented sorting, we can either call a sorting procedure for each of the array segments or use an implementation specialized in this operation. As an alternative, we explore an approach named fix sort, which adjusts the array to allow off-the-shelf general sorting algorithms to perform segmented sorting. We implemented and compared different methods to sort multiple segments in a shared memory environment using CUDA. Throughout our experiments, we noticed a great variation in performance when using the MGPU and CUB libraries, the bitonic sort from CUDA samples, the fix sort-based strategies, and a radix sort procedure called for each segment. The tests showed that using fix sort can be favorable in some cases, and enabled us to create a guideline for efficient implementation of segmented sorting routines based on the parameters of array lengths and number of segments.

K-nearest neighbor is widely used data mining algorithm in many areas such as text, medicine. In this research, methods to speed up the K-nearest neighbor algorithm when executed sequentially have been proposed. All of these methods scan through the data set element by element. The first one uses a max heap implementation to speed up finding nearest neighbors of a data point. The second one uses a modified version of randomized selection to find the kth order statistic and then subsequently prune the data points to get the neighbors. The third method uses an insertion mechanism to find the appropriate position every time a data point is scanned in the data set in an initially maintained k-sized sorted array. Based on the size of the data set and the value of k, a suitable method is chosen from the above mentioned methods. Analysis of the methods for various data set sizes and k values has also been performed.

The paper suggests a technique for fast data sort based on a specially organized binary searching network with the following new distinctive features: 1) data sort is done within the time of data acquisition through a serial interface; 2) a new type of pipeline, which we call ring pipeline, is created 3) the delay for receiving each data item is minimized thanks to the novel ring pipeline; 4) sorted data can be transmitted almost immediately after receiving the last input item; 5) several data sets may be sorted by the same network at the same acquisition time. It is proved theoretically that the network is very fast. It was modelled and evaluated in software and the basic components were synthesized and implemented in hardware. The results have shown a significant speed-up comparing to the best known alternatives.DOI: http://dx.doi.org/10.5755/j01.eie.22.4.15920

In recent years, computer science specialists are faced with the challenge of processing massive amounts of data. To overcome this barrier, researchers have developed new techniques to process data in efficient ways. This paper aims to present an algorithm for sorting uniformly distributed numbers, called Unisort. Given a uniformly distributed array of numbers, the algorithm places the numbers into bins to obtain sorted sub-arrays. It then merges the sorted sub-arrays to obtain the final sorted array. This work demonstrates that if numbers are uniformly distributed, the algorithm is able to sort them in O(n) time. Furthermore, the algorithm can be generalized to numbers produced by any known distribution. The only requirement is to know the distribution a priori. However, in the worst case scenario, when the distribution is not known, the numbers may fall in the same bin. For the worst case, the algorithm becomes similar to merge sort. Experiments conducted to assess the performance level of the algorithm, in terms of time efficiency, show that it is faster than quicksort, heapsort and Bucket sort. The algorithm has broad applications in information technology, since almost every information system organizes data by sorting it.

In this paper, we investigate neutron-induced errors in three implementations of sort algorithms (QuickSort, MergeSort, and RadixSort) executed on modern graphics processing units designed for high-performance computing and large server applications. We measure the radiation-induced error rate of sort algorithms taking advantage of the neutron beam available at the Los Alamos Neutron Science Center facility. We also analyze output error criticality by identifying specific output error patterns. We found that radiation can cause wrong elements to appear in the sorted array, misalign values as well as application crashes or system hangs. This paper presents results showing that the criticality of the radiation-induced output error pattern depends on the application. Additionally, an extensive fault-injection campaign has been performed. This campaign allows for better understanding of the observed phenomena. We take advantage of SASS-assembly Intrumentator Fault Injector developed by NVIDIA, which can inject faults into all the user-accessible architectural state. Comparing fault-injection results with radiation experiments data provides an understanding that not all the output errors observed under radiation can be replicated in fault injection. However, fault injection is useful in identifying possible root causes of the output errors observed in radiation testing. Finally, we take advantage of our experimental and analytical study to design efficient experimentally tuned hardening strategies. We detect the error patterns that are critical to the final application and find the more efficient way to detect them. With an overhead as low as 16% of the execution time, we are able to reduce the output error rate of sort of about one order of magnitude.