Computer Science – Data Structures and Algorithms
Scientific paper
2007-10-08
Computer Science
Data Structures and Algorithms
24 pages, 4 figures. A preliminary (now outdated) version was presented at SPIRE 2006
Scientific paper
Minimal-interval semantics associates with each query over a document a set of intervals, called witnesses, that are incomparable with respect to inclusion (i.e., they form an antichain): witnesses define the minimal regions of the document satisfying the query. Minimal-interval semantics makes it easy to define and compute several sophisticated proximity operators, provides snippets for user presentation, and can be used to rank documents. In this paper we provide algorithms for computing conjunction and disjunction that are linear in the number of intervals and logarithmic in the number of operands; for additional operators, such as ordered conjunction and Brouwerian difference, we provide linear algorithms. In all cases, space is linear in the number of operands. More importantly, we define a formal notion of optimal laziness, and either prove it, or prove its impossibility, for each algorithm. Optimal laziness implies that the algorithms do not assume random access to the input intervals, and read as little input as possible to produce a certain output. We cast our results in the general framework of antichain completions of interval orders, making our algorithms directly applicable to other domains.
Boldi Paolo
Vigna Sebastiano
No associations
LandOfFree
Efficient Optimally Lazy Algorithms for Minimal-Interval Semantics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient Optimally Lazy Algorithms for Minimal-Interval Semantics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Optimally Lazy Algorithms for Minimal-Interval Semantics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-544297