research-article

Open access

NosWalker: A Decoupled Architecture for Out-of-Core Random Walk Processing

Authors:

Mingxing Zhang,

Yongwei WuAuthors Info & Claims

ASPLOS 2023: Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3

Pages 466 - 482

https://doi.org/10.1145/3582016.3582025

Published: 25 March 2023 Publication History

Abstract

Out-of-core random walk system has recently attracted a lot of attention as an economical way to run billions of walkers over large graphs. However, existing out-of-core random walk systems are all built upon general out-of-core graph processing frameworks, and hence do not take advantage of the unique properties of random walk applications. Different from traditional graph analysis algorithms, the sampling process of random walk can be decoupled from the processing of the walkers. It enables the system to reserve only pre-sample results in memory, which are typically much smaller than the entire edge set. Moreover, in random walk, it is not the number of walkers but the number of steps moved per second that dominates the overall performance. Thus, with independent walkers, there is no need to process all the walkers simultaneously.

In this paper, we present NosWalker, an out-of-core random walk system that replaces the graph oriented scheduling with a decoupled system architecture that provides walker oriented scheduling. NosWalker is able to adaptively generate walkers and flexibly adjust the distribution of reserved pre-sample results in memory. Instead of processing all the walkers at once, NosWalker only tries its best to keep a few walkers able to continuously move forward. Experimental results show that NosWalker can achieve up to two orders of magnitude speedup compared to state-of-the-art out-of-core random walk systems. In particular, NosWalker demonstrates superior performance when the memory capacity can only hold about 10%-50% of the graph data, which can be a common case when the user needs to run billions of walkers over large graphs.

References

[1]

2022. The 2012 common crawl graph. http://webdatacommons.org/

[2]

2022. cgroups(7) Linux manual page. https://man7.org/linux/man-pages/man7/cgroups.7.html

[3]

2022. Graph 500. https://graph500.org/

[4]

2022. Linux-native asynchronous I/O access library. https://pagure.io/libaio

[5]

2022. Linux System Administrators Guide: Chapter 6. Memory Management. https://tldp.org/LDP/sag/html/buffer-cache.html

[6]

2022. Node2vec on Spark. https://github.com/aditya-grover/node2vec

[7]

2022. Random walk. https://en.wikipedia.org/wiki/Random_walk

[8]

2023. Price of ECC Unbuffered Memory. https://www.amazon.com/Tech-Unbuffered-Memory-PowerEdge-Server/dp/B07NQS57WZ?th=1

[9]

2023. Price of Intel SSD D7-P5510 Series. https://www.amazon.com/Intel-SSD-D7-P5510-Series-7-68TB/dp/B08R3YQN2V

[10]

Khushbu Agarwal, Tome Eftimov, Raghavendra Addanki, Sutanay Choudhury, Suzanne Tamang, and Robert Rallo. 2019. Snomed2Vec: Random Walk and Poincaré Embeddings of a Clinical Knowledge Base for Healthcare Analytics. arXiv preprint arXiv:1907.08650.

[11]

Joachim H Ahrens and Ulrich Dieter. 1989. An alias method for sampling from the normal distribution. Computing, 42, 2-3 (1989), 159–170. https://doi.org/10.1007/BF02239745

Digital Library

[12]

Zhiyuan Ai, Mingxing Zhang, Yongwei Wu, Xuehai Qian, Kang Chen, and Weimin Zheng. 2018. Clip: A disk I/O focused parallel out-of-core graph processing system. IEEE Transactions on Parallel and Distributed Systems, 30, 1 (2018), 45–62. https://doi.org/10.1109/TPDS.2018.2858250

Digital Library

[13]

Michael J Anderson, Narayanan Sundaram, Nadathur Satish, Md Mostofa Ali Patwary, Theodore L Willke, and Pradeep Dubey. 2016. Graphpad: Optimized graph primitives for parallel and distributed platforms. In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 313–322. https://doi.org/10.1109/IPDPS.2016.86

[14]

Béla Bollobás. 1980. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics, 1, 4 (1980), 311–316. https://doi.org/10.1016/S0195-6698(80)80030-8

[15]

Yuanzhe Cai, Pei Li, Hongyan Liu, Jun He, and Xiaoyong Du. 2008. S-simrank: Combining content and link information to cluster papers effectively and efficiently. In International Conference on Advanced Data Mining and Applications. 317–329. https://doi.org/10.1007/978-3-540-88192-6_30

Digital Library

[16]

Mo Chen, Jianzhuang Liu, and Xiaoou Tang. 2008. Clustering via Random Walk Hitting Time on Directed Graphs. In Proceedings of the 23rd national conference on Artificial intelligence-Volume 2. 616–621.

Digital Library

[17]

Rong Chen, Jiaxin Shi, Yanzhe Chen, and Haibo Chen. 2015. PowerLyra: Differentiated graph computation and partitioning on skewed graphs. In Proceedings of the Tenth European Conference on Computer Systems. 1–15. https://doi.org/10.1145/3298989

Digital Library

[18]

Shuhan Cheng, Guangyan Zhang, Jiwu Shu, and Weimin Zheng. 2016. Asyncstripe: I/o efficient asynchronous graph computing on a single server. In Proceedings of the Eleventh IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis. 1–10. https://doi.org/10.1145/2968456.2968473

Digital Library

[19]

Avery Ching, Sergey Edunov, Maja Kabiljo, Dionysios Logothetis, and Sambavi Muthukrishnan. 2015. One trillion edges: Graph processing at facebook-scale. Proceedings of the VLDB Endowment, 8, 12 (2015), 1804–1815. https://doi.org/10.14778/2824032.2824077

Digital Library

[20]

Fan Chung and Wenbo Zhao. 2010. PageRank and random walks on graphs. In Fete of combinatorics and computer science. Springer, 43–62. https://doi.org/10.1007/978-3-642-13580-4_3

[21]

Nick Craswell and Martin Szummer. 2007. Random walks on the click graph. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval. 239–246. https://doi.org/10.1145/1277741.1277784

Digital Library

[22]

Wendy Ellens, Floske M Spieksma, Piet Van Mieghem, Almerima Jamakovic, and Robert E Kooij. 2011. Effective graph resistance. Linear algebra and its applications, 435, 10 (2011), 2491–2506. https://doi.org/10.1016/j.laa.2011.02.024

[23]

Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. 1999. On power-law relationships of the internet topology. ACM SIGCOMM computer communication review, 29, 4 (1999), 251–262. https://doi.org/10.1145/316194.316229

Digital Library

[24]

Siying Feng, Jiawen Sun, Subhankar Pal, Xin He, Kuba Kaszyk, Dong-hyeon Park, Magnus Morton, Trevor Mudge, Murray Cole, and Michael O’Boyle. 2021. CoSPARSE: A Software and Hardware Reconfigurable SpMV Framework for Graph Analytics. In 2021 58th ACM/IEEE Design Automation Conference (DAC). 949–954. https://doi.org/10.1109/DAC18074.2021.9586114

Digital Library

[25]

Dániel Fogaras, Balázs Rácz, Károly Csalogány, and Tamás Sarlós. 2005. Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internet Mathematics, 2, 3 (2005), 333–358. https://doi.org/10.1080/15427951.2005.10129104

[26]

Santo Fortunato and Darko Hric. 2016. Community detection in networks: A user guide. Physics reports, 659 (2016), 1–44. https://doi.org/10.1016/j.physrep.2016.09.002

[27]

Francois Fouss, Alain Pirotte, Jean-Michel Renders, and Marco Saerens. 2007. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Transactions on knowledge and data engineering, 19, 3 (2007), 355–369. https://doi.org/10.1109/TKDE.2007.46

Digital Library

[28]

Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. 1983. A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and systems (TOPLAS), 5, 1 (1983), 66–77. https://doi.org/10.1145/357195.357200

Digital Library

[29]

Prasun Gera, Hyojong Kim, Piyush Sao, Hyesoon Kim, and David Bader. 2020. Traversing large graphs on GPUs with unified memory. Proceedings of the VLDB Endowment, 13, 7 (2020), 1119–1133. https://doi.org/10.14778/3384345.3384358

Digital Library

[30]

Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. PowerGraph: Distributed graph-parallel computation on natural graphs. In the Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12). Hollywood, CA. 17–30. https://doi.org/10.5555/2387880.2387883

Digital Library

[31]

Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 855–864. https://doi.org/10.1145/2939672.2939754

Digital Library

[32]

Masoud Reyhani Hamedani and Sang-Wook Kim. 2016. SimRank and its variants in academic literature data: measures and evaluation. In Proceedings of the 31st Annual ACM Symposium on Applied Computing. 1102–1107. https://doi.org/10.1145/2851613.2851811

Digital Library

[33]

Wook-Shin Han, Sangyeon Lee, Kyungyeol Park, Jeong-Hoon Lee, Min-Soo Kim, Jinha Kim, and Hwanjo Yu. 2013. TurboGraph: a fast parallel graph engine handling billion-scale graphs in a single PC. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. 77–85. https://doi.org/10.1145/2487575.2487581

Digital Library

[34]

Abhinav Jangda, Sandeep Polisetty, Arjun Guha, and Marco Serafini. 2021. Accelerating graph sampling for graph machine learning using GPUs. In Proceedings of the 16th European Conference on Computer Systems. 311–326. https://doi.org/10.1145/3447786.3456244

Digital Library

[35]

Glen Jeh and Jennifer Widom. 2002. Simrank: a measure of structural-context similarity. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. 538–543. https://doi.org/10.1145/775047.775126

Digital Library

[36]

Sang-Woo Jun, Andy Wright, Sizhuo Zhang, and Shuotao Xu. 2018. GraFBoost: Using accelerated flash storage for external graph analytics. In 2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA). 411–424. https://doi.org/10.1109/ISCA.2018.00042

Digital Library

[37]

Richard A Kronmal and Arthur V Peterson Jr. 1979. On the alias method for generating random variables from a discrete distribution. The American Statistician, 33, 4 (1979), 214–218. https://doi.org/10.1080/00031305.1979.10482697

[38]

Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What is Twitter, a social network or a news media? In Proceedings of the 19th international conference on World Wide Web. 591–600. https://doi.org/10.1145/1772690.1772751

Digital Library

[39]

Aapo Kyrola. 2013. Drunkardmob: Billions of random walks on just a PC. In Proceedings of the 7th ACM conference on Recommender systems. 257–264. https://doi.org/10.1145/2507157.2507173

Digital Library

[40]

Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. 2012. Graphchi: Large-scale graph computation on just a $PC$. In 10th $USENIX$ Symposium on Operating Systems Design and Implementation ($OSDI$ 12). 31–46. https://doi.org/10.5555/2387880.2387884

Digital Library

[41]

Kartik Lakhotia, Rajgopal Kannan, and Viktor Prasanna. 2018. Accelerating $PageRank$ using $Partition-Centric$ Processing. In 2018 USENIX Annual Technical Conference (USENIX ATC 18). 427–440. https://doi.org/10.5555/3277355.3277397

Digital Library

[42]

Hongzheng Li, Yingxia Shao, Junping Du, Bin Cui, and Lei Chen. 2022. An I/O-efficient disk-based graph system for scalable second-order random walk of large graphs. Proceedings of the VLDB Endowment, 15, 8 (2022), 1619–1631. https://doi.org/10.14778/3529337.3529346

Digital Library

[43]

Pei Li, Hongyan Liu, Jeffrey Xu Yu, Jun He, and Xiaoyong Du. 2010. Fast single-pair simrank computation. In Proceedings of the 2010 SIAM International Conference on Data Mining. 571–582. https://doi.org/10.1137/1.9781611972801.50

[44]

Rong-Hua Li, Jeffrey Xu Yu, Xin Huang, and Hong Cheng. 2014. Random-walk domination in large graphs. In 2014 IEEE 30th International Conference on Data Engineering. 736–747. https://doi.org/10.1109/ICDE.2014.6816696

[45]

Hang Liu and H Howie Huang. 2017. Graphene: Fine-grained $IO$ management for graph computing. In 15th $USENIX$ Conference on File and Storage Technologies ($FAST$ 17). 285–300. https://doi.org/10.5555/3129633.3129659

Digital Library

[46]

Qin Liu, Zhenguo Li, John CS Lui, and Jiefeng Cheng. 2016. Powerwalk: Scalable personalized pagerank via random walks with vertex-centric decomposition. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. 195–204. https://doi.org/10.1145/2983323.2983713

Digital Library

[47]

Steffen Maass, Changwoo Min, Sanidhya Kashyap, Woonhak Kang, Mohan Kumar, and Taesoo Kim. 2017. Mosaic: Processing a trillion-edge graph on a single machine. In Proceedings of the Twelfth European Conference on Computer Systems. 527–543. https://doi.org/10.1145/3064176.3064191

Digital Library

[48]

Daniel Margo and Margo Seltzer. 2015. A scalable distributed graph partitioner. Proceedings of the VLDB Endowment, 8, 12 (2015), 1478–1489. https://doi.org/10.14778/2824032.2824046

Digital Library

[49]

Abbas Mazloumi, Xiaolin Jiang, and Rajiv Gupta. 2019. Multilyra: Scalable distributed evaluation of batches of iterative graph queries. In 2019 IEEE International Conference on Big Data (Big Data). 349–358. https://doi.org/10.1109/BigData47090.2019.9006359

[50]

Michael Molloy and Bruce Reed. 1995. A critical point for random graphs with a given degree sequence. Random structures & algorithms, 6, 2-3 (1995), 161–180. https://doi.org/10.1002/rsa.3240060204

Digital Library

[51]

Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank citation ranking: Bringing order to the web. Stanford InfoLab.

[52]

Santosh Pandey, Lingda Li, Adolfy Hoisie, Xiaoye S Li, and Hang Liu. 2020. C-SAW: A framework for graph sampling and random walk on GPUs. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis. 1–15. https://doi.org/10.1109/SC41405.2020.00060

[53]

Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. DeepWalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 701–710. https://doi.org/10.1145/2623330.2623732

Digital Library

[54]

Nataša Pržulj. 2007. Biological network comparison using graphlet degree distribution. Bioinformatics, 23, 2 (2007), e177–e183. https://doi.org/10.1093/bioinformatics/btl301

Digital Library

[55]

Natasa Pržulj, Derek G Corneil, and Igor Jurisica. 2004. Modeling interactome: scale-free or geometric? Bioinformatics, 20, 18 (2004), 3508–3515. https://doi.org/10.1093/bioinformatics/bth436

[56]

Bruno Ribeiro and Don Towsley. 2010. Estimating and sampling graphs with multidimensional random walks. In Proceedings of the 10th ACM SIGCOMM conference on Internet measurement. 390–403. https://doi.org/10.1145/1879141.1879192

Digital Library

[57]

Amitabha Roy, Ivo Mihailovic, and Willy Zwaenepoel. 2013. X-stream: Edge-centric graph processing using streaming partitions. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. 472–488. https://doi.org/10.1145/2517349.2522740

Digital Library

[58]

Semih Salihoglu and Jennifer Widom. 2013. Computing strongly connected components in pregel-like systems. Technical report, Stanford University.

[59]

Yingxia Shao, Shiyue Huang, Xupeng Miao, Bin Cui, and Lei Chen. 2020. Memory-aware framework for efficient second-order random walk on large graphs. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 1797–1812. https://doi.org/10.1145/3318464.3380562

Digital Library

[60]

Peng Sun, Yonggang Wen, Ta Nguyen Binh Duong, and Xiaokui Xiao. 2017. Graphmp: An efficient semi-external-memory big graph processing system on a single machine. In 2017 IEEE 23rd International Conference on Parallel and Distributed Systems (ICPADS). 276–283. https://doi.org/10.1109/ICPADS.2017.00045

[61]

Shixuan Sun, Yuhang Chen, Shengliang Lu, Bingsheng He, and Yuchen Li. 2021. ThunderRW: An in-memory graph random walk engine. In Proc. VLDB Endow. 14, 1992–2005. https://doi.org/10.14778/3476249.3476257

Digital Library

[62]

Hanghang Tong, Christos Faloutsos, and Jia-Yu Pan. 2006. Fast random walk with restart and its applications. In Sixth international conference on data mining (ICDM’06). 613–622. https://doi.org/10.1109/ICDM.2006.70

Digital Library

[63]

Hanghang Tong, Christos Faloutsos, and Jia-Yu Pan. 2008. Random walk with restart: fast solutions and applications. Knowledge and Information Systems, 14, 3 (2008), 327–346. https://doi.org/10.1007/s10115-007-0094-2

Digital Library

[64]

John Von Neumann. 1951. 13. various techniques used in connection with random digits. Appl. Math Ser, 12, 36-38 (1951), 3.

[65]

Keval Vora. 2019. $LUMOS$: Dependency-Driven Disk-based Graph Processing. In 2019 $USENIX$ Annual Technical Conference ($USENIX$$ATC$ 19). 429–442. https://doi.org/10.5555/3358807.3358844

Digital Library

[66]

Keval Vora, Guoqing Xu, and Rajiv Gupta. 2016. Load the Edges You Need: A Generic $I/O$ Optimization for Disk-based Graph Processing. In 2016 USENIX Annual Technical Conference (USENIX ATC 16). 507–522. https://doi.org/10.5555/3026959.3027006

Digital Library

[67]

Pengyu Wang, Chao Li, Jing Wang, Taolei Wang, Lu Zhang, Jingwen Leng, Quan Chen, and Minyi Guo. 2021. Skywalker: Efficient Alias-Method-Based Graph Sampling and Random Walk on GPUs. In 2021 30th International Conference on Parallel Architectures and Compilation Techniques (PACT). 304–317. https://doi.org/10.1109/PACT52795.2021.00029

Digital Library

[68]

Rui Wang, Yongkun Li, Hong Xie, Yinlong Xu, and John C. S. Lui. 2020. GraphWalker: An I/O-efficient and resource-friendly graph analytic system for fast and scalable random walks. In 2020 USENIX Annual Technical Conference (USENIX ATC 20). 559–571. https://doi.org/10.5555/3489146.3489184

Digital Library

[69]

Wanjing Wei, Yangzihao Wang, Pin Gao, Shijie Sun, and Donghai Yu. 2020. A distributed multi-GPU system for large-scale node embedding at Tencent. arXiv preprint arXiv:2005.13789.

[70]

Chengshuo Xu, Abbas Mazloumi, Xiaolin Jiang, and Rajiv Gupta. 2022. SimGQ+: Simultaneously evaluating iterative point-to-all and point-to-point graph queries. Journal of parallel and distributed computing, 164 (2022), 12–27. https://doi.org/10.1016/j.jpdc.2022.01.007

Digital Library

[71]

Yahoo!. 2002. Yahoo! AltaVista Web Page Hyperlink Connectivity Graph. https://webscope.sandbox.yahoo.com/catalog.php?datatype=g

[72]

Ke Yang, Xiaosong Ma, Saravanan Thirumuruganathan, Kang Chen, and Yongwei Wu. 2021. Random Walks on Huge Graphs at Cache Efficiency. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles CD-ROM. 311–326. https://doi.org/10.1145/3477132.3483575

Digital Library

[73]

Ke Yang, MingXing Zhang, Kang Chen, Xiaosong Ma, Yang Bai, and Yong Jiang. 2019. KnightKing: A fast distributed graph random walk engine. In Proceedings of the 27th ACM Symposium on Operating Systems Principles. 524–537. https://doi.org/10.1145/3341301.3359634

Digital Library

[74]

Luh Yen, Denis Vanvyve, Fabien Wouters, François Fouss, Michel Verleysen, and Marco Saerens. 2005. clustering using a random walk based distance measure. In ESANN. 317–324.

[75]

Serif Yesil, Azin Heidarshenas, Adam Morrison, and Josep Torrellas. 2020. Speeding up SpMV for power-law graph analytics by enhancing locality & vectorization. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis. 1–15. https://doi.org/10.1109/SC41405.2020.00090

[76]

Dalong Zhang, Xin Huang, Ziqi Liu, Jun Zhou, Zhiyang Hu, Xianzheng Song, Zhibang Ge, Lin Wang, Zhiqiang Zhang, and Yuan Qi. [n. d.]. AGL: A Scalable System for Industrial-purpose Graph Machine Learning. Proceedings of the VLDB Endowment, 13, 12 ([n. d.]), https://doi.org/10.14778/3415478.3415539

Digital Library

[77]

Mingxing Zhang, Yongwei Wu, Youwei Zhuo, Xuehai Qian, Chengying Huan, and Kang Chen. 2018. Wonderland: A novel abstraction-based out-of-core graph processing system. 53, 2 (2018), 608–621. https://doi.org/10.1145/3296957.3173208

Digital Library

[78]

Yu Zhang, Xiaofei Liao, Hai Jin, Lin Gu, Ligang He, Bingsheng He, and Haikun Liu. 2018. CGraph: A correlations-aware approach for efficient concurrent iterative graph processing. In 2018 $USENIX$ Annual Technical Conference ($USENIX$$ATC$ 18). 441–452. https://doi.org/10.5555/3277355.3277398

Digital Library

[79]

Jin Zhao, Yu Zhang, Xiaofei Liao, Ligang He, Bingsheng He, Hai Jin, Haikun Liu, and Yicheng Chen. 2019. GraphM: an efficient storage system for high throughput of concurrent graph processing. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1–14. https://doi.org/10.1145/3295500.3356143

Digital Library

[80]

Chenguang Zheng, Hongzhi Chen, Yuxuan Cheng, Zhezheng Song, Yifan Wu, Changji Li, James Cheng, Hao Yang, and Shuai Zhang. 2022. ByteGNN: efficient graph neural network training at large scale. Proceedings of the VLDB Endowment, 15, 6 (2022), 1228–1242. https://doi.org/10.14778/3514061.3514069

Digital Library

[81]

Da Zheng, Disa Mhembere, Randal Burns, Joshua Vogelstein, Carey E Priebe, and Alexander S Szalay. 2015. FlashGraph: Processing billion-node graphs on an array of commodity SSDs. In 13th $USENIX$ conference on file and storage technologies ($FAST$ 15). 45–58. https://doi.org/10.5555/2750482.2750486

Digital Library

[82]

Yunhong Zhou, Dennis Wilkinson, Robert Schreiber, and Rong Pan. 2008. Large-scale parallel collaborative filtering for the netflix prize. In International conference on algorithmic applications in management. 337–348. https://doi.org/10.1007/978-3-540-68880-8_32

Digital Library

[83]

Xiaowei Zhu, Wentao Han, and Wenguang Chen. 2015. GridGraph: Large-scale graph processing on a single machine using 2-level hierarchical partitioning. In USENIX ATC ’15 Proceedings of the 2015 USENIX Conference on Usenix Annual Technical Conference. 375–386. https://doi.org/10.5555/2813767.2813795

Digital Library

Cited By

Lin SWang RLi YXu YLui J(2025)Two-Dimensional Balanced Partitioning and Efficient Caching for Distributed Graph AnalysisIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.350129236:2(133-149)Online publication date: Feb-2025
https://doi.org/10.1109/TPDS.2024.3501292
Mei JSun SLi CXu CChen CLiu YWang JZhao CHou XGuo MHe BCong X(2024)FlowWalker: A Memory-Efficient and High-Performance GPU-Based Dynamic Graph Random Walk FrameworkProceedings of the VLDB Endowment10.14778/3659437.365943817:8(1788-1801)Online publication date: 31-May-2024
https://dl.acm.org/doi/10.14778/3659437.3659438
Huan CLiu YZhang HSong SPandey SChen SFang XJin YLepers BWu YLiu H(2024)TEA+: A Novel Temporal Graph Random Walk Engine with Hybrid Storage ArchitectureACM Transactions on Architecture and Code Optimization10.1145/365260421:2(1-26)Online publication date: 21-May-2024
https://dl.acm.org/doi/10.1145/3652604
Show More Cited By

Index Terms

NosWalker: A Decoupled Architecture for Out-of-Core Random Walk Processing

Recommendations

Simulation of postural sway by elastically tethered random walk
MMES'10: Proceedings of the 2010 international conference on Mathematical models for engineering science

Stabilometry is routinely used to asses postural steadiness of human body by measuring the movements of the centre of pressure (postural sway) of a standing subject with a force platform. Data acquisition time dependence of various postural sway ...
Diffusivity of a random walk on random walks

We consider a random walk Zn1,',ZnK+1∈ï K+1 with the constraint that each coordinate of the walk is at distance one from the following one. In this paper, we show that this random walk is slowed down by a variance factor ï K2=2K+2 with respect to the ...
The Stirling's formula and Polya's random walk theorem
ESET '24: Proceedings of the 2024 8th International Conference on E-Society, E-Education and E-Technology

This paper is about Stirling's formula and its application in random walk, The article first introduces the Stirling's formula and random walks, as well as their applications, and then provides proofs for the Stirling's formula and some lemmas. We have ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPLOS 2023: Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3

March 2023

820 pages

ISBN:9781450399180

DOI:10.1145/3582016

General Chair:
Tor M. Aamodt
University of British Columbia, Canada
,
Program Chairs:
Natalie Enright Jerger
University of Toronto, Canada
,
Michael Swift
University of Wisconsin-Madison, USA

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution 4.0 International License.

Sponsors

In-Cooperation

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 March 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Key Research & Development Program of China
Natural Science Foundation of China

Conference

ASPLOS '23

Sponsor:

ASPLOS '23: 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3

March 25 - 29, 2023

BC, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 535 of 2,713 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
855
Total Downloads

Downloads (Last 12 months)294
Downloads (Last 6 weeks)41

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lin SWang RLi YXu YLui J(2025)Two-Dimensional Balanced Partitioning and Efficient Caching for Distributed Graph AnalysisIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.350129236:2(133-149)Online publication date: Feb-2025
https://doi.org/10.1109/TPDS.2024.3501292
Mei JSun SLi CXu CChen CLiu YWang JZhao CHou XGuo MHe BCong X(2024)FlowWalker: A Memory-Efficient and High-Performance GPU-Based Dynamic Graph Random Walk FrameworkProceedings of the VLDB Endowment10.14778/3659437.365943817:8(1788-1801)Online publication date: 31-May-2024
https://dl.acm.org/doi/10.14778/3659437.3659438
Huan CLiu YZhang HSong SPandey SChen SFang XJin YLepers BWu YLiu H(2024)TEA+: A Novel Temporal Graph Random Walk Engine with Hybrid Storage ArchitectureACM Transactions on Architecture and Code Optimization10.1145/365260421:2(1-26)Online publication date: 21-May-2024
https://dl.acm.org/doi/10.1145/3652604
Li YSun SXiao HYe CLu SHe B(2024)A Survey on Concurrent Processing of Graph Analytical Queries: Systems and AlgorithmsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.339393636:11(5508-5528)Online publication date: Nov-2024
https://doi.org/10.1109/TKDE.2024.3393936

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten