Storing and Querying Evolving Graphs in NoSQL Storage Models
Alexandros Spitalas, Anastasios Gounaris, Andreas Kosmatopoulos, Kostas Tsichlas · 2025
Read Storing and Querying Evolving Graphs in NoSQL Storage Models by Alexandros Spitalas, Anastasios Gounaris, Andreas Kosmatopoulos, Kostas Tsichlas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-17438.txt.
Introduction
Alexandros Spitalas and co-authors store changing graphs in a NoSQL database in a 2025 paper. Evolving graphs track ties between entities over time. Keeping full history while answering heavy global queries is the hard part. The team build on MongoDB with a vertex-centric layout.
Their model leans on in-database query machinery to cut stored copies and client work. Both snapshot and interval views of history are supported. Tests use standard social network generator data, run on single machines and clusters. Global queries, usually the slowest, speed up markedly. Storage costs fall as well. The work gives graph historians a practical layout for time-aware analytics.
Catalog record
| CREATOR | Alexandros Spitalas, Anastasios Gounaris, Andreas Kosmatopoulos, Kostas Tsichlas |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-17438
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Storing and Querying Evolving Graphs in NoSQL Storage Models Alexandros Spitalas, Anastasios Gounaris, Andreas Kosmatopoulos, Kostas Tsichlas Abstract This paper investigates advanced storage models for evolving graphs, focusing on the efficient management of historical data and the optimization of global query performance. Evolving graphs, which represent dynamic relationships between entities over time, present unique challenges in preserving their complete history while supporting complex analytical queries. We first do a fast review of the current state of the art focusing mainly on distributed historical graph databases to provide the context of our proposals. We investigate the implementation of an enhanced vertex-centric storage model in MongoDB that prioritizes space efficiency by leveraging in-database query mechanisms to minimize redundant data and reduce storage costs. To ensure broad applicability, we employ datasets, some of which are generated with the LDBC SNB generator, appropriately post-processed to utilize both snapshot- and interval-based representations. Our experimental results both in centralized and distributed infrastructures, demonstrate significant improvements in query performance, particularly for resource-intensive global queries that traditionally suffer from inefficiencies in entity-centric frameworks. The proposed model achieves these gains by optimizing memory usage, reducing client involvement, and exploiting the computational capabilities of MongoDB. By addressing key bottlenecks in the storage and processing of evolving graphs, this study demonstrates a step toward a robust and scalable framework for managing dynamic graph data. This work contributes to the growing field of temporal graph analytics by enabling more efficient exploration of historical data and facilitating real-time insights into the evolution of complex networks. 1 Introduction Consider the challenge of tracking the spread of an infectious disease through global air travel. To understand how an outbreak evolved, we need to analyze how passengers moved between cities over time, identifying critical points where the disease was likely transmitted. A static representation of the flight network is insufficient, as routes change daily, restrictions alter travel patterns, and the contagion follows a dynamic trajectory. Efficiently storing and querying this evolving network is essential to reconstruct past transmission pathways, predict future outbreaks, and inform containment strategies. The ability to retrieve historical snapshots at any time granularity and analyze evolving connectivity patterns is crucial for timely decision-making, highlighting the need for scalable and optimized temporal graph storage solutions. The analysis of networks that evolve over time has gained increasing attention across multiple scientific disciplines, including sociology [ 13 ] , physics [ 56 ] , ecology [ 48 ] , computer science [ 43 ] , and engineering [ 54 ] . These networks - commonly referred to as dynamic, adaptive, time-varying, evolving, or temporal networks, depending partly on the scientific area under consideration - capture interactions between entities that change over time. While different fields emphasize distinct aspects of temporal graphs, a common challenge remains: representing and querying the historical evolution of such networks efficiently. Understanding how relationships form, persist, and dissolve is critical for applications ranging from social influence modeling to infrastructure resilience analysis. To provide a unified framework for studying these networks, the concept of Time-Varying Graphs (TVGs) [ 8 ] has been introduced, offering a formalism to express various temporal network models. This formalism represents entities as nodes and their relationships as edges, both of which can be annotated with attributes (such as name and weight). TVGs facilitate the application of time-aware algorithms, enabling tasks such as temporal shortest paths, influence spread analysis, and anomaly detection in dynamic systems. However, while substantial progress has been made in defining the theoretical foundations and computational techniques for temporal graphs, less attention has been given to the underlying storage models that support these operations. Without efficient storage solutions, retrieving historical snapshots, executing time-dependent queries, and scaling to large datasets remain computationally expensive and impractical. Indeed, many traditional database systems struggle to balance storage efficiency with query performance, especially for large-scale temporal graphs. This gap necessitates the development of storage models that can compactly represent historical data while enabling fast retrieval of both localized and global queries. To give an example, consider a graph corresponding to a social network that comprises millions of users (vertices) and the friendship relationships between them (edges). By examining the graph through two subsequent days, we witness a number of newly created, removed, and altered vertices or edges and a significant fraction of the graph that has remained the same across the two days. A system that aims to efficiently store all the snapshots of such a graph should employ techniques that mitigate the presence of unaltered data between different snapshots (i.e., take advantage of the commonalities between snapshots and refrain from storing duplicate data across snapshots). Moreover, the consideration of snapshots results in constraining the time granularity of the graph. Two consecutive snapshots could be defined over two consecutive years, months, days, hours, minutes, etc. This means that in general, snapshots are merely a view of the network at a particular time granularity and could change based on the user-defined query. However, in many systems, for performance reasons, the time granularity is predefined and cannot change since it requires the partial or total rebuilding of the system. In a nutshell, this paper has a three-fold contribution; 1) it reviews the current research on historical graph management systems, 2) it evaluates extensively a vertex-centric approach that leverages MongoDB, and 3) it identifies a lack of temporal graph generators and makes a first step toward this direction by creating historical graph datasets based on the LDBC SNB [ 3 ] . 1 1 1 This paper partially contains heavily updated material from previously published conference papers by the same authors [ 58 , 59 ] . In particular, apart from the new material explicitly stated in Sec. , all experiments have been re-conducted in different settings (local and cluster modes). The survey of existing storage techniques for temporal graphs, categorizes prior works based on their system architecture (distributed vs. non-distributed) focusing on distributed systems. In addition, it highlights trade-offs between different approaches and identifies key limitations in current solutions. We also explore a vertex-centric storage model that leverages MongoDB to enhance the efficiency of temporal graph storage and retrieval. Unlike traditional snapshot-based approaches, this model optimizes space utilization by structuring historical data in a vertex-centric manner, reducing redundancy while maintaining fast access to both local and global queries. We compare our results to a similar Cassandra-based implementation [ 31 ] . Overall, the MongoDB implementation can perform more complex in-database queries and decrease client involvement in query processing. Additionally, instead of getting the documents from the database in a single large batch, we explore the option to employ a foreach approach (when this is expected to be more efficient), and as a result, to further reduce client involvement and memory requirements. Finally, to validate our approach we use/generate historical graph datasets and conduct extensive experiments to explore the performance of different versions of our storage model in various settings. These settings include transactions or graph-scale operations, batch or streaming modes, and the use of snapshots or time intervals. Our evaluation measures query execution times, storage efficiency, and scalability, with a focus on complex global queries that are traditionally expensive in entity-centric systems. The results both in a centralized as well as in a