Using Compressed Suffix-Arrays for a Compact Representation of Temporal-Graphs

Simple item page
dc.contributor.authorBrisaboa, Nieves R.
dc.contributor.authorCaro, Diego
dc.contributor.authorFariña, Antonio
dc.contributor.authorRodríguez, M. Andrea
dc.date.accessioned2019-07-11T23:27:02Z
dc.date.available2019-07-11T23:27:02Z
dc.date.issued2018
dc.description.abstractTemporal 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.
dc.format.extent24 p.
dc.identifier.citationData Structures and Algorithms (cs.DS) Information Sciences, Volume 465, October 2018, Pages 459-483
dc.identifier.urihttp://hdl.handle.net/11447/2527
dc.identifier.urihttp://dx.doi.org/10.1016/j.ins.2018.07.023
dc.language.isoen
dc.subjectTemporal graphs
dc.subjectCompressed Suffix Array
dc.subjectSelf-index
dc.titleUsing Compressed Suffix-Arrays for a Compact Representation of Temporal-Graphs
dc.typeArticle

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Using Compressed Suffix-Arrays for a compact representation of temporal-graphs.pdf
Size:
682.16 KB
Format:
Adobe Portable Document Format
Description:
Texto completo
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Artículos Ingeniería

Implementado por OpenGeek Services