Reachability Preserving Compression for Dynamic Graph Abstract   Reachability preserving compression generates small graphs that preserve the information only relevant to reachability queries, and the compressed graph can answer any reachability query without decompression. Existing reachability preserving compression algorithms either require a long compression time or include redundant data in the compressed graph. In this paper, we propose a novel edge sorting alogrithm for fast, nonredudant reachability preserving compression. On the other hand, we found that the current incremental reachability compression algorithms for dynamic graphs may return incorrect results in some cases. Therefore, we propose two novel incremental reachability compression algorithms. An algorithm called incremental reachability preserving compression with optimum compression ratio, which generates an update compressed graph that is exactly the same as the graph computed by recompression. The other algorithm called fast incremental reachability preserving compression, which can update the compressed graph in a short time. Extensive experiments on real datasets show the efficiency and the effectiveness of our methods.

Novel Efficient Coding Scheme for DataRate Limited JourneyAware GraphData Transmission How to efficiently transmit graphdata to mobile devices is quite appealing nowadays, especially for autonomous vehicles and positioning systems. When a mobile receiver is set out for a journey, the objective is often to reconstruct topologicallycomplete subgraphs according to the arrival data in real time. Hence, we dedicate a novel coding scheme to segmenting and arranging the data efficiently from a huge meshgrid graph. When the datarate is restricted, through our proposed partitioning and scheduling schemes, mobile receivers can greatly relax the requirement for the number of transmission times to reconstruct topologicallycomplete subgraphs. To evaluate our proposed techniques, we derive the expected number of transmission times required to reconstruct a subgraph theoretically. Moreover, we define the khop completeness to measure the probability of reconstructing a topologicallycomplete subgraph by any scheme. Our proposed new method greatly outperforms the conventional scheme theoretically and by simulation. Our proposed method can enable the future journeyaware dynamic mapping system on vehicles without any need of prestored huge map database.