192 citations · 726 across the 22 of their papers we have counts for
22 papers
Integer Division by Constants: Optimal Bounds
Daniel Lemire, Colin Bartlett, Owen Kaser
The integer division of a numerator n by a divisor d gives a quotient q and a remainder r. Optimizing compilers accelerate software by replacing the division of n by d with the div…
Faster Remainder by Direct Computation: Applications to Compilers and Software Libraries
Daniel Lemire, Owen Kaser, Nathan Kurz
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…
Roaring Bitmaps: Implementation of an Optimized Software Library
Daniel Lemire, Owen Kaser, Nathan Kurz +4
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, differenc…
Consistently faster and smaller compressed bitmaps with Roaring
Daniel Lemire, Gregory Ssi-Yan-Kai, Owen Kaser
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)…
Faster 64-bit universal hashing using carry-less multiplications
Daniel Lemire, Owen Kaser
Intel and AMD support the Carry-less Multiplication (CLMUL) instruction set in their x64 processors. We use CLMUL to implement an almost universal 64-bit hash family (CLHASH). We c…
Better bitmap performance with Roaring bitmaps
Samy Chambi, Daniel Lemire, Owen Kaser +1
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,…