Using Compressed Suffix-Arrays for a compact representation of temporal-graphs
| Autor: | Antonio Fariña, Diego Caro, Nieves R. Brisaboa, M. Andrea Rodríguez |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
Compressed suffix array Structure (mathematical logic) Information Systems and Management Computer science Search engine indexing 02 engineering and technology Data structure Graph Computer Science Applications Theoretical Computer Science Artificial Intelligence Control and Systems Engineering 020204 information systems Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) 020201 artificial intelligence & image processing Enhanced Data Rates for GSM Evolution Suffix Representation (mathematics) Algorithm Software |
| Zdroj: | Information Sciences |
| ISSN: | 0020-0255 |
| DOI: | 10.1016/j.ins.2018.07.023 |
| Popis: | Temporal graphs represent binary relationships that change along time. They can model the dynamism of, for example, social and communication networks. Temporal graphs are defined as sets of contacts that are edges tagged with the temporal intervals when they are active. This work explores the use of the Compressed Suffix Array (CSA), a well-known compact and self-indexed data structure in the area of text indexing, to represent large temporal graphs. The new structure, called Temporal Graph CSA (TGCSA), is experimentally compared with the most competitive compact data structures in the state-of-the-art, namely, EDGELOG and CET. The experimental results show that TGCSA obtains a good space-time trade-off. It uses a reasonable space and is efficient for solving complex temporal queries. Furthermore, TGCSA has wider expressive capabilities than EDGELOG and CET, because it is able to represent temporal graphs where contacts on an edge can temporally overlap. 41 pages, Information Sciences |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect