ACM Transactions on Database Systems · 2011 · 73 citations · 20 references
ComputingComputer ScienceAlgorithmsData StructuresDatabasesGraph AlgorithmsGraph AnalyticsGraph LabelingGraph TheoryQuery ProcessingCompressionGraph IndexingGraph QueryingIncremental Index UpdateLabelingLabelsQuery AnsweringReachability
Reachability query is one of the fundamental queries in graph database. The main idea behind answering reachability queries is to assign vertices with certain labels such that the reachability between any two vertices can be determined by the labeling information. Though several approaches have been proposed for building these reachability labels, it remains open issues on how to handle increasingly large number of vertices in real-world graphs, and how to find the best tradeoff among the labeling size, the query answering time, and the construction time. In this article, we introduce a novel graph structure, referred to as path-tree , to help labeling very large graphs. The path-tree cover is a spanning subgraph of G in a tree shape. We show path-tree can be generalized to chain-tree which theoretically can has smaller labeling cost. On top of path-tree and chain-tree index, we also introduce a new compression scheme which groups vertices with similar labels together to further reduce the labeling size. In addition, we also propose an efficient incremental update algorithm for dynamic index maintenance. Finally, we demonstrate both analytically and empirically the effectiveness and efficiency of our new approaches.
20
Adhi Harmoko S, M.Komp, Joseph Marie Jacquard et al. · 2005 · 18.4K citations
A Decomposition Theorem for Partially Ordered Sets
R. P. Dilworth · Annals of Mathematics · 1950 · 987 citations
Reachability and Distance Queries via 2-Hop Labels
Edith Cohen, Eran Halperin, Haim Kaplan et al. · SIAM Journal on Computing · 2003 · 508 citations