18 papers · ranked by Valyu relevance
Carbonell Juan Pablo, Solsona, José E., Szasz + 3 more
We provide full certifications of two versions of merge sort of arrays in the verification-aware programming language Dafny. We start by considering schemas for applying the divide-and-conquer or partition method of solution to specifications given by pre- and post-conditions involving linear arrays. We then derive the…
Jesper Larsson Träff
This note makes an observation that significantly simplifies a number of previous parallel, two-way merge algorithms based on binary search and sequential merge in parallel. First, it is shown that the additional merge step of distinguished elements as found in previous algorithms is not necessary, thus simplifying the…
Philippe J. Giabbanelli, Joseph G. Peters
In distributed classification, each learner observes its environment and deduces a classifier. As a learner has only a local view of its environment, classifiers can be exchanged among the learners and integrated, or merged, to improve accuracy. However, the operation of merging is not defined for most classifiers.…
Sam Buss, Alexander Knop
We introduce new stable natural merge sort algorithms, called 2-merge sort and α-merge sort. We prove upper and lower bounds for several merge sort algorithms, including Timsort, Shivers' sort, α-stack sorts, and our new 2-merge and α-merge sorts. The upper and lower bounds have the forms c · n log m and c · n log n…
Oded Green, Saher Odeh, Yitzhak Birk
We present a novel, visually intuitive approach to partitioning two input 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 output merged sorted…
Mohammad Abdur Rob, Md. Zakir Hossen, Md. Kamal Hossen, Md. Mithun Ali + 2 more
Sorting algorithms play a crucial role in computing, but most are designed with rigid structure that are only efficient under certain conditions. Although some sorting algorithms perform well in some circumstances, they do not perform well on some resistant platforms. This study introduces Wall-L Merge Sort, which…
Willi Mann, Nikolaus Augsten, Christian S. Jensen, Mateusz Pawlik
We provide efficient support for applications that aim to continuously find pairs of similar sets in rapid streams, such as Twitter streams that emit tweets as sets of words. Using a sliding window model, the top-k result changes as new sets enter the window or existing ones leave the window. Specifically, when a set…
Jamshed Khan, Tobias Rubel, Erin Molloy, Laxman Dhulipala + 1 more
Purpose String indexes such as the suffix array (sa) and the closely related longest common prefix (lcp) array are fundamental objects in bioinformatics and have a wide variety of applications. Despite their importance in practice, few scalable parallel algorithms for constructing these are known, and the existing…
Alejandro Hernandez Wences, Michael C. Schatz
Genome assembly projects typically run multiple algorithms in an attempt to find the single best assembly, although those assemblies often have complementary, if untapped, strengths and weaknesses. We present our metassembler algorithm that merges multiple assemblies of a genome into a single superior sequence. We…
Feng Shi, Zhiyuan Yan, Meghanad D. Wagh
—Merging-based sorting networks are an important family of sorting networks. Most merge sorting networks are based on 2-way or multi-way merging algorithms using 2-sorters as basic building blocks. An alternative is to use n-sorters, instead of 2-sorters, as the basic building blocks so as to greatly reduce the number…
Nikolas Bernaola, Mario Michiels, Pedro Larrañaga, Concha Bielza
We present the Fast Greedy Equivalence Search (FGES)-Merge, a new method for learning the structure of gene regulatory networks via merging locally learned Bayesian networks, based on the fast greedy equivalent search algorithm. The method is competitive with the state of the art in terms of the Matthews correlation…
Sirilak Ketchaya, Apisit Rattanatranurak
Quicksort is an important algorithm that uses the divide and conquer concept, and it can be run to solve any problem. The performance of the algorithm can be improved by implementing this algorithm in parallel. In this paper, the parallel sorting algorithm named the Multi-Deque Partition Dual-Deque Merge Sorting…
Aaron S. Brewster, Daniel W. Paley, Asmit Bhowmick, David W. Mittan-Moreau + 5 more
The cctbx.xfel suite of processing programs and tools allows fast, visual analysis of serial diffraction images from synchrotrons and XFELs. Built on DIALS and cctbx, cctbx.xfel is designed for real-time and post-experiment processing with a fully featured graphical user interface. Users can quickly identify hitrates…
Thomas Krannich, W. Timothy J. White, Sebastian Niehus, Guillaume Holley + 2 more
With the increasing throughput of sequencing technologies, structural vari-ant (SV) detection has become possible across ten of thousands of genomes. Non-reference sequence (NRS) variants have drawn less attention compared to other types of SVs due to the computational complexity of detecting them. When using…
Vladimir Smirnov, Tandy Warnow
Phylogeny estimation is an important part of much biological research, but large-scale tree estimation is infeasible using standard methods due to computational issues. Recently, an approach to large-scale phylogeny has been proposed that divides a set of species into disjoint subsets, computes trees on the subsets…
Adam C. English, Vipin K. Menon, Richard Gibbs, Ginger A. Metcalf + 1 more
For multi-sample structural variant analyses like merging, benchmarking, and annotation, the fundamental operation is to identify when two SVs are the same. Commonly applied approaches for comparing SVs were developed alongside technologies which produce ill-defined boundaries. As SV detection becomes more exact…
Charu Manivannan, Jakub Krukar, Angela Schwering, Saeid Norouzian-Maleki
'Saeid Norouzian-Maleki'] Sketch maps are valuable tools used across various disciplines including spatial cognition, environmental psychology, and spatial reasoning. A common approach to evaluate sketch maps in research is to align and compare them with metric maps. However, sketch maps are highly abstract and contain…
Trevor Gokey, David L. Mobley
Molecular mechanics force fields require a chemical perception model to assign parameters to molecules. A recent advancement in force fields is the use of the SMARTS substructure query language as the perception model. Although it is straightforward to write SMARTS patterns to define new force field parameters, it is…