Paper by Erik D. Demaine

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.

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.

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

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)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated January 22, 2017 by Erik Demaine.