What is it about?
Graph is a data structure composed of vertices and edges. Graphs, especially evolving graphs, are widely used in many real world scenarios. For example, in a social network, one can view each person as a vertex and each relationship between two people as an edge. And the graph evolves when a person/relationship is added/deleted. Path queries are one of the most useful queries on a graph. In this paper, we focus on pairwise path queries. That is, given two vertices of the graph, we want to find a path between them that satisfies specific property, such as the path with the minimum steps. We discuss a wide range of different queries and propose an unified algorithm that can answer them efficiently.
Featured Image
Photo by Kier in Sight on Unsplash
Why is it important?
The lower bound based algorithm porposed by this paper is novel. The experiments show that our method is several orders of magnitude faster than existing solutions.
Read the Original
This page is a summary of: Achieving Sub-second Pairwise Query over Evolving Graphs, January 2023, ACM (Association for Computing Machinery),
DOI: 10.1145/3575693.3576173.
You can read the full text:
Contributors
The following have contributed to this page
