**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)

See also other papers by Erik Demaine.

Last updated October 19, 2020 by Erik Demaine.