In the past, I was interested in Graph due to its complex structure and the potential in application domains like social network, web, and bio-science. I developed several graph engines. Specifically, Kineograph (Cheng et al., 2012) is designed for OLAP and OLTP on fast changing graphs, Chronos (Han et al., 2014) is a system for temporal graph analytics, and GraM (Wu et al., 2015) is a high-performance graph engine that set a new speed record for trillion-scale graph analytics. GraM has been used to analyze the large-scale web data and internal Ads data of the Microsoft Bing service.
References
2015
SoCC
GraM: scaling graph computation to the trillions
Ming Wu, and 8 more authors
In Proceedings of the Sixth ACM Symposium on Cloud Computing, SoCC, Kohala Coast, Hawaii, 2015
GraM is an efficient and scalable graph engine for a large class of widely used graph algorithms. It is designed to scale up to multicores on a single server, as well as scale out to multiple servers in a cluster, offering significant, often over an order-of-magnitude, improvement over existing distributed graph engines on evaluated graph algorithms. GraM is also capable of processing graphs that are significantly larger than previously reported. In particular, using 64 servers (1,024 physical cores), it performs a PageRank iteration in 140 seconds on a synthetic graph with over one trillion edges, setting a new milestone for graph engines.GraM’s efficiency and scalability comes from a judicious architectural design that exploits the benefits of multi-core and RDMA. GraM uses a simple message-passing based scaling architecture for both scaling up and scaling out to expose inherent parallelism. It further benefits from a specially designed multi-core aware RDMA-based communication stack that preserves parallelism in a balanced way and allows overlapping of communication and computation. A high degree of parallelism often comes at the cost of lower efficiency due to resource fragmentation. GraM is equipped with an adaptive mechanism that evaluates the cost and benefit of parallelism to decide the appropriate configuration. Combined, these mechanisms allow GraM to scale up and out with high efficiency.
@inproceedings{10.1145/2806777.2806849,title={GraM: scaling graph computation to the trillions},author={Wu, Ming and Yang, Fan and Xue, Jilong and Xiao, Wencong and Miao, Youshan and Wei, Lan and Lin, Haoxiang and Dai, Yafei and Zhou, Lidong},year={2015},booktitle={Proceedings of the Sixth ACM Symposium on Cloud Computing, {SoCC}},location={Kohala Coast, Hawaii},publisher={Association for Computing Machinery},address={New York, NY, USA},series={SoCC '15},pages={408–421},doi={10.1145/2806777.2806849},isbn={9781450336512},numpages={14},keywords={RDMA, graph computation engine, scalability}}
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.
@inproceedings{10.1145/2592798.2592799,title={Chronos: a graph engine for temporal graph analysis},author={Han, Wentao and Miao, Youshan and Li, Kaiwei and Wu, Ming and Yang, Fan and Zhou, Lidong and Prabhakaran, Vijayan and Chen, Wenguang and Chen, Enhong},year={2014},booktitle={Proceedings of the Ninth European Conference on Computer Systems},location={Amsterdam, The Netherlands},publisher={Association for Computing Machinery},address={New York, NY, USA},series={EuroSys '14},doi={10.1145/2592798.2592799},isbn={9781450327046},articleno={1},numpages={14}}
Kineograph is a distributed system that takes a stream of incoming data to construct a continuously changing graph, which captures the relationships that exist in the data feed. As a computing platform, Kineograph further supports graph-mining algorithms to extract timely insights from the fast-changing graph structure. To accommodate graph-mining algorithms that assume a static underlying graph, Kineograph creates a series of consistent snapshots, using a novel and efficient epoch commit protocol. To keep up with continuous updates on the graph, Kineograph includes an incremental graph-computation engine. We have developed three applications on top of Kineograph to analyze Twitter data: user ranking, approximate shortest paths, and controversial topic detection. For these applications, Kineograph takes a live Twitter data feed and maintains a graph of edges between all users and hashtags. Our evaluation shows that with 40 machines processing 100K tweets per second, Kineograph is able to continuously compute global properties, such as user ranks, with less than 2.5-minute timeliness guarantees. This rate of traffic is more than 10 times the reported peak rate of Twitter as of October 2011.
@inproceedings{10.1145/2168836.2168846,title={Kineograph: taking the pulse of a fast-changing and connected world},author={Cheng, Raymond and Hong, Ji and Kyrola, Aapo and Miao, Youshan and Weng, Xuetian and Wu, Ming and Yang, Fan and Zhou, Lidong and Zhao, Feng and Chen, Enhong},year={2012},booktitle={Proceedings of the 7th ACM European Conference on Computer Systems},location={Bern, Switzerland},publisher={Association for Computing Machinery},address={New York, NY, USA},series={EuroSys '12},pages={85–98},doi={10.1145/2168836.2168846},isbn={9781450312233},numpages={14},keywords={distributed storage, graph processing}}