Grammar compressed sequences with rank/select support

Simple item page
UDC.coleccionInvestigaciónes_ES
UDC.departamentoCiencias da Computación e Tecnoloxías da Informaciónes_ES
UDC.grupoInvLaboratorio de Bases de Datos (LBD)es_ES
UDC.journalTitleJournal of Discrete Algorithmses_ES
dc.contributor.authorOrdóñez, Alberto
dc.contributor.authorNavarro, Gonzalo
dc.contributor.authorBrisaboa, Nieves R.
dc.date.accessioned2017-02-27T17:16:43Z
dc.date.embargoEndDate2018-10-14es_ES
dc.date.embargoLift2018-10-14
dc.date.issued2016-10-14
dc.descriptionAn early partial version of this paper appeared in Proc. SPIRE 2014: G. Navarro, A. Ordóñez Grammar compressed sequences with rank/select support, Proc. 21st International Symposium on String Processing and Information Retrieval, LNCS, SPIRE, vol. 8799 (2014), pp. 31–44es_ES
dc.descriptionThe final publication is available at Springer via http://dx.doi.org/10.1016/j.jda.2016.10.001es_ES
dc.description.abstract[Abstract] Sequence representations supporting not only direct access to their symbols, but also rank/select operations, are a fundamental building block in many compressed data structures. Several recent applications need to represent highly repetitive sequences, and classical statistical compression proves ineffective. We introduce, instead, grammar-based representations for repetitive sequences, which use up to 6% of the space needed by statistically compressed representations, and support direct access and rank/select operations within tens of microseconds. We demonstrate the impact of our structures in text indexing applications.es_ES
dc.description.sponsorshipChile. Fondo Nacional de Desarrollo Científico y Tecnológico; 140796es_ES
dc.description.sponsorshipMinisterio de Economía, Industria y Competitividad; 00645663/ITC-20133062es_ES
dc.description.sponsorshipMinisterio de Economía, Industria y Competitividad; TIN2009-14560-C03-02es_ES
dc.description.sponsorshipMinisterio de Economía, Industria y Competitividad; TIN2010-21246-C02-01es_ES
dc.description.sponsorshipMinisterio de Economía, Industria y Competitividad; TIN2013-46238-C4-3-Res_ES
dc.description.sponsorshipMinisterio de Economía, Industria y Competitividad; TIN2013-47090-C3-3-Pes_ES
dc.description.sponsorshipMinisterio de Economía, Industria y Competitividad; AP2010-6038es_ES
dc.description.sponsorshipXunta de Galicia; GRC2013/053es_ES
dc.identifier.citationAlberto Ordóñez, Gonzalo Navarro, Nieves R. Brisaboa, Grammar compressed sequences with rank/select support, Journal of Discrete Algorithms, Available online 14 October 2016, ISSN 1570-8667, http://dx.doi.org/10.1016/j.jda.2016.10.001.es_ES
dc.identifier.doi10.1016/j.jda.2016.10.001
dc.identifier.issn1570-8667
dc.identifier.issn1570-8675
dc.identifier.urihttp://hdl.handle.net/2183/18191
dc.language.isoenges_ES
dc.publisherElsevier BVes_ES
dc.relation.projectIDinfo:eu-repo/grantAgreement/EC/H2020/690941
dc.relation.urihttp://www.sciencedirect.com/science/article/pii/S157086671630034X?np=y&npKey=3f1c328b4e3e50d868dc16ee1923ba301c2a53b77745f7b638604b7fcfef3c9ees_ES
dc.rightsAtribución-NoComercial-SinDerivadas 3.0 Españaes_ES
dc.rights.accessRightsopen accesses_ES
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/es/*
dc.subjectGrammar compressiones_ES
dc.subjectRepetitive sequenceses_ES
dc.subjectText indexinges_ES
dc.titleGrammar compressed sequences with rank/select supportes_ES
dc.typejournal articlees_ES
dspace.entity.typePublication
relation.isAuthorOfPublication42f2c226-9868-4516-8efd-2cd3c6692034
relation.isAuthorOfPublication.latestForDiscovery42f2c226-9868-4516-8efd-2cd3c6692034

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
2016_Grammar_compressed_sequences_with_rankselect_support.pdf
Size:
2.45 MB
Format:
Adobe Portable Document Format
Description:
Download

Collections

Investigación (FIC)