Range Non-Overlapping Indexing
524 views · Published 9 October 2007 · 32:43 · Indexed 20 September 2026
Channel: Google TechTalks · 2007 · Howto & Style
Google Tech Talks
July 31, 2007
ABSTRACT
We present a variation of the indexing problem involving constraints on the location of the pattern in the text. We call the variation \emph{range non-overlapping indexing} problem: given a text $T=t_{1}.. t_{n}$ over alphabet $\Sigma$, efficiently preprocess it such that future queries of the form ``given a pattern $P=p_{1}.. p_{m}$ over $\Sigma$ and two text locations $i \leq j$, find a sequence of locations where $P$ appears in $T$ between locations $i$ and $j$, such that the occurrences are \emph{non-overlapping} and their number is maximal''. This problem thus generalizes the \emph{string statistics problem}~\cite{AP96, BLOP02}, in which we only had...
More from this channel
-
34:17
Thinglink - A Free Product Code for Creative Work
-
44:29
Understanding Urban Environments Through the Use of...
-
46:04
Customizable Scalable Compute Intensive Stream Queries
-
51:26
All The Government's Information
-
41:35
Combining Discriminative Features to Infer Complex...
-
59:42
Dimensions of Reputation in Electronic Markets
-
46:50
Accessing Legacy Documents in the iPod Age
-
44:36
Trondheim Wireless Broadband Commons