Space-efficient substring occurrence estimation (Contributo in atti di convegno)

Type
Label
  • Space-efficient substring occurrence estimation (Contributo in atti di convegno) (literal)
Anno
  • 2011-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1145/1989284.1989300 (literal)
Alternative label
  • Orlandi, Alessio ; Venturini, Rossano (2011)
    Space-efficient substring occurrence estimation
    in 30th symposium on Principles of Database Systems of Data, PODS 2011, Athens, Greece, 12-16 June 2011
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Orlandi, Alessio ; Venturini, Rossano (literal)
Pagina inizio
  • 95 (literal)
Pagina fine
  • 106 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#altreInformazioni
  • ID_PUMA: cnr.isti/cnr.isti/2011-A2-018. - ID Modulo Commessa 2103 - ICT.P09.006.001 - 074 - Tecnologie avanzate, Sistemi e Servizi per Grid. - Area di valutazione 01 - Scienze matematiche e informatiche (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#url
  • http://portal.acm.org/citation.cfm?id=1989300&CFID=29642294&CFTOKEN=82582261 (literal)
Note
  • Scopu (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Dipartimento di Informatica, Università di Pisa ; CNR-ISTI, Pisa (literal)
Titolo
  • Space-efficient substring occurrence estimation (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#isbn
  • 978-1-4503-0660-7 (literal)
Abstract
  • We study the problem of estimating the number of occurrences of substrings in textual data: A text T on some alphabet Sigma of size sigma is preprocessed and an index I is built. The index is used in lieu of the text to answer queries of the form CountH(P), returning an approximated number of the occurrences of an arbitrary pattern P as a substring of T. The problem has its main application in selectivity estimation related to the LIKE predicate in textual databases. Our focus is on obtaining an algorithmic solution with guaranteed error rates and small footprint. To achieve that, we first enrich previous work in the area of compressed text-indexing providing an optimal data structure that requires (|T|log sigma/l) bits where l e 1 is the additive error on any answer. We also approach the issue of guaranteeing exact answers for sufficiently frequent patterns, providing a data structure whose size scales with the amount of such patterns. Our theoretical findings are sustained by experiments showing the practical impact of our data structures. (literal)
Editore
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Editore di
Insieme di parole chiave di
data.CNR.it