15 papers · ranked by Valyu relevance
Alexander Narvaez
Sorting over bounded-universe integer keys has traditionally relied on counting sort and radix sort, both of which incur mandatory prefix-sum passes, auxiliary scatter buffers, or multiple permutation passes. This paper introduces DialSort, a non-comparative sorting architecture based on the self-indexing principle…
Vasiliy S. Shlyk
Integer sorts in OLAP engines often run on columns whose cardinality $K$ is much smaller than the array length $N$. After a group-by stage the intermediate key column has $K$ bounded by the number of distinct group keys, and even a column-store scan typically operates on dictionary-encoded categorical fields where $K$…
Mohammed Alaa Ala’anzy, Nurdaulet Tolendi, Baizhan Baubek, Abdulmohsen Algarni + 1 more
Sorting can be approached in two main ways: sequentially and in parallel. In sequential sorting, data is processed in a single-threaded manner, which can be slow for large datasets. However, parallel sorting divides the task across multiple processing units, enabling faster results by processing data simultaneously.…
Julia Golonka, Filip Krużel, Rosario Schiano Lo Moriello
Resource-constrained sensor nodes in Internet-of-Things (IoT) and embedded sensing applications frequently rely on low-cost microcontrollers, where even basic algorithmic choices directly impact latency, energy consumption, and memory footprint. This study evaluates six sorting algorithms-Bubble Sort, Insertion Sort…
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…
Hriday Jain, Ketan Sabale, Aditya Shastri, Hiren Kumar Thakkar + 1 more
Sorting is a foundational primitive in modern data processing, influencing the execution speed of high-performance data pipelines. However, the algorithmic landscape is currently bifurcated by a pervasive "Stability Tax": practitioners must sacrifice either order preservation for high throughput or execution speed for…
Robert Clausecker, Florian Schintke
We present Radsort, a variant of LSD radix sort, sorting data with $\mathcal O(\sqrt n)$ additional space. Radsort is stable, admits a simple implementation and is easy to parallelise. For arrays exceeding a size of around 2 MiB it outperforms a conventional out-of-place LSD radix sort.
G. Jäger, Nacim Oijid
For the buffet, the waiter of a restaurant gets a large stack of pancakes from the overworked cook. As usual, one side is burnt, and as the level of batter decreases, the pancakes became smaller and smaller. Hence, the waiter ends up with a stack of one-sided burnt pancakes sorted by size, with the larger at the bottom…
Kai Yi
Let $s$ denote West's stack-sorting map. In 2020, Defant characterized and enumerated the set $s^{n-m}(S_n)$ for $n \geq 2m-3$. While $|s^{n-m}(S_n)| = B_m$ when $n \geq 2m-2$, where $B_m$ denotes the $m$th Bell number, there are additional permutations when $n = 2m-3$. In this paper, we explore the more complex $n =…
Simon Van de Vyver, Tibo Vande Moortele, Peter Dawyndt, Bart Mesuere + 1 more
Background Pattern matching is a fundamental challenge in bioinformatics, especially in the fields of genomics, transcriptomics and proteomics. Efficient indexing structures, such as suffix arrays, are critical for searching large datasets. A sparse suffix array (SSA) retains only suffixes at every k-th position in the…
Rahul Varki, Christina Boucher
Relative Lempel–Ziv (RLZ) is an effective compression method for large, repetitive collections; however, the fundamental primitives required to elevate it from a passive archival format to a tractable representation for compressed construction have yet to be fully established. In this paper, we introduce an algorithmic…
Rahul Varki, Christina Boucher
Relative Lempel-Ziv (RLZ) is an effective compression method for large, repetitive collections; however, the fundamental primitives required to elevate it from a passive archival format to a tractable representation for compressed construction have yet to be fully established. In this paper, we introduce an algorithmic…
Anastasia C. Diseth, Simon J. Puglisi
Given a sequence S of subsets of symbols drawn from an alphabet of size σ, a subset rank query srank(i, c) asks for the number of subsets before the ith subset that contain the symbol c. It was recently shown (Alanko et al., Proc. SIAM ACDA, 2023) that subset rank queries on the spectral Burrows-Wheeler lead to…
Samuel Garcia, Chris Halcrow, Charlie Windolf, Zachary M. McKenzie + 5 more
Spike sorting is an algorithmic process that extracts the activity of individual neurons from extracellular electrophysiology recordings. With the ballooning use of high density probes, such as Neuropixels, this essential processing step is increasingly becoming time consuming and computationally expensive. Although…
Daniela Valério, Samuel Debray, Alireza Karami, Maxime Cauté + 2 more
How does the human brain represent the meaning of abstract symbols? Some theories postulate the existence of semantic spaces where concepts occupy positions that reflect their conceptual relationships. In the number domain, psychological evidence suggests that integers are represented along a mental number line which…