Adaptive set intersections

Simple item page
dc.contributor.authorDemaine, Erik, D.
dc.contributor.authorLopez-Ortiz, Alejandro
dc.contributor.authorMunro, J., l.
dc.date.accessioned2023-03-01T18:27:01Z
dc.date.available2023-03-01T18:27:01Z
dc.date.issued1998
dc.description.abstractWe introduce a new data structure, corresponding to a fully persistent SET ADT, motivated by the efficient evaluation of boolean queries in text retrieval systems. We then focus on a key operation required by the ADT, namely the problem of efficiently evaluating an intersection expression over a static collection of integer sets. We present an optimal nondeterministic algorithm for computing the shortest proof of nonintersection for disjoint sets in the comparison model. Then we propose an adaptive algorithm for computing such proofs in deterministic fashion. The number of comparisons performed by this algorithm falls within a small multiplicative factor of the theoretical best. This algorithm is generalized to compute the intersection of nondisjoint collections of sets with the same competitive factor.
dc.description.copyrightCopyright @ Erik D. Demaine, Alejandro Lopez-Ortiz, and J. lan Munro, 1998.
dc.identifier.urihttps://unbscholar.lib.unb.ca/handle/1882/14680
dc.rightshttp://purl.org/coar/access_right/c_abf2
dc.subject.disciplineComputer Science
dc.titleAdaptive set intersections
dc.typetechnical report

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
item.pdf
Size:
746.25 KB
Format:
Adobe Portable Document Format
Download

Collections

Research Reports