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

The increasing popularity of flash memory means more database systems will run on flash memory in the future. One of the most important database operations is the external sort. Hence, this paper is focused on studying the problem of efficient external sorting on flash memory. In contrast to most previous work, we target the situation where previously sorted data have become progressively unsorted due to data updates. Accordingly, we call this ‘partially’ sorted data. We focus on re-sorting partially sorted data by taking advantage of the partial sorted nature of the data to speed up the run generation phase of the traditional external merge sort. We do this by finding ‘naturally occurring’ page runs in the partially sorted data. Our algorithm can perform up to a factor of 1024 less write IO compared with a traditional external merge sort during the run generation phase. We map the problem of finding naturally occurring runs into the shortest distance problem in a directed acyclic graph (DAG). Accordingly, we propose an optimal solution to the problem using the well-known DAG-Shortest-Paths algorithm. However, we found that the optimal solution was too slow for even moderate-sized data sets and accordingly propose a fast heuristic solution that—we experimentally show—finds a high percentage of page runs using a minimum of computational overhead. Experiments using both real and synthetic data sets show that our heuristic algorithm can halve the external sorting time when compared with three likely competing external sorting algorithms.

Summary. We show that exchanging of pairs in an array which are in incorrect order leads to sorted array. It justifies correctness of Bubble Sort, Insertion Sort, and Quicksort.

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.

Sorting the suffixes of a string into lexicographical order is a fundamental task in a number of contexts, most notably lossless compression (Burrows--Wheeler transformation) and text indexing (suffix arrays). Most approaches to suffix sorting produce a sorted array of suffixes directly, continually moving suffixes into their final place in the array until the ordering is complete. In this article, we describe a novel and resource-efficient (time and memory) approach to suffix sorting, which works in a complementary way—by assigning each suffix its rank in the final ordering, before converting to a sorted array, if necessary, once all suffixes are ranked. We layer several powerful extensions on this basic idea and show experimentally that our approach is superior to other leading algorithms in a variety of real-world contexts.

The ideas and key algorithms of a sorted list data structure based on a 2-dimensional (2D) array container are presented. It is shown that with an appropriately chosen number of rows, the efficiency of insertion and deletion is much improved compared to traditional approaches of using 1D arrays or linked structures. Yet, the binary search capability is retained. While such a data structure may deserve further exploration for its practical merit, its real value may well be in data structure classes, where the implementations and related issues provide sources for challenging projects. In addition, the implementation also provides a good example in understanding 2D arrays implemented as array of arrays in an object-oriented language.

Usually, binary search only makes sense in sorted arrays. We show that insertion sort based on repeated "binary searches" in an initially unsorted array also sorts n elements in time Θ(n2 log n). If n is a power of two, then the expected termination point of a binary search in a random permutation of n elements is exactly the cell where the element should be if the array was sorted. We further show that we can sort in expected time Θ(n2 log n) by always picking two random cells and swapping their contents if they are not ordered correctly.

We consider a class of problems in which an algorithm seeks to compute a function f over a set of n inputs, where each input has an associated price. The algorithm queries inputs sequentially, trying to learn the value of the function for the minimum cost. We apply the competitive analysis of algorithms to this framework, designing algorithms that incur large cost only when the cost of the cheapest “proof” for the value of f is also large. We provide algorithms that achieve the optimal competitive ratio for functions that include arbitrary Boolean AND/OR trees, and for the problem of searching in a sorted array. We also investigate a model for pricing in this framework and construct, for every AND/OR tree, a set of prices that satisfies a very strong type of equilibrium property.

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.

Our goal is the registration of multiple 3D point clouds obtained from LIDAR scans of underground mines. Such a capability is crucial to the surveying and planning operations in mining. Often, the point clouds only partially overlap and initial alignment is unavailable. Here, we propose an interactive user-assisted point cloud registration system. Guided by the system, the user's role is simply to identify and search for overlapping regions across the point clouds. Specifically, given two point sets, the user clicks on a point in one set, then simply hovers the mouse on the other set to find a matching point. Each mouse position gives rise to a translation, and our system instantly optimises the rotation that aligns the point clouds. Assuming that each individual point set is horizontally levelled with the ground by the level compensator on the LIDAR device, given a candidate 3D translation only one angular parameter needs to be estimated to rotationally align two 3D point sets. We propose a fast rotation search algorithm that delivers globally optimal results in real time. Our method conducts branch-and-bound optimisation with a novel bounding function whose evaluation amounts to simple sorted array operations. This provides smooth and accurate feedback to the user's search for overlapping regions. Our system is intuitive and helps to accelerate the registration of multiple scans.

Given a k-character query string and an array of n strings arranged in lexicographical order, computing the rank of the query string among the n strings or deciding whether it occurs in the array requires the inspection of $$ \Theta\left( \frac {k\log {\log n}} {\log {\log {(4+\frac{k \log{\log n}}{\log n})}}}+k+\log n\right) $$ characters in the worst case.

An iterative algorithm based on binary search has been presented for finding the mode of a sorted array and its frequency. Complexity of the algorithm has been deduced. Numerical experiments show its supremacy over the iterative implementation of Griffiths' algorithm.

We describe the challenges arising from tracking dark matter particles in state of the art cosmological simulations. We are in the process of running the Indra suite of simulations, with an aggregate count of more than 35 trillion particles and 1.1PB of total raw data volume. However, it is not enough just to store the particle positions and velocities in an efficient manner -- analyses also need to be able to track individual particles efficiently through the temporal history of the simulation. The required inverted indices can easily have raw sizes comparable to the original simulation.We explore various strategies on how to create an efficient index for such data, using additional insight from the physical properties of the particle motions for a greatly compressed data representation. The basic particle data are stored in a relational database in course-grained containers corresponding to leaves of a fixed depth oct-tree labeled by their Peano-Hilbert index. Within each container the individual objects are sorted by their Lagrangian identifier. Thus each particle has a multi-level address: the PH key of the container and the index of the particle within the sorted array (the slot).Given the nature of the cosmological simulations and choice of the PH-box sizes, in consecutive snapshots particles can only cross into spatially adjacent boxes. Also, the slot number of a particle in adjacent snapshots is adjusted up or down by typically a small number. As a result, a special version of delta encoding over the multi-tier address already results in a dramatic reduction of data that needs to be stored. We follow next with an efficient bit-compression, adapting to the statistical properties of the two-part addresses, achieving a final compression ratio better than a factor of 9. The final size of the full inverted index is projected to be 22.5 TB for a petabyte ensemble of simulations.

Sorting is one of the most well-known problems in computer science and is frequently used for benchmarking computer systems. It can contribute significantly to the overall execution time of a process in a computer system. Dedicated sorting architectures can be used to accelerate applications and/or to reduce energy consumption. In this paper, we propose an efficient sorting network aiming at accelerating the sorting operation in FPGA-based embedded systems. The proposed sorting network is implemented based on an Optimized Odd-even sorting method (O2) using fully pipelined combinational logic architecture and ring shape processing. Consequently, O2 generates the sorted array of numbers in parallel when the input array of numbers is given, without any delay or lag. Unlike conventional sorting networks, O2 sorting network does not need memory to hold data and information about sorting, and neither need input clock to perform the sorting operations sequentially. We conclude that by using O2 in FPGA-based image processing, we can optimize the performance of filters such as median filter which demands high performance sorting operations for realtime applications.

Sorting is an age old problem in Computer Science. Recently with the advent of cloud computing this problem is revisited on encrypted data. This paper tries to evaluate the possibility of applying the recently discovered Fully Homomorphic Encryption schemes to sort encrypted text. The paper first develops fully homomorphic circuits for performing comparison based swaps and then employs them to realize conventional sorting algorithms. Since the sorting time grows exponentially with the input size, it is required to propose suitable measures to reduce it; the delay occuring due to the costly Recrypt operation which removes the noise in the Homomorphic computations. The paper then investigates the opportunity of reducing Recrypt by experimenting on the average errors introduced due to wrong comparisons, which arise due to the removal of the de-noising step. Results show that suitably choosing the number of Recrypt operations results in an almost sorted array. This motivates to develop a two-stage sorting called LazySort: the first phase performing a Bubble sort with reduced Recrypt operations to result in an almost sorted array, to be followed by a second stage which employs an Insertion sort with all Recrypt operations. Detailed experiments show that helps to obtain a significant speed up in the sorting time.

As a basic building block of many applications, sorting algorithms that efficiently run on modern machines are key for the performance of these applications. With the recent shift to using GPUs for general purpose compuing, researches have proposed several sorting algorithms for single-GPU systems. However, some workstations and HPC systems have multiple GPUs, and applications running on them are designed to use all available GPUs in the system. In this paper we present a high performance multi-GPU merge sort algorithm that solves the problem of sorting data distributed across several GPUs. Our merge sort algorithm first sorts the data on each GPU using an existing single-GPU sorting algorithm. Then, a series of merge steps produce a globally sorted array distributed across all the GPUs in the system. This merge phase is enabled by a novel pivot selection algorithm that ensures that merge steps always distribute data evenly among all GPUs. We also present the implementation of our sorting algorithm in CUDA, as well as a novel inter-GPU communication technique that enables this pivot selection algorithm. Experimental results show that an efficient implementation of our algorithm achieves a speed up of 1.9x when running on two GPUs and 3.3x when running on four GPUs, compared to sorting on a single GPU. At the same time, it is able to sort two and four times more records, compared to sorting on one GPU.

In the information age, the huge amount of data and information are exchanged which requires fast and efficient searching mechanisms for effective use of this information. There are various sequential searching algorithms to search an element in an unsorted array or sorted array of elements. A number of researchers have explored methods for improving the efficiency and speedup of search using parallel hardware, for eg. A 2-D Mesh of Processors can be used to solve various searching problems in O(n1/2) time regardless of any assumption about wire delay. We proposed an algorithm for searching on Hypercube Interconnection network that solves the basic query problem, namely given an integer x, it is required to search a file of records on the s field for x. Proposed algorithm produces a yes or no answer to such a query in O(log n) time.

Let A be a sorted array of n numbers and B a sorted array of m numbers, both in nondecreasing order, with n/spl les/m. We consider the problem of determining, for each element A(j), j=1, 2, ..., n, the unique element B(i), 0/spl les/i/spl les/m, such that B(i)/spl les/A(j) >

Merging two sorted arrays is a prominent building block for sorting and other functions. Its efficient parallelization requires balancing the load among compute cores, minimizing the extra work brought about by parallelization, and minimizing inter-thread synchronization requirements. Efficient use of memory is also important. We present a novel approach to partitioning the two sorted arrays into pairs of contiguous sequences of elements, one from each array, such that 1) each pair comprises any desired total number of elements, and 2) the elements of each pair form a contiguous sequence in the final merged sorted array. While the resulting partition and the computational complexity are similar to those of certain previous algorithms, our approach is different, extremely intuitive, and offers interesting insights. Based on this, we present a synchronization-free, cache-efficient merging (and sorting) algorithm. While we use CREW PRAM as the basis, our algorithm is easily adaptable to additional architectures. In fact, our approach is even relevant to sequential cache-efficient sorting. The algorithms and performance results are presented, along with important cache-related insights.

As Adaboost has a good performance in classification, it is widely used in pattern recognition. However it takes long time to generate the weak classifiers. For improving the training speed, this paper presents a fast Adaboost weak classifier training algorithm. Firstly, sort the Eigen values to an array from small to large, and then traverse the sorted array once to find the best threshold and bias. The experimental results show that this improved algorithm can increase the training speed by 6 to 8 times.

The spatial arrangement of a chemical compound plays an important role regarding the related properties or activities. A straightforward approach to encode the geometry is to enumerate pairwise spatial relationships between k substructures, like functional groups or subgraphs. This leads to a combinatorial explosion with the number of features of interest and redundant information. The goal of this work is to compute all possible k-subsets of spatial points and to extract a single canonical descriptor for each subset in sub-polynomial computation time. More precisely, the problem is to reduce the complexity of nk = n·(n - 1)...(n - k) possible relationships (patterns or descriptors) for n features and k-point relationships. We propose a two-step algorithm to solve this problem. A modified algorithm for the computation of the binomial coefficient computes the k-subsets [1] containing the possible combinations of the n relevant features. If a k-subset is completed in the inner recursion, the algorithm computes a canonical representation for it. By defining a natural order by means of the geometrical center of gravity of the k points, we extract k patterns that describe the distance to the center of gravity and type of the spatial feature k ∈ F. Then, the algorithm returns a unique identifier for the lexicographically sorted array of patterns. If applicable (), an additional identifier is added which has the form , where dij denotes the geometrical distance between features i, j. Else (), this step is omitted. Therefore, this approach also considers stereochemistry. Finally, one feature is returned for each k-subset resulting in a set of C(n, k) patterns describing the structure. The main result is that the number of features is reduced from nk to C(n, k), which equals the binomial coefficient. This procedure is useful in combination with similarity approaches that use spatial relationships, like pharmacophore searches, fingerprints, or graph kernels. We experimentally validated the algorithm on numerous QSAR benchmark sets in combination with the pharmacophore kernel [2].

Ring artifacts often appear in flat-detector CT because of imperfect or defect detector elements or calibration. In high-spatial resolution CT images reducing such artifacts becomes a necessity. In this paper, we used the post-processing ring correction in polar coordinates (RCP)1 to eliminate the ring artifacts. The median filter is applied to the uncorrected images in polar coordinates and ring artifacts are extracted from the original images. The algorithm has a very high computational cost due to the time-expensive median filtering and coordinate transformation on CPUs. Graphics processing units (GPUs)ca n be seen as parallel co-processors with high computational power. All steps of the RCP algorithm were implemented with CUDA2(Compute Unified Device Architecture, NVIDIA). We introduced a new GPU-based branchless vectorized median (BVM)filter. 3, 4 This algorithm is based on minmax sorting and keeps track of a sorted array from which values are deleted and to which new values are inserted. For comparison purpose a modified pivot median filter5 on GPUs was presented, which compares a pivot element to all other values and recursively finds the median element. We evaluated the performance of the RCP method using 512 slices, each slice consisted of 512×512 pixels. This post-processing method efficiently reduces ring artifacts in the reconstructed images and improves image quality. Our CUDAbased RCP is up to 13.6 times faster than the optimized CPU-based (single core)r outine. Comparing our two GPU-based median filters showed a performance benefit by roughly 60% when switching from Pivot to BVM code. The main reason is that the BVM algorithm is branchless and makes use of data-level parallelism. The BVM method is better suited to the model of modern graphics processing. A multi-GPU solution showed that the performance scaled nearly linearly.

Median filtering is an important tool in signal or image processing. Based on the vector capabilities of modern hardware, which allows for vectorized min, max and mask operations, we provide a median algorithm of complexity O(NM) that is both branchless and vectorized. In contrast to conventional fast median filters, whose run-time is data-dependent and that can operate only on scalar data, its runtime is predictable and data-independent and it can simultaneously operate on several one-dimensional signals thereby making use of data-level parallelism. Our branchless vectorized median (BVM) filter keeps track of a sorted array from which values are deleted and to which new values are inserted. As a spin-off effect we could also use our work to provide a data sorting algorithm that is branchless and vectorized. Although it is of O(M2) computational complexity while other sort algorithms are of O(M lnM) computational complexity, at least for typical data, it may outperform other implementations for small M. This is mainly due to the fact that we have no unexpected branches which would stall the instruction pipeline and that we can simultaneously operate on vectors of data. Here, however, we focus on median filtering. BVM is compared to a median filter based on doubly linked lists (DLL) and to the median implementation of the Intel Performance Primitives (IPP) library. The comparison uses constant data and linear data, which are two unrealistic settings, and random data, which is more realistic. For constant data IPP is up to five times faster than BVM whose run-time does not depend on the data themselves. However, regarding the realistic case of median filtering noisy data BVM outperforms DLL by about a factor of 1.5 and IPP by about a factor of 2 in our CPU-based implementations, which is far more than we did expect initially.