Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



Practical compressed string dictionaries
Indexado
WoS WOS:000367634200005
Scopus SCOPUS_ID:84944096663
DOI 10.1016/J.IS.2015.08.008
Año 2016
Tipo artículo de investigación

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



The need to store and query a set of strings - a string dictionary - arises in many kinds of applications. While classically these string dictionaries have accounted for a small share of the total space budget (e.g., in Natural Language Processing or when indexing text collections), recent applications in Web engines, Semantic Web (RDF) graphs, Bioinformatics, and many others handle very large string dictionaries, whose size is a significant fraction of the whole data. In these cases, string dictionary management is a scalability issue by itself. This paper focuses on the problem of managing large static string dictionaries in compressed main memory space. We revisit classical solutions for string dictionaries like hashing, tries, and front-coding, and improve them by using compression techniques. We also introduce some novel string dictionary representations built on top of recent advances in succinct data structures and full-text indexes. All these structures are empirically compared on a heterogeneous testbed formed by real-world string dictionaries. We show that the compressed representations may use as little as 5% of the original dictionary size, while supporting lookup operations within a few microseconds. These numbers outperform the state-of-the-art space/time tradeoffs in many cases. Furthermore, we enhance some representations to provide prefix- and substring-based searches, which also perform competitively. The results show that compressed string dictionaries are a useful building block for various data-intensive applications in different domains. (C) 2015 Elsevier Ltd. All rights reserved.

Revista



Revista ISSN
Information Systems 0306-4379

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Computer Science, Information Systems
Scopus
Information Systems
Software
Hardware And Architecture
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 MARTINEZ-PRIETO, MIGUEL ANGEL Hombre UNIV VALLADOLID - España
Universidad de Valladolid - España
2 Brisaboa, Nieves R. Mujer Univ A Coruna - España
Universidade da Coruña - España
3 Canovas Emhart, Rodrigo Hombre Univ Melbourne - Australia
University of Melbourne - Australia
4 CLAUDE-FAUST, FRANCISCO JOSE Hombre Universidad Diego Portales - Chile
5 NAVARRO-BADINO, GONZALO Hombre Universidad de Chile - Chile

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Origen de Citas Identificadas



Muestra la distribución de países cuyos autores citan a la publicación consultada.

Citas identificadas: Las citas provienen de documentos incluidos en la base de datos de DATACIENCIA

Citas Identificadas: 4.76 %
Citas No-identificadas: 95.24 %

Muestra la distribución de instituciones nacionales o extranjeras cuyos autores citan a la publicación consultada.

Citas identificadas: Las citas provienen de documentos incluidos en la base de datos de DATACIENCIA

Citas Identificadas: 4.76 %
Citas No-identificadas: 95.24 %

Financiamiento



Fuente
FONDECYT Iniciación
CONICYT, Chile
Spanish Ministry of Economy and Competitiveness
ICT COST Action KEYSTONE

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
Funded in part by Fondecyt Iniciacion 11130104.

Muestra la fuente de financiamiento declarada en la publicación.