Fast Computation of Reachability Labeling for Large Graphs

摘要: The need of processing graph reachability queries stems from many applications that manage complex data as graphs. include transportation network, Internet traffic analyzing, Web navigation, semantic web, chemical informatics and bio-informatics systems, computer vision. A query, one the primary tasks, is to find whether two given objects, u v, are related in any ways a large dataset. Formally, query about if v reachable directed which size. In this paper, we focus ourselves on building labeling for graph, order process efficiently. Such needs be minimized size efficiency answering queries, computed fast constructing such labeling. As labeling, 2-hop cover was proposed arbitrary graphs with theoretical bounds both construction cost resulting However, practice, reported, very high even super power machines. propose novel geometry-based algorithm computes high-quality fast. Our experimental results verify effectiveness our techniques over real synthetic datasets.