Скачать или смотреть "Better bitmap performance with Roaring bitmaps" Session Recording

This video is the session recording where we discussed the research paper "Better bitmap performance with Roaring bitmaps".

🚨 Session Recording's Timestamps 🕰️ are at the bottom of this description box.

Roaring bitmaps are a clever data structure that efficiently stores and processes sets of integers using a hybrid approach combining different compression techniques.

At its core, Roaring partitions 32-bit integers into chunks based on their most significant 16 bits, then uses different storage strategies depending on the density of each chunk. For sparse chunks containing up to 4,096 values, Roaring uses sorted arrays of 16-bit integers, while for denser chunks, it employs 65,536-bit bitmaps.
This two-level indexing approach, combined with careful optimization of low-level operations like unions and intersections, allows Roaring to achieve excellent compression ratios and breakneck processing speeds. It often performs several times faster than traditional compressed bitmap formats like WAH and Concise while using significantly less memory.

The elegant balance between compression and speed has made Roaring bitmaps a popular choice in major database systems like Apache Spark and Apache Lucene, where they're used to accelerate operations on large sets of integers like document IDs or row numbers.

Session Recording's Timestamps 🕰️:
00:00 Reading group session's introduction
1:06 Session Start
1:52 Discussing the basic concepts
7:17 Why are Bitmaps good?
8:36 Summary of discussion till now
9:00 Discussing the Motivation for Roaring Bitmaps
11:14 Roaring Bitmaps' Internals
11:40 Answering a question about Bitmaps
13:45 Roaring Bitmaps' Internals (Continued)
14:14 Correcting a mistake in the Whiteboard
14:23 Roaring Bitmaps' Internals (Continued)
16:03 What are Containers?
19:20 Answering a Question
21:42 Discussing the Design of Containers
24:34 How to convert between Array containers and Bitmap containers
33:35 Summarising the Discussion on Containers
34:38 What operations can you do with Roaring Bitmaps?
36:45 How to perform the Union of Roaring Bitmaps?
43:21 Answering a Question
46:11 How to perform the Intersection of Roaring Bitmaps?
55:54 Summary of discussion till now
57:07 Discussing the Performance of Roaring Bitmaps
1:02:03 Answering a Question
1:04:32 Answering more Questions
1:15:40 Essential points about Asymptotic Complexity
1:18:22 Presenting my Rust implementation of Roaring Bitmaps 🦀
1:23:27 Closing Discussions
1:28:14 My Session's Alarm went off... 🙂
1:28:15 Reading group session's feedback

#roaring #bitmaps #roaringbitmaps #distributedsystems #researchpaper #readinggroup #dsa #performance #memory