D. Belazzougui

activity

20112013

most citedRandom input helps searching predecessors

4 citations · 8 across the 4 of their papers we have counts for

collaborators

4 papers

cs.DS2013

Various improvements to text fingerprinting

Djamal Belazzougui, Roman Kolpakov, Mathieu Raffinot

Let s = s_1 .. s_n be a text (or sequence) on a finite alphabet Σof size σ. A fingerprint in s is the set of distinct characters appearing in one of its substrings. The problem con…

cs.DS2013

Single and multiple consecutive permutation motif search

Djamal Belazzougui, Adeline Pierrot, Mathieu Raffinot +1

Let $t$ be a permutation (that shall play the role of the {\em text}) on $[n]$ and a pattern $p$ be a sequence of $m$ distinct integer(s) of $[n]$ , $m \leq n$ . The pattern $p$ occur…

cs.DS2012★ 4 cited

Predecessor search with distance-sensitive query time

Djamal Belazzougui, Paolo Boldi, Sebastiano Vigna

A predecessor (successor) search finds the largest element $x^{-}$ smaller than the input string $x$ (the smallest element $x^{+}$ larger than or equal to $x$ , respectively) out of a g…

cs.DS2011★ 4 cited

Random input helps searching predecessors

D. Belazzougui, A. C. Kaporis, P. G. Spirakis

We solve the dynamic Predecessor Problem with high probability (whp) in constant time, using only $n^{1 + δ}$ bits of memory, for any constant $δ > 0$ . The input keys are random wrt a…