ABSTRACT Background When sharing or logging numerical data, we must convert binary floating‐point numbers into their decimal string representations. For example, the number π might become 3.1415927. Engineers have perfected many algorithms for producing such accurate, short strings. Aims We present an empirical comparison across diverse hardware architectures and datasets. Methods We benchmarked several established and recent algorithms for converting binary floating‐point numbers (IEEE 754 double‐precision) to their decimal string representations. We executed the conversions across multiple CPU microarchitectures, including recent Intel (Alder Lake, Skylake), AMD (Zen 3, Zen 4), and ARM (Apple M1/M2, Neoverse) processors, using recent versions of GCC, Clang, and platform‐specific compilers and several datasets. Results and Conclusions Cutting‐edge techniques like Schubfach and Dragonbox achieve up to a tenfold speedup over Steele and White's Dragon4, executing as few as 210 instructions per conversion compared to Dragon4's 1500–5000 instructions. Often per their specification, none of the implementations we surveyed consistently produced the shortest possible strings—some generate outputs up to 30% longer than optimal. We find that standard library implementations in languages such as C++ and Swift execute significantly more instructions than the fastest methods, with performance gaps varying across CPU architectures and compilers. We suggest some optimization targets for future research.

ABSTRACT Objective Converting binary integers to variable‐length decimal strings is a fundamental operation in computing. Conventional fast approaches rely on recursive division and small lookup tables. The goal of this work is to develop a significantly faster method for this task. Methods We propose a SIMD‐based algorithm that leverages integer multiply‐add instructions available on recent AMD and Intel processors. Our method eliminates lookup tables entirely and computes multiple quotients and remainders in parallel. Additionally, we introduce a dual‐variant design with dynamic selection that adapts to input characteristics: a branch‐heavy variant optimized for homogeneous digit‐length distributions and a branch‐light variant for heterogeneous datasets. Results Our single‐core algorithm consistently outperforms all competing methods across the full range of integer sizes. It runs 1.4–2× faster than the closest competitor and 2–4× faster than the C++ standard library function ‘ std::to_chars ’ across tested workloads. Conclusion The proposed SIMD‐based approach with dual‐variant dynamic selection provides a substantial performance improvement for integer‐to‐decimal conversion, delivering superior speed without relying on traditional lookup tables.

Massive Open Online Courses (MOOCs) face significant challenges due to low completion rates, primarily caused by insufficient personalized support for learners. To address this, we developed a pedagogical AI-powered conversational agent enhanced with Retrieval-Augmented Generation (RAG) to provide real-time, contextually relevant support. Our evaluation with 25 learners demonstrated a statistically significant knowledge gain in the experimental group compared to the control group. Additionally, the agent achieved a high System Usability Scale (SUS) score. These findings highlight the potential of AI technologies to enhance online learning environments and inform future research on their role as learning companions in distance education.

ABSTRACT The positional population count operation pospopcnt counts for an array of ‐bit words how often each of the bits was set. Various applications in bioinformatics, database engineering, and digital processing exist. Building on earlier work by Klarqvist et al., we show how positional population counts can be rapidly computed using SIMD techniques with good performance from the first byte, approaching memory‐bound speeds for input arrays of as little as 4 KiB. Improvements include an improved algorithm structure, better handling of unaligned and very short arrays, as well as faster bit‐parallel accumulation of intermediate results. We provide a generic algorithm description as well as implementations for various SIMD instruction set extensions, including Intel AVX2, AVX‐512, and ARM ASIMD, and discuss the adaptation of our algorithm to other platforms.

Summary Pseudorandom values are often generated as 64‐bit binary words. These random words need to be converted into ranged values without statistical bias. We present an efficient algorithm to generate multiple independent uniformly‐random bounded integers from a single uniformly‐random binary word, without any bias. In the common case, our method uses one multiplication and no division operations per value produced. In practice, our algorithm can more than double the speed of unbiased random shuffling for small to moderately large arrays.

ABSTRACT Objectives To enhance the throughput of DNS parsing by addressing the computational expense of processing large plain text DNS zone files. To specifically increase the speed of parsing DNS zone files compared to existing state‐of‐the‐art parsers. Method Development of a new approach named simdzone for DNS parsing. Utilization of data parallelism through Single Instruction Multiple Data (SIMD) instructions available on modern processors to accelerate parsing operations. Result The simdzone approach significantly increased parsing speeds, being several times faster than the parsers in Knot DNS and NLnet Labs' Name Server Daemon (NSD). The software library developed from this approach was integrated into NSD, replacing its previous parser. Conclusion The implementation of SIMD‐based data parallelism in DNS parsing provides a substantial performance improvement, making it a viable solution for handling large DNS zone files more efficiently. This not only reduces processing time but also enhances the overall functionality of DNS services.

ABSTRACT Background Modern processors feature Single Instruction, Multiple Data (SIMD) instructions capable of processing 16 bytes or more simultaneously, enabling significant performance enhancements in data‐intensive tasks. Two major Web browser engines (WebKit and Blink) have adopted SIMD algorithms for parsing HTML. Objective This study reviews recent advances in utilizing SIMD instructions to accelerate HTML parsing through vectorized classification techniques. Methods We compare these HTML parsing techniques with a faster alternative. Performance is benchmarked against traditional methods on recent ARM processors. Results Our measurements demonstrate a 20‐fold performance improvement in HTML scanning using SIMD‐based approaches compared to conventional parsing methods on modern ARM architectures. Conclusion These findings underscore the transformative potential of SIMD‐based algorithms in optimizing Web browser performance, offering substantial speedups for processing Internet formats and HTML parsing.

Abstract We sometimes need to compute the most significant digits of the product of small integers with a multiplier requiring much storage, e.g. a large integer (e.g. $5^{100}$) or an irrational number ($\pi $). We only need to access the most significant digits of the multiplier—as long as the integers are sufficiently small. We provide an efficient algorithm to compute the range of integers given a truncated multiplier and a desired number of digits.

Summary JSON is a popular standard for data interchange on the Internet. Ingesting JSON documents can be a performance bottleneck. A popular parsing strategy consists in converting the input text into a tree‐based data structure—sometimes called a Document Object Model or DOM. We designed and implemented a novel JSON parsing interface—called On‐Demand—that appears to the programmer like a conventional DOM‐based approach. However, the underlying implementation is a pointer iterating through the content, only materializing the results (objects, arrays, strings, numbers) lazily. On recent commodity processors, an implementation of our approach provides superior performance in multiple benchmarks. To ensure reproducibility, our work is freely available as open source software. Several systems use On Demand: for example, Apache Doris, the Node.js JavaScript runtime, Milvus, and Velox.

Abstract URLs are fundamental elements of web applications. By applying vector algorithms, we built a fast standard‐compliant C++ implementation. Our parser uses three times fewer instructions than competing parsers following the WHATWG standard (e.g., Servo's rust‐url) and up to eight times fewer instructions than the popular curl parser. The Node.js environment adopted our C++ library. In our tests on realistic data, a recent Node.js version (20.0) with our parser is four to five times faster than the last version with the legacy URL parser.

Abstract Intel includes in its recent processors a powerful set of instructions capable of processing 512‐bit registers with a single instruction (AVX‐512). Some of these instructions have no equivalent in earlier instruction sets. We leverage these instructions to efficiently transcode strings between the most common formats: UTF‐8 and UTF‐16. With our novel algorithms, we are often twice as fast as the previous best solutions. For example, we transcode Chinese text from UTF‐8 to UTF‐16 at more than 5 GiB using fewer than 2 CPU instructions per character. To ensure reproducibility, we make our software freely available as an open‐source library. Our library is part of the popular Node.js JavaScript runtime.

Summary In recent work, Lemire (2021) presented a fast algorithm to convert number strings into binary floating‐point numbers. The algorithm has been adopted by several important systems: for example, it is part of the runtime libraries of GCC 12, Rust 1.55, and Go 1.16. The algorithm parses any number string with a significand containing no more than 19 digits into an IEEE floating‐point number. However, there is a check leading to a fallback function to ensure correctness. This fallback function is never called in practice. We prove that the fallback is unnecessary. Thus we can slightly simplify the algorithm and its implementation.

Abstract In software, text is often represented using Unicode formats (UTF‐8 and UTF‐16). We frequently have to convert text from one format to the other, a process called transcoding. Popular transcoding functions are slower than state‐of‐the‐art disks and networks. These transcoding functions make little use of the single‐instruction‐multiple‐data (SIMD) instructions available on commodity processors. By designing transcoding algorithms for SIMD instructions, we multiply the speed of transcoding on current systems ( 64 and ARM). To ensure reproducibility, we make our software freely available as an open source library.

Summary In several fields such as statistics, machine learning, and bioinformatics, categorical variables are frequently represented as one‐hot encoded vectors. For example, given eight distinct values, we map each value to a byte where only a single bit has been set. We are motivated to quickly compute statistics over such encodings. Given a stream of k‐bit words, we seek to compute k distinct sums corresponding to bit values at indexes 0, 1, 2, …, k − 1. If the k‐bit words are one‐hot encoded then the sums correspond to a frequency histogram. This multiple‐sum problem is a generalization of the population‐count problem where we seek the sum of all bit values. Accordingly, we refer to the multiple‐sum problem as a positional population‐count. Using SIMD (Single Instruction, Multiple Data) instructions from recent Intel processors, we describe algorithms for computing the 16‐bit position population count using less than half of a CPU cycle per 16‐bit word. Our best approach uses up to 400 times fewer instructions and is up to 50 times faster than baseline code using only regular (non‐SIMD) instructions, for sufficiently large inputs.

Abstract The majority of text is stored in UTF‐8, which must be validated on ingestion. We present the lookupalgorithm, which outperforms UTF‐8 validation routines used in many libraries and languages by more than 10 times using commonly available single‐instruction‐multiple‐data instructions. To ensure reproducibility, our work is freely available as open source software.

Abstract With disks and networks providing gigabytes per second, parsing decimal numbers from strings becomes a bottleneck. We consider the problem of parsing decimal numbers to the nearest binary floating‐point value. The general problem requires variable‐precision arithmetic. However, we need at most 17 digits to represent 64‐bit standard floating‐point numbers (IEEE 754). Thus, we can represent the decimal significand with a single 64‐bit word. By combining the significand and precomputed tables, we can compute the nearest floating‐point number using as few as one or two 64‐bit multiplications. Our implementation can be several times faster than conventional functions present in standard C libraries on modern 64‐bit systems (Intel, AMD, ARM, and POWER9). Our work is available as open source software used by major systems such as Apache Arrow and Yandex ClickHouse. The Go standard library has adopted a version of our approach.

Summary Many common document formats on the Internet are text‐only such as email (MIME) and the Web (HTML, JavaScript, JSON, and XML). To include images or executable code in these documents, we first encode them as text using base64. Standard base64 encoding uses 64 ASCII characters, ie, both lower and upper case Latin letters, digits and two other symbols. We show how we can encode and decode base64 data at nearly the speed of a memory copy (memcpy) on recent Intel processors, as long as the data does not fit in the first‐level (L1) cache. We use the single‐instruction‐multiple‐data instruction set AVX‐512 available on commodity processors. Our implementation generates several times fewer instructions than previous single‐instruction‐multiple‐data‐accelerated base64 codecs. It is also more versatile, as it can be adapted, even at runtime, to any base64 variant by only changing constants.

Summary On common processors, integer multiplication is many times faster than integer division. Dividing a numerator n by a divisor d is mathematically equivalent to multiplication by the inverse of the divisor (n/d=n∗1/d). If the divisor is known in advance, or if repeated integer divisions will be performed with the same divisor, it can be beneficial to substitute a less costly multiplication for an expensive division. Currently, the remainder of the division by a constant is computed from the quotient by a multiplication and a subtraction. However, if just the remainder is desired and the quotient is unneeded, this may be suboptimal. We present a generally applicable algorithm to compute the remainder more directly. Specifically, we use the fractional portion of the product of the numerator and the inverse of the divisor. On this basis, we also present a new and simpler divisibility algorithm to detect nonzero remainders. We also derive new tight bounds on the precision required when representing the inverse of the divisor. Furthermore, we present simple C implementations that beat the optimized code produced by state‐of‐the‐art C compilers on recent x64 processors (eg, Intel Skylake and AMD Ryzen), sometimes by more than 25%. On all tested platforms, including 64‐bit ARM and POWER8, our divisibility test functions are faster than state‐of‐the‐art Granlund‐Montgomery divisibility test functions, sometimes by more than 50%.

Apache Calcite is a foundational software framework that provides query processing, optimization, and query language support to many popular open-source data processing systems such as Apache Hive, Apache Storm, Apache Flink, Druid, and MapD. The goal of this paper is to formally introduce Calcite to the broader research community, brie y present its history, and describe its architecture, features, functionality, and patterns for adoption. Calcite's architecture consists of a modular and extensible query optimizer with hundreds of built-in optimization rules, a query processor capable of processing a variety of query languages, an adapter architecture designed for extensibility, and support for heterogeneous data models and stores (relational, semi-structured, streaming, and geospatial). This exible, embeddable, and extensible architecture is what makes Calcite an attractive choice for adoption in big-data frameworks. It is an active project that continues to introduce support for the new types of data sources, query languages, and approaches to query processing and optimization.

Counting the number of ones in a binary stream is a common operation in database, information-retrieval, cryptographic and machine-learning applications. Most processors have dedicated instructions to count the number of ones in a word (e.g. popcnt on ×64 processors). Maybe surprisingly, we show that a vectorized approach using SIMD instructions can be twice as fast as using the dedicated instructions on recent Intel processors. The benefits can be even greater for applications such as similarity measures (e.g. the Jaccard index) that require additional Boolean operations. Our approach has been adopted by LLVM: it is used by its popular C compiler (Clang).

Codd’s relational model describes just one possible world. To better cope with incomplete information, extended database models allow several possible worlds. Vague tables are one such convenient extended model where attributes accept sets of possible values (e.g., the manager is either Jill or Bob). However, conceptual database design in such cases remains an open problem. In particular, there is no canonical definition of functional dependencies (FDs) over possible worlds (e.g., each employee has just one manager). We identify several desirable properties that the semantics of such FDs should meet including Armstrong’s axioms, the independence from irrelevant attributes, seamless satisfaction and implied by strong satisfaction. We show that we can define FDs such that they have all our desirable properties over vague tables. However, we also show that no notion of FD can satisfy all our desirable properties over a more general model (disjunctive tables). Our work formalizes a trade-off between having a general model and having well-behaved FDs.

Summary Compressed bitmap indexes are used in systems such as Git or Oracle to accelerate queries. They represent sets and often support operations such as unions, intersections, differences, and symmetric differences. Several important systems such as Elasticsearch, Apache Spark, Netflix's Atlas, LinkedIn's Pivot, Metamarkets' Druid, Pilosa, Apache Hive, Apache Tez, Microsoft Visual Studio Team Services, and Apache Kylin rely on a specific type of compressed bitmap index called Roaring. We present an optimized software library written in C implementing Roaring bitmaps: CRoaring. It benefits from several algorithms designed for the single‐instruction–multiple‐data instructions available on commodity processors. In particular, we present vectorized algorithms to compute the intersection, union, difference, and symmetric difference between arrays. We benchmark the library against a wide range of competitive alternatives, identifying weaknesses and strengths in our software. Our work is available under a liberal open‐source license.

Automated service composition fulfills complex tasks by combining different existing web services together. Unfortunately, optimizing service composition is still a challenging area that needs to be addressed. In this article, we propose a novel relational database approach for automated service composition. All possible service combinations are generated beforehand and stored in a relational database. When a user request comes, our system composes SQL queries to search in the database and return the best Quality of Service (QoS) solutions. We test the performance of the proposed system with a web service challenge data set. Our experimental results demonstrate that this system can always find top-K valid solutions to satisfy user's functional and non-functional requirements.

Web developers use base64 formats to include images, fonts, sounds, and other resources directly inside HTML, JavaScript, JSON, and XML files. We estimate that billions of base64 messages are decoded every day. We are motivated to improve the efficiency of base64 encoding and decoding. Compared to state-of-the-art implementations, we multiply the speeds of both the encoding (≈ 10 ×0) and the decoding (≈ 7 ×). We achieve these good results by using the single-instruction-multiple-data instructions available on recent Intel processors (AVX2). Our accelerated software abides by the specification and reports errors when encountering characters outside of the base64 set. It is available online as free software under a liberal license.

Summary Random hashing can provide guarantees regarding the performance of data structures such as hash tables – even in an adversarial setting. Many existing families of hash functions are universal: given two data objects, the probability that they have the same hash value is low given that we pick hash functions at random. However, universality fails to ensure that all hash functions are well behaved. We might further require regularity: when picking data objects at random they should have a low probability of having the same hash value, for any fixed hash function. We present the efficient implementation of a family of non‐cryptographic hash functions (PM+) offering good running times, good memory usage, and distinguishing theoretical guarantees: almost universality and component‐wise regularity. On a variety of platforms, our implementations are comparable with the state of the art in performance. On recent Intel processors, PM+ achieves a speed of 4.7 bytes per cycle for 32‐bit outputs and 3.3 bytes per cycle for 64‐bit outputs. We review vectorization through Single Instruction on Multiple Data instructions (e.g., AVX2) and optimizations for superscalar execution. Copyright © 2016 John Wiley & Sons, Ltd.

Web service composition enables the provision of existing resources on the web without investing in new infrastructure. However, searching an optimal composition solution with both functional and non-functional requirements is a computationally demanding problem: the time and space requirements may be insufferable due to the high number of available services. To alleviate this problem, we propose the application of a skyline operation to reduce the search space and improve the scalability. We design a system to solve the composition problem with two separate processes. The Graphplan approach finds a solution in a short time, the database approach may take longer time to find a solution, but the solution returned by this approach always has fewer redundant services with a better QoS value. Full Solution Indexing using Database (FSIDB) approach pre-computes all services combinations and store them as paths in a database. Partial pre-composing approach chooses "popular" paths generated by FSIDB approach and store them in a separate table. If the problem can be solved by these paths, there is no need to search the table with whole paths. We evaluate our approach with a web service challenge dataset.

In the current Big Data era, systems for collecting, storing and efficiently exploiting huge amounts of data are continually introduced, such as Hadoop, Apache Spark, Dremel, etc. Druid is one of theses systems especially designed to manage such data quantities, and allows to perform detailed real-time analysis on terabytes of data within sub-second latencies. One of the important Druid's requirements is fast data filtering. To insure that, Druid makes an extensive use of bitmap indexes. Previously, we introduced a new compressed bitmap index scheme called Roaring bitmap that has shown interesting results when compared to the bitmap compression scheme adopted by Druid: Concise. Since, Roaring bitmap has been integrated to Druid as an indexing solution. In this work, we produce an extensive series of experiments in order to compare Roaring bitmap and Concise time-space performances when used to accelerate Druid's OLAP queries and other kinds of operations Druid realizes on bitmaps, like: retrieving set bits from bitmaps, computing bitmap complements, aggregating several bitmaps with logical ORs and ANDs operations. Roaring bitmap has shown to improve up to ≈ 5× analytical queries response times under Druid compared to Concise.

Summary Bitmap indexes are commonly used in databases and search engines. By exploiting bit‐level parallelism, they can significantly accelerate queries. However, they can use much memory, and thus, we might prefer compressed bitmap indexes. Following Oracle's lead, bitmaps are often compressed using run‐length encoding (RLE). Building on prior work, we introduce the Roaring compressed bitmap format: it uses packed arrays for compression instead of RLE. We compare it to two high‐performance RLE‐based bitmap encoding techniques: Word Aligned Hybrid compression scheme and Compressed ‘n’ Composable Integer Set. On synthetic and real data, we find that Roaring bitmaps (1) often compress significantly better (e.g., 2×) and (2) are faster than the compressed alternatives (up to 900× faster for intersections). Our results challenge the view that RLE‐based bitmap compression is best. Copyright © 2015 John Wiley & Sons, Ltd.

Summary Compressed bitmap indexes are used to speed up simple aggregate queries in databases. Indeed, set operations like intersections, unions and complements can be represented as logical operations (AND, OR and NOT) that are ideally suited for bitmaps. However, it is less obvious how to apply bitmaps to more advanced queries. For example, we might seek products in a store that meet some, but maybe not all, criteria. Such threshold queries generalize intersections and unions; they are often used in information‐retrieval and data‐mining applications. We introduce new algorithms that are sometimes three orders of magnitude faster than a naïve approach. Our work shows that bitmap indexes are more broadly applicable than is commonly believed. Copyright © 2014 John Wiley & Sons, Ltd.

Summary Sorted lists of integers are commonly used in inverted indexes and database systems. They are often compressed in memory. We can use the single‐instruction, multiple data (SIMD) instructions available in common processors to boost the speed of integer compression schemes. Our S4‐BP128‐D4 scheme uses as little as 0.7 CPU cycles per decoded 32‐bit integer while still providing state‐of‐the‐art compression. However, if the subsequent processing of the integers is slow, the effort spent on optimizing decompression speed can be wasted. To show that it does not have to be so, we (1) vectorize and optimize the intersection of posting lists; (2) introduce the SIMD GALLOPING algorithm. We exploit the fact that one SIMD instruction can compare four pairs of 32‐bit integers at once. We experiment with two Text REtrieval Conference (TREC) text collections, GOV2 and ClueWeb09 (category B), using logs from the TREC million‐query track. We show that using only the SIMD instructions ubiquitous in all modern CPUs, our techniques for conjunctive queries can double the speed of a state‐of‐the‐art approach. Copyright © 2015 John Wiley & Sons, Ltd.

Summary Compressed bitmap indexes are used in databases and search engines. Many bitmap compression techniques have been proposed, almost all relying primarily on run‐length encoding (RLE). However, on unsorted data, we can get superior performance with a hybrid compression technique that uses both uncompressed bitmaps and packed arrays inside a two‐level tree. An instance of this technique, Roaring, has recently been proposed. Due to its good performance, it has been adopted by several production platforms (e.g., Apache Lucene, Apache Spark, Apache Kylin, and Druid). Yet there are cases where run‐length‐encoded bitmaps are smaller than the original Roaring bitmaps—typically when the data are sorted so that the bitmaps contain long compressible runs. To better handle these cases, we build a new Roaring hybrid that combines uncompressed bitmaps, packed arrays, and RLE‐compressed segments. The result is a new Roaring format that compresses better. Overall, our new implementation of Roaring can be several times faster (up to two orders of magnitude) than the implementations of traditional RLE‐based alternatives (WAH, Concise, and EWAH) while compressing better. We review the design choices and optimizations that make these good results possible. Copyright © 2016 John Wiley & Sons, Ltd.

Functional dependencies (FDs) are an integral part of database design. However, they are only defined when we exclude null markers. However, we commonly use null markers in practice. To bridge this gap between theory and practice, researchers have proposed definitions of FDs over relations with null markers. Though sound, these definitions lack some qualities that we find desirable. For example, some fail to satisfy Armstrong's axioms—while these axioms are part of the foundation of common database methodologies. We propose a set of properties that any extension of FDs over relations with null markers should possess. We then propose two new extensions having these properties. These extensions attempt to allow null markers where they make sense to practitioners. They both support Armstrong's axioms and provide realizablenull markers: at any time, some or all of the null markers can be replaced by actual values without causing an anomaly. Our proposals may improve database designs.

The importance of a research article is routinely measured by counting how many times it has been cited. However, treating all citations with equal weight ignores the wide variety of functions that citations perform. We want to automatically identify the subset of references in a bibliography that have a central academic influence on the citing paper. For this purpose, we examine the effectiveness of a variety of features for determining the academic influence of a citation. By asking authors to identify the key references in their own work, we created a data set in which citations were labeled according to their academic influence. Using automatic feature selection with supervised machine learning, we found a model for predicting academic influence that achieves good performance on this data set using only four features. The best features, among those we evaluated, were those based on the number of times a reference is mentioned in the body of a citing paper. The performance of these features inspired us to design an influence‐primed h‐index (the hip‐index). Unlike the conventional h‐index, it weights citations by how many times a reference is mentioned. According to our experiments, the hip‐index is a better indicator of researcher performance than the conventional h‐index.

In many important applications—such as search engines and relational database systems—data are stored in the form of arrays of integers. Encoding and, most importantly, decoding of these arrays consumes considerable CPU time. Therefore, substantial effort has been made to reduce costs associated with compression and decompression. In particular, researchers have exploited the superscalar nature of modern processors and single-instruction, multiple-data (SIMD) instructions. Nevertheless, we introduce a novel vectorized scheme called SIMD-BP128⋆ that improves over previously proposed vectorized approaches. It is nearly twice as fast as the previously fastest schemes on desktop processors (varint-G8IU and PFOR). At the same time, SIMD-BP128⋆ saves up to 2 bits/int. For even better compression, we propose another new vectorized scheme (SIMD-FastPFOR) that has a compression ratio within 10% of a state-of-the-art scheme (Simple-8b) while being two times faster during decoding. © 2013 The Authors. Software: Practice and Experience Published by John Wiley & Sons, Ltd.

Compression algorithms are important for data-oriented tasks, especially in the era of “Big Data.” Modern processors equipped with powerful SIMD instruction sets provide us with an opportunity for achieving better compression performance. Previous research has shown that SIMD-based optimizations can multiply decoding speeds. Following these pioneering studies, we propose a general approach to accelerate compression algorithms. By instantiating the approach, we have developed several novel integer compression algorithms, called Group-Simple, Group-Scheme, Group-AFOR, and Group-PFD, and implemented their corresponding vectorized versions. We evaluate the proposed algorithms on two public TREC datasets, a Wikipedia dataset, and a Twitter dataset. With competitive compression ratios and encoding speeds, our SIMD-based algorithms outperform state-of-the-art nonvectorized algorithms with respect to decoding speeds.

We present fast strongly universal string hashing families: they can process data at a rate of 0.2 CPU cycle per byte. Maybe surprisingly, we find that these families—though they require a large buffer of random numbers—are often faster than popular hash functions with weaker theoretical guarantees. Moreover, conventional wisdom is that hash functions with fewer multiplications are faster. Yet we find that they may fail to be faster due to operation pipelining. We present experimental results on several processors including low-power processors. Our tests include hash functions designed for processors with the carry-less multiplication instruction set. We also prove, using accessible proofs, the strong universality of our families.

Sorting database tables before compressing them improves the compression rate. Can we do better than the lexicographical order? For minimizing the number of runs in a run-length encoding compression scheme, the best approaches to row-ordering are derived from traveling salesman heuristics, although there is a significant trade-off between running time and compression. A new heuristic, Multiple Lists, which is a variant on Nearest Neighbor that trades off compression for a major running-time speedup, is a good option for very large tables. However, for some compression schemes, it is more important to generate long runs rather than few runs. For this case, another novel heuristic, Vortex, is promising. We find that we can improve run-length encoding up to a factor of 3 whereas we can improve prefix coding by up to 80%: these gains are on top of the gains due to lexicographically sorting the table. We prove that the new row reordering is optimal (within 10%) at minimizing the runs of identical values within columns, in a few cases.

Bitmap indexes must be compressed to reduce input/output costs and minimize CPU usage. To accelerate logical operations (AND, OR, XOR) over bitmaps, we use techniques based on run-length encoding (RLE), such as Word-Aligned Hybrid (WAH) compression. These techniques are sensitive to the order of the rows: a simple lexicographical sort can divide the index size by 9 and make indexes several times faster. We investigate reordering heuristics based on computed attribute-value histograms. Simply permuting the columns of the table based on these histograms can increase the sorting efficiency by 40%.

Data stored in a data warehouse are inherently multidimensional, unlike most data-pruning techniques (such as iceberg and top-k queries). However, analysts need to issue multidimensional queries. For example, an analyst may need to select not just the most profitable stores or---separately---the most profitable products, but simultaneous sets of stores and products fulfilling some profitability constraints. To fill this need, we propose a new operator, the diamond dice. Because of the interaction between dimensions, the computation of diamonds is challenging. We present the first diamond-dicing experiments on large data sets. Our external memory algorithm avoids potentially expensive random accesses. Experiments show that we can compute diamond cubes over fact tables containing 100 million facts and 500,000 distinct attribute values in less than an hour using a single-core PC.

For a massive I/O array of size n , we want to compute the first N local moments, for some constant N . Our simpler algorithms partition the array into consecutive ranges called bins, and apply not only to local-moment queries, but also to algebraic queries. With N buffers of size √ n , time complexity drops to O (√ n ). A more sophisticated approach uses hierarchical buffering and has a logarithmic time complexity ( O ( b log b n )), when using N hierarchical buffers of size n / b . Using overlapped bin buffering, we show that only one buffer is needed, as with wavelet-based algorithms, but using much less storage.

A data warehouse cannot materialize all possible views, hence we must estimate quickly, accurately, and reliably the size of views to determine the best candidates for materialization. Many available techniques for view-size estimation make particular statistical assumptions and their error can be large. Comparatively, unassuming probabilistic techniques are slower, but they estimate accurately and reliability very large view sizes using little memory. We compare five unassuming hashing-based view-size estimation techniques including Stochastic Probabilistic Counting and LOGLOG Probabilistic Counting. Our experiments show that only Generalized Counting, Gibbons-Tirthapura, and Adaptive Counting provide universally tight estimates irrespective of the size of the view; of those, only Adaptive Counting remains constantly fast as we increase the memory budget.

Time series are difficult to monitor, summarize and predict. Segmentation organizes time series into few intervals having uniform characteristics (flatness, linearity, modality, monotonicity and so on). For scalability, we require fast linear time algorithms. The popular piecewise linear model can determine where the data goes up or down and at what rate. Unfortunately, when the data does not follow a linear model, the computation of the local slope creates overfitting. We propose an adaptive time series model where the polynomial degree of each interval vary (constant, linear and so on). Given a number of regressors, the cost of each interval is its polynomial degree: constant intervals cost 1 regressor, linear intervals cost 2 regressors, and so on. Our goal is to minimize the Euclidean (l2) error for a given model complexity. Experimentally, we investigate the model where intervals can be either constant or linear. Over synthetic random walks, historical stock market prices, and electrocardiograms, the adaptive model provides a more accurate segmentation than the piecewise linear model without increasing the cross-validation error or the running time, while providing a richer vocabulary to applications. Implementation issues, such as numerical stability and real-world performance, are discussed.

Monotonicity is a simple yet significant qualitative characteristic. We consider the problem of segmenting an array in up to K segments. We want segments to be as monotonic as possible and to alternate signs. We propose a quality metric for this problem, present an optimal linear time algorithm based on novel formalism, and compare experimentally its performance to a linear time top-down regression algorithm. We show that our algorithm is faster and more accurate. Applications include pattern recognition and qualitative modeling.

Rating-based collaborative filtering is the process of predicting how a user would rate a given item from other user ratings. We propose three related slope one schemes with predictors of the form f (x) = x + b, which precompute the average difference between the ratings of one item and another for users who rated both. Slope one algorithms are easy to implement, efficient to query, reasonably accurate, and they support both online queries and dynamic updates, which makes them good candidates for real-world systems. The basic slope one scheme is suggested as a new reference scheme for collaborative filtering. By factoring in items that a user liked separately from items that a user disliked, we achieve results competitive with slower memory-based schemes over the standard benchmark EachMovie and Movielens data sets while better fulfilling the desiderata of CF applications.

The normalization of a data cube is the process of choosing an ordering for the attribute values, and the chosen ordering.Our optimized hybrid OLAP storage mechanism was observed to be 44% more storage efficient than ROLAP and the gains due to normalization alone accounted for 45% of this increase in efficiency.