Invited speakers
Daniel Lemire
University of Quebec (TELUQ), Canada
Algorithms for Modern Processor Architectures ▼
For decades, Dennard scaling propelled remarkable advancements in processor technology. As transistor sizes shrank, manufacturers increased clock frequencies to enhance computational speed while simultaneously reducing power consumption, adhering to the principle of constant power density. This synergy delivered consistent performance improvements in both hardware and software. However, over the past two decades, this trend has faltered: physical and thermal constraints have caused clock frequencies to plateau, often leaving software performance stagnant as it struggles to fully utilize available hardware capabilities. Nevertheless, modern processors provide substantial opportunities for performance optimization through advanced architectural features. These include enhanced Single-Instruction-Multiple-Data (SIMD) instructions—such as Scalable Vector Extensions (SVE) and AVX-512—which enable parallel processing of large datasets, greater memory-level parallelism to improve data access efficiency, advanced branch predictors to enhance instruction flow, and broader superscalar execution to execute multiple instructions per cycle more effectively. We advocate for a comprehensive approach: robust mathematical models grounded in a current and detailed understanding of system architecture. Through this lens, we explore how algorithmic design can leverage these characteristics of contemporary processors, drawing insights from practical case studies in widely used software. Our findings underscore the critical need to align software design with hardware capabilities to overcome the challenges of the post-Dennard era.
Giulia Bernardini
University of Trieste, Italy
Combinatorial Algorithms for String Data Privatization: Experimental Insights ▼
In this talk, I will present two combinatorial approaches to string data privatization. The first part of the talk introduces reverse-safe data structures (z-RSDS), which prevent data reconstruction by ensuring that any encoded information is consistent with at least z plausible original datasets. I will focus on an engineered implementation of the z-RSDS construction algorithm that, despite a theoretically high worst-case complexity, runs in only a few minutes for million-letter texts. The second part of the talk explores the interplay between data sanitization and frequent pattern mining, addressing how to hide sensitive patterns from a string while minimizing the number of spurious patterns that are introduced in the process. I will present several algorithmic formulations—ranging from exact ILP-based models to scalable greedy heuristics—and show how they are effective in preserving mining accuracy while enforcing privacy constraints on both synthetic and real-world datasets.
Sebastiano Vigna
University of Milan, Italy
ε-Cost Sharding: Scaling Hypergraph-Based Static Functions and Filters to Trillions of Keys ▼
We describe a simple and yet very scalable implementation of static functions (VFunc) and of static filters (VFilter) based on hypergraphs. We introduce the idea of ε-cost sharding, which allows us to build structures that can manage trillions of keys, at the same time increasing memory locality in hypergraph-based constructions. Contrarily to the commonly used HEM sharding method, ε-cost sharding does not require to store of additional information, and does not introduce dependencies in the computation chain; its only cost is that of few arithmetical instructions, and of a relative increase ε in space usage. We apply ε-cost sharding to the classical MWHC construction, but we obtain the best result by combining Dietzfelbinger and Walzer's fuse graphs for large shards with lazy Gaussian elimination for small shards. We obtain large structures with an overhead of 10.5% with respect to the information-theoretical lower bound and with a query time that is a few nanoseconds away from the query time of the non-sharded version, which is the fastest currently available within the same space bounds. Besides comparing our structures with a non-sharded version, we contrast its tradeoffs with bumped ribbon constructions, a space-saving alternative to hypergraph-based static functions and filters, which provide optimum space consumption but slow construction and query time (though construction can be parallelized very efficiently). We build offline a trillion-key filter using commodity hardware in just 60 ns/key.