Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro, “Adaptive Set Intersections, Unions, and Differences”, in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), San Francisco, California, January 9–11, 2000, pages 743–752.

Abstract:

Motivated by boolean queries in text database systems, we consider the problems of finding the intersection, union, or difference of a collection of sorted sets. While the worst-case complexity of these problems is straightforward, we consider a notion of complexity that depends on the particular instance. We develop the idea of a proof that a given set is indeed the correct answer. Proofs, and in particular shortest proofs, are characterized. We present adaptive algorithms that make no a priori assumptions about the problem instance, and show that their running times are within a constant factor of optimal with respect to a natural measure of the difficulty of an instance. In the process, we develop a framework for designing and evaluating adaptive algorithms in the comparison model.

Length:

The paper is 10 pages and the talk is 20 minutes.

Availability:

The paper is available in PostScript (222k) and gzipped PostScript (86k).

See information on file formats.

[Google Scholar search]

Related papers:

ALENEX2001 (Experiments on Adaptive Set Intersections for Text Retrieval Systems)