Wenfei Fan
Chunming Hu
ABSTRACT
The incremental problem for a class Q of graph queries aims to compute, given a query Q in 'Q, graph G, output Q(G) and updates Δ G to G as input, changes Δ O to Q(G) such that Q(G ⊕ Δ G) = Q(G) ⊕ Δ O. It is called bounded if its cost can be expressed as a polynomial function in the sizes of Q, Δ G and Δ O. It is to reduce computations on possibly big G to small Δ G and Δ O. No matter how desirable, however, our first results are negative: for common graph queries such as graph traversal, connectivity, keyword search and pattern matching, their incremental problems are unbounded.
In light of the negative results, we propose two characterizations for the effectiveness of incremental computation: (a) localizable, if its cost is decided by small neighbors of nodes in Δ G instead of the entire G; and (b) bounded relative to a batch algorithm T, if the cost is determined by the sizes of Δ G and changes to the affected area that is necessarily checked by T. We show that the incremental computations above are either localizable or relatively bounded, by providing corresponding incremental algorithms. That is, we can either reduce the incremental computations on big graphs to small data, or incrementalize batch algorithms by minimizing unnecessary recomputation. Using real-life graphs, we experimentally verify the effectiveness of our algorithms.
- DBpedia.sl http://wiki.dbpedia.org/Downloads2014.Google Scholar
- Full version.sl http://homepages.inf.ed.ac.uk/s1368930/inc-full.pdf.Google Scholar
- SNAP.sl http://snap.stanford.edu/data/index.html.Google Scholar
- S. Abiteboul, J. McHugh, M. Rys, V. Vassalos, and J. L. Wiener. Incremental maintenance for materialized views over semistructured data. In VLDB, 1998. Google ScholarDigital Library
- U. A. Acar. Self-Adjusting Computation. PhD thesis, Carnegie Mellon University, 2005. Google ScholarDigital Library
- U. A. Acar, G. E. Blelloch, and R. Harper. Adaptive functional programming. In POPL, 2002. Google ScholarDigital Library
- V. M. Antimirov. Partial derivatives of regular expressions and finite automaton constructions. TCS, 155(2), 1996. Google ScholarDigital Library
- G. Bhalotia, A. Hulgeri, C. Nakhe, S. Chakrabarti, and S. Sudarshan. Keyword searching and browsing in databases using BANKS. In ICDE, 2002. Google ScholarDigital Library
- P. Bhatotia, A. Wieder, R. Rodrigues, U. A. Acar, and R. Pasquin. Incoop: MapReduce for incremental computations. In SOCC, 2011. Google ScholarDigital Library
- P. K. Bhatotia. Incremental Parallel and Distributed Systems. PhD thesis, Saarland University, 2015.Google Scholar
- A. Bonifati, M. H. Goodfellow, I. Manolescu, and D. Sileo. Algebraic incremental maintenance of XML views. TODS, 38(3):14, 2013. Google ScholarDigital Library
- R. Bramandia, B. Choi, and W. K. Ng. On incremental maintenance of 2-hop labeling of graphs. In WWW, 2008. Google ScholarDigital Library
- P. Burkhardt and C. Waring. An NSA big graph experiment. Technical Report NSA-RD-2013-056002v1, U.S. National Security Agency, 2013.Google Scholar
- L. S. Colby, T. Griffin, L. Libkin, I. S. Mumick, and H. Trickey. Algorithms for deferred view maintenance. In SIGMOD, 1996. Google ScholarDigital Library
- L. P. Cordella, P. Foggia, C. Sansone, and M. Vento. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell., 26(10):1367--1372, 2004. Google ScholarDigital Library
- C. Demetrescu, D. Eppstein, Z. Galil, and G. F. Italiano. Dynamic graph algorithms. In Algorithms and theory of computation handbook. Chapman & Hall/CRC, 2010. Google ScholarDigital Library
- W. Fan, X. Wang, and Y. Wu. Incremental graph pattern matching. TODS, 38(3), 2013. Google ScholarDigital Library
- W. Fan, X. Wang, and Y. Wu. Distributed graph simulation: Impossibility and possibility. PVLDB, 7(12), 2014. Google ScholarDigital Library
- W. Fan, X. Wang, and Y. Wu. Querying big graphs within bounded resources. In SIGMOD, 2014. Google ScholarDigital Library
- W. Fan, Y. Wu, and J. Xu. Functional dependencies for graphs. In SIGMOD, 2016. Google ScholarDigital Library
- W. Fan, J. Xu, Y. Wu, W. Yu, J. Jiang, Z. Zheng, B. Zhang, Y. Cao, and C. Tian. Parallelizing sequential graph computations. In SIGMOD, 2017. Google ScholarDigital Library
- M. A. Gallego, J. D. Fernández, M. A. Martínez-Prieto, and P. de la Fuente. An empirical study of real-world SPARQL queries. In USEWOD workshop, 2011.Google Scholar
- I. Grujic, S. Bogdanovic-Dinic, and L. Stoimenov. Collecting and analyzing data from e-government facebook pages. In ICT Innovations, 2014.Google Scholar
- A. Gupta, H. V. Jagadish, and I. S. Mumick. Data integration using self-maintainable views. In EDBT, 1996. Google ScholarDigital Library
- A. Gupta, I. S. Mumick, and V. S. Subrahmanian. Maintaining views incrementally. In SIGMOD, 1993. Google ScholarDigital Library
- B. Haeupler, T. Kavitha, R. Mathew, S. Sen, and R. E. Tarjan. Incremental cycle detection, topological ordering, and strong component maintenance. ACM Trans. Algorithms, 8(1):3, 2012. Google ScholarDigital Library
- H. He, H. Wang, J. Yang, and P. S. Yu. Blinks: ranked keyword searches on graphs. In SIGMOD, 2007. Google ScholarDigital Library
- M. R. Henzinger and V. King. Maintaining minimum spanning trees in dynamic graphs. In ICALP, 1997. Google ScholarDigital Library
- J. Hromkovic, S. Seibert, and T. Wilke. Translating regular expressions into small ε-free nondeterministic finite automata. J. Comput. Syst. Sci., 62(4):565--588, 2001. Google ScholarDigital Library
- V. Kacholia, S. Pandit, S. Chakrabarti, S. Sudarshan, R. Desai, and H. Karambelkar. Bidirectional expansion for keyword search on graph databases. In VLDB, 2005. Google ScholarDigital Library
- H. A. Kuno and E. A. Rundensteiner. Incremental maintenance of materialized object-oriented views in multiview: Strategies and performance evaluation. TKDE, 10(5):768--792, 1998. Google ScholarDigital Library
- J. Lacki. Improved deterministic algorithms for decremental reachability and strongly connected components. ACM Trans. Algorithms, 9(3):27, 2013. Google ScholarDigital Library
- A. O. Mendelzon and P. T. Wood. Finding regular simple paths in graph databases. SICOMP, 24(6), 1995. Google ScholarDigital Library
- A. Ntoulas, J. Cho, and C. Olston. What's new on the Web? The evolution of the Web from a search engine perspective. In WWW, 2004. Google ScholarDigital Library
- C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.Google Scholar
- W. Pugh and T. Teitelbaum. Incremental computation via function caching. In POPL, 1989. Google ScholarDigital Library
- L. Qin, J. X. Yu, L. Chang, H. Cheng, C. Zhang, and X. Lin. Scalable big graph processing in mapreduce. In SIGMOD, 2014. Google ScholarDigital Library
- G. Ramalingam and T. Reps. On the computational complexity of dynamic graph problems. TCS, 158(1--2), 1996. Google ScholarDigital Library
- G. Ramalingam and T. W. Reps. An incremental algorithm for a generalization of the shortest-path problem. J. Algorithms, 21(2):267--305, 1996. Google ScholarDigital Library
- L. Roditty and U. Zwick. A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In STOC, 2004. Google ScholarDigital Library
- D. Saha. An incremental bisimulation algorithm. In FSTTCS, 2007. Google ScholarDigital Library
- A. Stotz, R. Nagi, and M. Sudit. Incremental graph matching for situation awareness. FUSION, 2009.Google Scholar
- R. Tarjan. Depth-first search and linear graph algorithms. SICOMP, 1(2):146--160, 1972.Google ScholarDigital Library
- T. Teitelbaum and T. W. Reps. The cornell program synthesizer: A syntax-directed programming environment. Commun. ACM, 24(9):563--573, 1981. Google ScholarDigital Library
- J. X. Yu, L. Qin, and L. Chang. Keyword search in relational databases: A survey. IEEE Data Eng. Bull., 33(1), 2010.Google ScholarDigital Library
- Y. Zhuge and H. Garcia-Molina. Graph structured views and their incremental maintenance. In ICDE, 1998. Google ScholarDigital Library
Index Terms
- Incremental Graph Computations: Doable and Undoable
Recommendations
Incremental Graph Computations: Doable and Undoable
The incremental problem for a class \( {\mathcal {Q}} \) of graph queries aims to compute, given a query \( Q \in {\mathcal {Q}} \) , graph G, answers Q(G) to Q in G and updates ΔG to G as input, changes ΔO to output Q(G) such that Q(G⊕ΔG) = Q(G)⊕ΔO. ...
Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs
SIGMOD '16: Proceedings of the 2016 International Conference on Management of DataA variety of applications spanning various domains, e.g., social networks, transportation, and bioinformatics, have graphs as first-class citizens. These applications share a vital operation, namely, finding the shortest path between two nodes. In many ...
An effective framework for asynchronous incremental graph processing
Although many graph processing systems have been proposed, graphs in the real-world are often dynamic. It is important to keep the results of graph computation up-to-date. Incremental computation is demonstrated to be an efficient solution to update ...
Comments