adaptive algorithm for computing the intersection of k sorted sets...model with an encoding of the shortest proof of the answer...performs better for “burstier” inputs than a worst-case optimal method...explores how algorithm behaves under actual data

intersection of large ordered sets is a common problem in the context of the evaluation of boolean queries to a search engine. In this paper we engineer a better algorithm for this task, which improves over those proposed by Demaine, Munro and López-Orti