Random input helps searching predecessors

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

We solve the dynamic Predecessor Problem with high probability (whp) in constant time, using only $n^{1+\delta}$ bits of memory, for any constant $\delta > 0$. The input keys are random wrt a wider class of the well studied and practically important

Externí odkaz: http://arxiv.org/abs/1104.4353

Indexing and Querying Character Sets in One- and Two-Dimensional Words.

Autor: Belazzougui, D.¹ Djamal.Belazzougui@cs.helsinki.fi, Kolpakov, R.² foroman@mail.ru, Raffinot, M.³ raffinot@liafa.univ-paris-diderot.fr

Publikováno v: Journal of Mathematical Sciences. Aug2018, Vol. 233 Issue 1, p1-9. 9p.

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Compressed static functions with applications

Autor: Belazzougui D., Venturini R.

Publikováno v: 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 229–240, New orleans, Louisiana, USA, 5 gennaio 2013
info:cnr-pdr/source/autori:Belazzougui D.; Venturini R./congresso_nome:24th Annual ACM-SIAM Symposium on Discrete Algorithms/congresso_luogo:New orleans, Louisiana, USA/congresso_data:5 gennaio 2013/anno:2013/pagina_da:229/pagina_a:240/intervallo_pagine:229–240

Given a set of integer keys from a bounded universe along with associated data, the dictionary problem asks to answer two queries: membership and retrieval. Membership has to tell whether a given element is in the dictionary or not; Retrieval has to

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::9939ac5dc8ed6b38c37e66e856423ee4
https://openportal.isti.cnr.it/doc?id=people______::9939ac5dc8ed6b38c37e66e856423ee4

Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses

Autor: Belazzougui, D., PAOLO BOLDI, Pagh, R., Vigna, S.

Publikováno v: Scopus-Elsevier

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b160066b041339bf1dd94e1cdb9392e6
https://doi.org/10.1137/1.9781611973068.86