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
Last updated November 1, 2014 by