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.

BibTeX

@InProceedings{SODA2000,
  AUTHOR        = {Erik D. Demaine and Alejandro L\'opez-Ortiz and
                   J. Ian Munro},
  TITLE         = {Adaptive Set Intersections, Unions, and Differences},
  BOOKTITLE     = {Proceedings of the 11th Annual ACM-SIAM Symposium on
                   Discrete Algorithms (SODA 2000)},
  BOOKURL       = {http://www.siam.org/meetings/da00/},
  ADDRESS       = {San Francisco, California},
  MONTH         = {January 9--11},
  YEAR          = 2000,
  PAGES         = {743--752},

  LENGTH        = {10 pages; 20 minutes},
  PAPERS        = {ALENEX2001},
  dblp          = {https://dblp.org/rec/conf/soda/DemaineLM00},
}

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)