Mergesort is a popular algorithm for sorting real-world workloads as it is immune to data skewness, suitable for parallelization using vectorized intrinsics, and relatively simple to multi-thread. In this paper, we introduce Origami , an in-memory merge-sort framework that is optimized for scalar, as well as all current SIMD (single-instruction multiple-data) CPU architectures. For each vector-extension set (e.g., SSE, AVX2, AVX-512), we present an in-register sorter for small sequences that is up to 8× faster than prior methods and a branchless streaming merger that achieves up to a 1.5× speed-up over the naive merge. In addition, we introduce a cache-residing quad-merge tree to avoid bottlenecking on memory bandwidth and a parallel partitioning scheme to maximize thread-level concurrency. We develop an end-to-end sort with these components and produce a highly utilized mergesort pipeline by reducing the synchronization overhead between threads. Single-threaded Origami performs up to 2× faster than the closest competitor and achieves a nearly perfect speed-up in multi-core environments.

Many applications in data analytics, information retrieval, and cluster computing process huge amounts of information. The complexity of involved algorithms and massive scale of data require a programming model that can not only offer a simple abstraction for inputs larger than RAM, but also squeeze maximum performance out of the available hardware. While these are usually conflicting goals, we show that this does not have to be the case for sequentially-processed data, i.e., in streaming applications. We develop a set of algorithms called Vortex that force the application to generate access violations (i.e., page faults) during processing of the stream, which are transparently handled in such a way that creates an illusion of an infinite buffer that fits into a regular C/C++ pointer. This design makes Vortex by far the simplest-to-use and fastest platform for various types of streaming I/O, inter-thread data transfer, and key shuffling. We introduce several such applications -- file I/O wrapper, bounded producer-consumer pipeline, vanishing array, key-partitioning engine, and novel in-place radix sort that is 3-4 times faster than the best prior approaches.

In this demonstration, we present VizQ, an efficient, scalable, and interactive system to process and visualize a comprehensive collection of novel visibility queries in the presence of obstacles in 3D space. Specifically, we demonstrate four types of query processing: (i) k Maximum Visibility Query (kMVQ), that finds k locations with the maximum visibility of a target object (ii) Visibility Color Map (VCM), where each point in the space is assigned a color value denoting the visibility measure of the target (iii) Continuous Maximum Visibility (CMV) that continuously finds the location that provides the best view of a moving target, and (iv) Text Visibility Color Map (TVCM), where VCM is generated considering readability of text data displayed on a target. We are the first to propose efficient algorithms to run all of the above four types of visibility queries in the context of a large number of 3D obstacle database. We exploit human visibility metrics to design our data structures and algorithms to efficiently process queries, and our approaches outperform baseline approaches in several order of magnitude both in terms of I/Os and processing time. The link of our demonstration video is https://youtu.be/rcizJtFvQfU.