Book contents
- Frontmatter
- Dedication
- Contents
- Preface
- 1 Introduction
- 2 A Warm-up
- 3 Random Sampling
- 4 List Ranking
- 5 Sorting Atomic Items
- 6 Set Intersection
- 7 Sorting Strings
- 8 The Dictionary Problem
- 9 Searching Strings by Prefix
- 10 Searching Strings by Substring
- 11 Integer Coding
- 12 Statistical Coding
- 13 Dictionary-Based Compressors
- 14 Block-Sorting Compression
- 15 Compressed Data Structures
- 16 Conclusion
- Index
6 - Set Intersection
Published online by Cambridge University Press: 08 June 2023
- Frontmatter
- Dedication
- Contents
- Preface
- 1 Introduction
- 2 A Warm-up
- 3 Random Sampling
- 4 List Ranking
- 5 Sorting Atomic Items
- 6 Set Intersection
- 7 Sorting Strings
- 8 The Dictionary Problem
- 9 Searching Strings by Prefix
- 10 Searching Strings by Substring
- 11 Integer Coding
- 12 Statistical Coding
- 13 Dictionary-Based Compressors
- 14 Block-Sorting Compression
- 15 Compressed Data Structures
- 16 Conclusion
- Index
Summary
This chapter tackles the simple problem of intersecting two (sorted) lists of increasing integers, which constitutes the backbone of every query resolver in databases and (Web) search engines. In dealing with this problem, the chapter describes several approaches of increasing sophistication and elegance, which eventually turn out to be efficient/optimal in terms of time and I/O complexities. A final solution will deploy a proper compression of the input integers and a two-level scheme aimed at reducing the final space occupancy and working efficiently over hierarchical memories.
- Type
- Chapter
- Information
- Pearls of Algorithm Engineering , pp. 72 - 81Publisher: Cambridge University PressPrint publication year: 2023