.png){kind=icon}
.png){kind=icon}
Return
Data structures for temporal graphs based on compact sequence representations
.png){kind=icon}
PRE
AI
DOI：10.1016/j.is.2015.02.002.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Temporal graphs represent vertices and binary relations that change along time. In this paper, a temporal graph is conceptualized as the sequences of changes on its edges during its lifetime, also known as temporal adjacency logs. The paper explores the use of compression techniques, and compact and self-indexed data structures, to represent large temporal graphs. More specifically, we present four strategies to represent temporal graphs. The first two strategies, Time-interval Log per Edge (EdgeLog) and the Adjacency Log of Events (EveLog), use compression techniques over the inverted indexes that represent the adjacency logs. Then, we introduce two new strategies to represent temporal graphs using compact and self-indexed data structures. Compact Adjacency Sequence (CAS) represents changes on adjacent vertices as a sequence stored in a Wavelet Tree, and the Compact Events ordered by Time (CET) represents the edges that change in each time instant using Interleaved Wavelet Tree, a new compact and self-indexed data structure specifically designed in this work that is able to represent a sequence of multidimensional symbols (that is, tuples of symbols encoded together). We experimentally evaluate the four strategies and compare them with previous alternatives in the state-of-the-art showing that the four alternatives can represent large temporal graphs making efficient use of space, while keeping good time performance for a wide range of useful queries. We conclude that the use of compression techniques or the use of compact and self-indexed data structures open the possibility for the design of interesting representations of temporal graphs that fit the heeds of different application domains. (C) 2015 Elsevier Ltd. All rights reserved.
Keywords:
Temporal graphs
Compact data structures
Wavelet tree
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.9
Papers:
2.8K
Citations:
1.8K