Knightking: A fast distributed graph random walk engine

Ke Yang; Ming Xing Zhang; Kang Chen; Xiaosong Ma; Yang Bai; Yong Jiang

doi:10.1145/3341301.3359634

Knightking: A fast distributed graph random walk engine

Ke Yang
, Ming Xing Zhang
, Kang Chen^*
, Xiaosong Ma
, Yang Bai
, Yong Jiang

^*Corresponding author for this work

Qatar Computing Research Institute

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

72 Citations (Scopus)

Abstract

Random walk on graphs has recently gained immense popularity as a tool for graph data analytics and machine learning. Currently, random walk algorithms are developed as individual implementations and suffer significant performance and scalability problems, especially with the dynamic nature of sophisticated walk strategies. We present KnightKing, the first general-purpose, distributed graph random walk engine. To address the unique interaction between a static graph and many dynamic walkers, it adopts an intuitive walker-centric computation model. The corresponding programming model allows users to easily specify existing or new random walk algorithms, facilitated by a new unified edge transition probability definition that applies across popular known algorithms. With KnightKing, these diverse algorithms benefit from its common distributed random walk execution engine, centered around an innovative rejection-based sampling mechanism that dramatically reduces the cost of higher-order random walk algorithms. Our evaluation confirms that KnightKing brings up to 4 orders of magnitude improvement in executing algorithms that currently can only be afforded with approximation solutions on large graphs.

Original language	English
Title of host publication	SOSP 2019 - Proceedings of the 27th ACM Symposium on Operating Systems Principles
Publisher	Association for Computing Machinery, Inc
Pages	524-537
Number of pages	14
ISBN (Electronic)	9781450368735
DOIs	https://doi.org/10.1145/3341301.3359634
Publication status	Published - 27 Oct 2019
Event	27th ACM Symposium on Operating Systems Principles, SOSP 2019 - Huntsville, Canada Duration: 27 Oct 2019 → 30 Oct 2019

Publication series

Name	SOSP 2019 - Proceedings of the 27th ACM Symposium on Operating Systems Principles

Conference

Conference	27th ACM Symposium on Operating Systems Principles, SOSP 2019
Country/Territory	Canada
City	Huntsville
Period	27/10/19 → 30/10/19

Keywords

Graph computing
Random walk
Rejection sampling

Access to Document

10.1145/3341301.3359634

Cite this

Yang, K., Zhang, M. X., Chen, K., Ma, X., Bai, Y., & Jiang, Y. (2019). Knightking: A fast distributed graph random walk engine. In SOSP 2019 - Proceedings of the 27th ACM Symposium on Operating Systems Principles (pp. 524-537). (SOSP 2019 - Proceedings of the 27th ACM Symposium on Operating Systems Principles). Association for Computing Machinery, Inc. https://doi.org/10.1145/3341301.3359634

@inproceedings{15f8723c0de549da9576448fa853ae60,

title = "Knightking: A fast distributed graph random walk engine",

abstract = "Random walk on graphs has recently gained immense popularity as a tool for graph data analytics and machine learning. Currently, random walk algorithms are developed as individual implementations and suffer significant performance and scalability problems, especially with the dynamic nature of sophisticated walk strategies. We present KnightKing, the first general-purpose, distributed graph random walk engine. To address the unique interaction between a static graph and many dynamic walkers, it adopts an intuitive walker-centric computation model. The corresponding programming model allows users to easily specify existing or new random walk algorithms, facilitated by a new unified edge transition probability definition that applies across popular known algorithms. With KnightKing, these diverse algorithms benefit from its common distributed random walk execution engine, centered around an innovative rejection-based sampling mechanism that dramatically reduces the cost of higher-order random walk algorithms. Our evaluation confirms that KnightKing brings up to 4 orders of magnitude improvement in executing algorithms that currently can only be afforded with approximation solutions on large graphs.",

keywords = "Graph computing, Random walk, Rejection sampling",

author = "Ke Yang and Zhang, \{Ming Xing\} and Kang Chen and Xiaosong Ma and Yang Bai and Yong Jiang",

note = "Publisher Copyright: {\textcopyright} 2019 Association for Computing Machinery.; 27th ACM Symposium on Operating Systems Principles, SOSP 2019 ; Conference date: 27-10-2019 Through 30-10-2019",

year = "2019",

month = oct,

day = "27",

doi = "10.1145/3341301.3359634",

language = "English",

series = "SOSP 2019 - Proceedings of the 27th ACM Symposium on Operating Systems Principles",

publisher = "Association for Computing Machinery, Inc",

pages = "524--537",

booktitle = "SOSP 2019 - Proceedings of the 27th ACM Symposium on Operating Systems Principles",

}

Yang, K, Zhang, MX, Chen, K, Ma, X, Bai, Y & Jiang, Y 2019, Knightking: A fast distributed graph random walk engine. in SOSP 2019 - Proceedings of the 27th ACM Symposium on Operating Systems Principles. SOSP 2019 - Proceedings of the 27th ACM Symposium on Operating Systems Principles, Association for Computing Machinery, Inc, pp. 524-537, 27th ACM Symposium on Operating Systems Principles, SOSP 2019, Huntsville, Canada, 27/10/19. https://doi.org/10.1145/3341301.3359634

Knightking: A fast distributed graph random walk engine. / Yang, Ke; Zhang, Ming Xing; Chen, Kang et al.
SOSP 2019 - Proceedings of the 27th ACM Symposium on Operating Systems Principles. Association for Computing Machinery, Inc, 2019. p. 524-537 (SOSP 2019 - Proceedings of the 27th ACM Symposium on Operating Systems Principles).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Knightking

T2 - 27th ACM Symposium on Operating Systems Principles, SOSP 2019

AU - Yang, Ke

AU - Zhang, Ming Xing

AU - Chen, Kang

AU - Ma, Xiaosong

AU - Bai, Yang

AU - Jiang, Yong

PY - 2019/10/27

Y1 - 2019/10/27

N2 - Random walk on graphs has recently gained immense popularity as a tool for graph data analytics and machine learning. Currently, random walk algorithms are developed as individual implementations and suffer significant performance and scalability problems, especially with the dynamic nature of sophisticated walk strategies. We present KnightKing, the first general-purpose, distributed graph random walk engine. To address the unique interaction between a static graph and many dynamic walkers, it adopts an intuitive walker-centric computation model. The corresponding programming model allows users to easily specify existing or new random walk algorithms, facilitated by a new unified edge transition probability definition that applies across popular known algorithms. With KnightKing, these diverse algorithms benefit from its common distributed random walk execution engine, centered around an innovative rejection-based sampling mechanism that dramatically reduces the cost of higher-order random walk algorithms. Our evaluation confirms that KnightKing brings up to 4 orders of magnitude improvement in executing algorithms that currently can only be afforded with approximation solutions on large graphs.

AB - Random walk on graphs has recently gained immense popularity as a tool for graph data analytics and machine learning. Currently, random walk algorithms are developed as individual implementations and suffer significant performance and scalability problems, especially with the dynamic nature of sophisticated walk strategies. We present KnightKing, the first general-purpose, distributed graph random walk engine. To address the unique interaction between a static graph and many dynamic walkers, it adopts an intuitive walker-centric computation model. The corresponding programming model allows users to easily specify existing or new random walk algorithms, facilitated by a new unified edge transition probability definition that applies across popular known algorithms. With KnightKing, these diverse algorithms benefit from its common distributed random walk execution engine, centered around an innovative rejection-based sampling mechanism that dramatically reduces the cost of higher-order random walk algorithms. Our evaluation confirms that KnightKing brings up to 4 orders of magnitude improvement in executing algorithms that currently can only be afforded with approximation solutions on large graphs.

KW - Graph computing

KW - Random walk

KW - Rejection sampling

UR - https://www.scopus.com/pages/publications/85076727705

U2 - 10.1145/3341301.3359634

DO - 10.1145/3341301.3359634

M3 - Conference contribution

AN - SCOPUS:85076727705

T3 - SOSP 2019 - Proceedings of the 27th ACM Symposium on Operating Systems Principles

SP - 524

EP - 537

BT - SOSP 2019 - Proceedings of the 27th ACM Symposium on Operating Systems Principles

PB - Association for Computing Machinery, Inc

Y2 - 27 October 2019 through 30 October 2019

ER -

Knightking: A fast distributed graph random walk engine

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this