Asynchronous Distributed Incremental Computation on Evolving Graphs

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9852
• 期：1
• 页码：722-738
• 全文大小：462 KB
• 参考文献：1.Bahmani, B., Chowdhury, A., Goel, A.: Fast incremental and personalized pagerank. Proc. VLDB Endow. 4(3), 173–184 (2010)CrossRef
  2.Baluja, S., Seth, R., Sivakumar, D., Jing, Y., Yagnik, J., Kumar, S., Ravichandran, D., Aly, M.: Video suggestion and discovery for youtube: taking random walks through the view graph. In: WWW 2008, pp. 895–904 (2008)
  3.Bhatotia, P., Wieder, A., Rodrigues, R., Acar, U.A., Pasquin, R.: Incoop: Mapreduce for incremental computations. In: SoCC 2011, pp. 7:1–7:14 (2011)
  4.Bogdanov, P., Singh, A.: Accurate and scalable nearest neighbors in large networks based on effective importance. In: CIKM 2013. pp. 1009–1018 (2013)
  5.Boldi, P., Vigna, S.: The WebGraph framework I: compression techniques. In: WWW 2004, pp. 595–601 (2004)
  6.Cheng, R., Hong, J., Kyrola, A., Miao, Y., Weng, X., Wu, M., Yang, F., Zhou, L., Zhao, F., Chen, E.: Kineograph: taking the pulse of a fast-changing and connected world. In: EuroSys 2012, pp. 85–98 (2012)
  7.Gonzalez, J.E., Xin, R.S., Dave, A., Crankshaw, D., Franklin, M.J., Stoica, I.: Graphx: graph processing in a distributed dataflow framework. In: OSDI 2014, pp. 599–613 (2014)
  8.Guan, Z., Wu, J., Zhang, Q., Singh, A., Yan, X.: Assessing and ranking structural correlations in graphs. In: SIGMOD 2011, pp. 937–948 (2011)
  9.Jeh, G., Widom, J.: Scaling personalized web search. In: WWW 2003, pp. 271–279 (2003)
  10.Kleinberg, J.M.: Authoritative sources in a hyperlinked environment. J. ACM 46, 604–632 (1999)MathSciNet CrossRef MATH
  11.Langville, A.N., Meyer, C.D.: Updating PageRank with iterative aggregation. In: WWW 2004, pp. 392–393 (2004)
  12.Langville, A.N., Meyer, C.D.: Updating markov chains with an eye on Google’s PageRank. SIAM J. Matrix Anal. Appl. 27(4), 968–987 (2006)MathSciNet CrossRef MATH
  13.Lempel, R., Moran, S.: Salsa: the stochastic approach for link-structure analysis. ACM Trans. Inf. Syst. 19(2), 131–160 (2001)CrossRef
  14.Leskovec, J., Krevl, A.: SNAP datasets: stanford large network dataset collection, Jun 2014. http://​snap.​stanford.​edu/​data
  15.Logothetis, D., Olston, C., Reed, B., Webb, K.C., Yocum, K.: Stateful bulk processing for incremental analytics. In: SoCC 2010, pp. 51–62 (2010)
  16.Murray, D.G., McSherry, F., Isaacs, R., Isard, M., Barham, P., Abadi, M.: Naiad: a timely dataflow system. In: SOSP 2013, pp. 439–455 (2013)
  17.Popa, L., Budiu, M., Yu, Y., Isard, M.: Dryadinc: reusing work in large-scale computations. In: HotCloud 2009 (2009)
  18.Sarkar, P., Moore, A.W.: Fast nearest-neighbor search in disk-resident graphs. In: KDD 2010, pp. 513–522 (2010)
  19.Song, H.H., Cho, T.W., Dave, V., Zhang, Y., Qiu, L.: Scalable proximity estimation and link prediction in online social networks. In: IMC 2009, pp. 322–335 (2009)
  20.Yin, J., Gao, L.: Scalable distributed belief propagation with prioritized block updates. In: CIKM 2014, pp. 1209–1218 (2014)
  21.Yin, J., Gao, L., Zhang, Z.M.: Scalable nonnegative matrix factorization with block-wise updates. In: Calders, T., Esposito, F., Hüllermeier, E., Meo, R. (eds.) ECML PKDD 2014, Part III. LNCS, vol. 8726, pp. 337–352. Springer, Heidelberg (2014)
  22.Yin, J., Zhang, Y., Gao, L.: Accelerating expectation-maximization algorithms with frequent updates. In: CLUSTER 2012, pp. 275–283 (2012)
  23.Zaharia, M., Das, T., Li, H., Hunter, T., Shenker, S., Stoica, I.: Discretized streams: fault-tolerant streaming computation at scale. In: SOSP 2013, pp. 423–438 (2013)
  24.Zhang, C., Jiang, S., Chen, Y., Sun, Y., Han, J.: Fast inbound Top-K query for random walk with restart. In: Appice, A., Rodrigues, P.P., Santos Costa, V., Gama, J., Jorge, A., Soares, C. (eds.) ECML PKDD 2015. LNCS, vol. 9285, pp. 608–624. Springer, Heidelberg (2015)CrossRef
  25.Zhang, Y., Gao, Q., Gao, L., Wang, C.: PrIter: a distributed framework for prioritized iterative computations. In: SoCC 2011, pp. 13:1–13:14 (2011)
  26.Zhang, Y., Gao, Q., Gao, L., Wang, C.: Maiter: an asynchronous graph processing framework for delta-based accumulative iterative computation. IEEE Trans. Parallel Distrib. Syst. 25(8), 2091–2100 (2014)CrossRef
  
• 作者单位：Jiangtao Yin (17)
  Lixin Gao (17)
  
  17. University of Massachusetts Amherst, Amherst, USA
  
• 丛书名：Machine Learning and Knowledge Discovery in Databases
• ISBN：978-3-319-46227-1
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9852

文摘

Graph algorithms have become an essential component in many real-world applications. An essential property of graphs is that they are often dynamic. Many applications must update the computation result periodically on the new graph so as to keep it up-to-date. Incremental computation is a promising technique for this purpose. Traditionally, incremental computation is typically performed synchronously, since it is easy to implement. In this paper, we illustrate that incremental computation can be performed asynchronously as well. Asynchronous incremental computation can bypass synchronization barriers and always utilize the most recent values, and thus it is more efficient than its synchronous counterpart. Furthermore, we develop a distributed framework, GraphIn, to facilitate implementations of incremental computation on massive evolving graphs. We evaluate our asynchronous incremental computation approach via extensive experiments on a local cluster as well as the Amazon EC2 cloud. The evaluation results show that it can accelerate the convergence speed by as much as 14x when compared to recomputation from scratch.