Optimality of Randomized Algorithms for the Intersection Problem

摘要

The "intersection of sorted arrays" problem has applications in indexed search engines such as Google. Previous works propose and compare deterministic algorithms for this problem, and offer lower bounds on the randomized complexity in different models (cost model, alternation model). We refine the alternation model into the redundancy model to prove that randomized algorithms perform better than deterministic ones on the intersection problem. We present a randomized and simplified version of a previous algorithm, optimal in this model.