Wentao Han
ABSTRACT
Temporal graphs capture changes in graphs over time and are becoming a subject that attracts increasing interest from the research communities, for example, to understand temporal characteristics of social interactions on a time-evolving social graph. Chronos is a storage and execution engine designed and optimized specifically for running in-memory iterative graph computation on temporal graphs. Locality is at the center of the Chronos design, where the in-memory layout of temporal graphs and the scheduling of the iterative computation on temporal graphs are carefully designed, so that common "bulk" operations on temporal graphs are scheduled to maximize the benefit of in-memory data locality. The design of Chronos further explores the interesting interplay among locality, parallelism, and incremental computation in supporting common mining tasks on temporal graphs. The result is a high-performance temporal-graph system that offers up to an order of magnitude speedup for temporal iterative graph mining compared to a straightforward application of existing graph engines on a series of snapshots.
- C. C. Aggarwal and H. Wang, editors. Managing and Mining Graph Data, volume 40 of Advances in Database Systems. Springer, 2010. Google Scholar
Digital Library
- P. Boldi, M. Santini, and S. Vigna. A large time-aware web graph. SIGIR Forum, 42(2):33--38, 2008. Google ScholarDigital Library
- S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Computer Networks, 30(1-7):107--117, 1998. Google ScholarDigital Library
- R. Chen, J. Shi, Y. Chen, H. Guan, B. Zang, and H. Chen. Powerlyra: Differentiated graph computation and partitioning on skewed graphs. Technical Report IPADSTR-2013-001, Shanghai Jiao Tong Univ., 2013.Google Scholar
- R. Cheng, J. Hong, A. Kyrola, Y. Miao, X. Weng, M. Wu, F. Yang, L. Zhou, F. Zhao, and E. Chen. Kineograph: taking the pulse of a fast-changing and connected world. In EuroSys, pages 85--98. ACM, 2012. Google ScholarDigital Library
- M. Frigo, C. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In FOCS, 1999. Google ScholarDigital Library
- J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. Powergraph: distributed graph-parallel computation on natural graphs. In OSDI, pages 17--30, 2012. Google ScholarDigital Library
- G. Karypis and V. Kumar. METIS - unstructured graph partitioning and sparse matrix ordering system, ver 2.0. Technical report, Univ. of Minnesota, 1995.Google Scholar
- Z. Khayyat, K. Awara, A. Alonazi, H. Jamjoom, D. Williams, and P. Kalnis. Mizan: a system for dynamic load balancing in large-scale graph processing. In EuroSys, pages 169--182, 2013. Google ScholarDigital Library
- U. Khurana and A. Deshpande. Efficient snapshot retrieval over historical graph data. In ICDE, 2013. Google ScholarDigital Library
- A. Kyrola, G. Blelloch, and C. Guestrin. GraphChi: large-scale graph computation on just a PC. In OSDI, volume 8, pages 31--46, 2012. Google ScholarDigital Library
- K. Lerman, R. Ghosh, and J. H. Kang. Centrality metric for dynamic networks. In MLG, pages 70--77, 2010. Google ScholarDigital Library
- J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In KDD, pages 177--187, 2005. Google ScholarDigital Library
- D. Lomet, R. Barga, M. F. Mokbel, G. Shegalov, R. Wang, and Y. Zhu. Immortal db: transaction time support for SQL server. In SIGMOD, 2005. Google ScholarDigital Library
- D. Lomet and B. Salzberg. Access methods for multiversion data. In SIGMOD, pages 315--324, 1989. Google ScholarDigital Library
- Y. Low, D. Bickson, J. Gonzalez, C. Guestrin, A. Kyrola, and J. M. Hellerstein. Distributed GraphLab: a framework for machine learning and data mining in the cloud. PVLDB, 5(8):716--727, Apr. 2012. Google ScholarDigital Library
- G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In SIGMOD, pages 135--146, 2010. Google ScholarDigital Library
- A. Mislove. Online social networks: measurement, analysis, and applications to distributed information systems. PhD thesis, Rice University, 2009. Google ScholarDigital Library
- D. Murray, F. McSherry, R. Isaacs, M. Isard, P. Barham, and M. Abadi. Naiad: a timely dataflow system. In SOSP, pages 439--455, 2013. Google ScholarDigital Library
- D. Nguyen, A. Lenharth, and K. Pingali. A lightweight infrastructure for graph analytics. In SOSP, pages 456--471, 2013. Google ScholarDigital Library
- PostgreSQL. PostgreSQL, 2013. http://postgresql.org.Google Scholar
- R. Power and J. Li. Piccolo: Building fast, distributed programs with partitioned tables. In OSDI, pages 1--14, 2010. Google ScholarDigital Library
- V. Prabhakaran, M. Wu, X. Weng, F. McSherry, L. Zhou, and M. Haridasan. Managing large graphs on multi-cores with graph awareness. In USENIX ATC, volume 12, 2012. Google ScholarDigital Library
- C. Ren, E. Lo, B. Kao, X. Zhu, and R. Cheng. On querying historical evolving graph sequences. PVLDB, 4(11):726--737, 2011.Google ScholarDigital Library
- L. Roditty and U. Zwick. On dynamic shortest paths problems. In ESA, pages 580--591, 2004.Google ScholarCross Ref
- D. M. Romero, B. Meeder, and J. Kleinberg. Differences in the mechanics of information diffusion across topics: idioms, political hashtags, and complex contagion on twitter. In WWW, pages 695--704, 2011. Google ScholarDigital Library
- A. Roy, I. Mihailovic, and W. Zwaenepoel. X-stream: edge-centric graph processing using streaming partitions. In SOSP, pages 472--488, 2013. Google ScholarDigital Library
- B. Salzberg and V. J. Tsotras. Comparison of access methods for time-evolving data. ACM Comput. Surv., 31(2):158--221, June 1999. Google ScholarDigital Library
- J. Shun and G. E. Blelloch. Ligra: a lightweight graph processing framework for shared memory. In PPoPP, pages 135--146, 2013. Google ScholarDigital Library
- Sina. Weibo, 2013. http://weibo.com.Google Scholar
- S. Venkataraman, E. Bodzsar, I. Roy, A. AuYoung, and R. Schreiber. Presto: distributed machine learning and graph processing with sparse matrices. In EuroSys, pages 197--210, 2013. Google ScholarDigital Library
- C. Wilson, B. Boe, R. Sala, K. P. N. Puttaswamy, and B. Y. Zhao. User interactions in social networks and their implications. In EuroSys, pages 205--218, 2009. Google ScholarDigital Library
- L. Yang, L. Qi, Y.-P. Zhao, B. Gao, and T.-Y. Liu. Link analysis using time series of web graphs. In CIKM, pages 1011--1014, 2007. Google ScholarDigital Library
- M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. Franklin, S. Shenker, and I. Stoica. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In NSDI, pages 2--2, 2012. Google ScholarDigital Library
- R. Zhang and M. Stradling. The HV-tree: a memory hierarchy aware version index. PVLDB, 3(1--2):397--408, Sept. 2010. Google ScholarDigital Library
Recommendations
CHRONOS: A Tool for Handling Temporal Ontologies in Protégé
ICTAI '12: Proceedings of the 2012 IEEE 24th International Conference on Tools with Artificial Intelligence - Volume 01Representing information evolving in time in ontologies is a difficult problem to deal with. Temporal relations are in fact ternary (i.e., properties of objects that change in time involve also a temporal value in addition to the object and the subject) ...
CHRONOS: Improving the Performance of Qualitative Temporal Reasoning in OWL
ICTAI '14: Proceedings of the 2014 IEEE 26th International Conference on Tools with Artificial IntelligenceWe investigate on potential improvements to reasoning about qualitative temporal information in OWL. Building upon path consistency, the new reasoner design, referred to as CHRONOS, computes a minimal set of relation compositions at run-time (based on a ...
On the Multichromatic Number of s-Stable Kneser Graphs
For positive integers n and s, a subset Sï [n] is s-stable if sï |i-j|ï n-s for distinct i,j∈S . The s-stable r-uniform Kneser hypergraph KGrn,ks-stable is the r-uniform hypergraph that has the collection of all s-stable k-element subsets of [n] as ...
Comments