Optimally selecting the top k values from X+Y with layer-ordered heaps

2020/01/30 by Oliver Serang, Serang, Oliver
Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.2001.11607

openalex publication_date 2020/01/30 · arxiv created 2020/10/05 · arxiv updated 2020/10/07 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28

Abstract

Selection and sorting the Cartesian sum, X+Y, are classic and important problems. Here, a new algorithm is presented, which generates the top k values of the form X_i+Y_j. The algorithm relies only on median-of-medians and is simple to implement. Furthermore, it uses data structures contiguous in memory, and is fast in practice. The presented algorithm is demonstrated to be theoretically optimal.

Related

• Selection on X₁ + X₁ + ⋯ X_m via Cartesian product tree
• Selection on X₁+X₂+⋯ + X_m with layer-ordered heaps
• Optimal construction of a layer-ordered heap
• Selection from heaps, row-sorted matrices and X+Y using soft heaps
• Median of heaps: linear-time selection by recursively constructing binary heaps