{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T02:33:09Z","timestamp":1769826789532,"version":"3.49.0"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,5,7]],"date-time":"2021-05-07T00:00:00Z","timestamp":1620345600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,5,7]],"date-time":"2021-05-07T00:00:00Z","timestamp":1620345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61702015"],"award-info":[{"award-number":["61702015"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["U1936104"],"award-info":[{"award-number":["U1936104"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61832001"],"award-info":[{"award-number":["61832001"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61729201"],"award-info":[{"award-number":["61729201"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2021,9]]},"DOI":"10.1007\/s00778-021-00669-2","type":"journal-article","created":{"date-parts":[[2021,5,7]],"date-time":"2021-05-07T21:04:51Z","timestamp":1620421491000},"page":"769-797","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["Memory-aware framework for fast and scalable second-order random walk over billion-edge natural graphs"],"prefix":"10.1007","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8559-2628","authenticated-orcid":false,"given":"Yingxia","family":"Shao","sequence":"first","affiliation":[]},{"given":"Shiyue","family":"Huang","sequence":"additional","affiliation":[]},{"given":"Yawen","family":"Li","sequence":"additional","affiliation":[]},{"given":"Xupeng","family":"Miao","sequence":"additional","affiliation":[]},{"given":"Bin","family":"Cui","sequence":"additional","affiliation":[]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,7]]},"reference":[{"key":"669_CR1","doi-asserted-by":"crossref","unstructured":"Boldi, P., Rosa, M.: Arc-community detection via triangular random walks. In: 2012 Eighth Latin American Web Congress, pp. 48\u201356 (2012)","DOI":"10.1109\/LA-WEB.2012.19"},{"issue":"3","key":"669_CR2","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s41019-019-0097-5","volume":"4","author":"S Bonner","year":"2019","unstructured":"Bonner, S., Kureshi, I., Brennan, J., Theodoropoulos, G., McGough, A.S., Obara, B.: Exploring the semantic content of unsupervised graph embeddings: an empirical study. Data Sci. Eng. 4(3), 269\u2013289 (2019)","journal-title":"Data Sci. Eng."},{"key":"669_CR3","doi-asserted-by":"crossref","unstructured":"Chaudhuri, S.: An overview of query optimization in relational systems. In: PODS, pp. 34\u201343 (1998)","DOI":"10.1145\/275487.275492"},{"key":"669_CR4","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.jpdc.2015.01.002","volume":"77","author":"A Das Sarma","year":"2015","unstructured":"Das Sarma, A., Molla, A.R., Pandurangan, G.: Efficient random walk sampling in distributed networks. J. Parallel Distrib. Comput. 77, 84\u201394 (2015)","journal-title":"J. Parallel Distrib. Comput."},{"issue":"2","key":"669_CR5","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s41019-019-0092-x","volume":"4","author":"VS Dave","year":"2019","unstructured":"Dave, V.S., Zhang, B., Chen, P.Y., Hasan, M.A.: Neural-brane: neural Bayesian personalized ranking for attributed network embedding. Data Sci. Eng. 4(2), 119\u2013131 (2019)","journal-title":"Data Sci. Eng."},{"issue":"1","key":"669_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0377-2217(87)90165-2","volume":"28","author":"K Dudzinski","year":"1987","unstructured":"Dudzinski, K., Walukiewicz, S.: Exact methods for the knapsack problem and its generalizations. Eur. J. Op. Res. 28(1), 3\u201321 (1987)","journal-title":"Eur. J. Op. Res."},{"key":"669_CR7","doi-asserted-by":"crossref","unstructured":"Feng, S., Cong, G., Khan, A., Li, X., Liu, Y., Chee, Y.M.: Inf2vec: Latent representation model for social influence embedding. In: ICDE, pp. 941\u2013952 (2018)","DOI":"10.1109\/ICDE.2018.00089"},{"key":"669_CR8","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198572237.001.0001","volume-title":"Probability and Random Processes","author":"G Grimmett","year":"2001","unstructured":"Grimmett, G., Stirzaker, D.: Probability and Random Processes, vol. 80. Oxford University Press, Oxford (2001)"},{"key":"669_CR9","doi-asserted-by":"crossref","unstructured":"Grover, A., Leskovec, J.: Node2vec: Scalable feature learning for networks. In: KDD, pp. 855\u2013864 (2016)","DOI":"10.1145\/2939672.2939754"},{"key":"669_CR10","unstructured":"Hamilton, W.L., Ying, R., Leskovec, J.: Inductive representation learning on large graphs. In: NIPS, pp. 1025\u20131035 (2017)"},{"key":"669_CR11","doi-asserted-by":"crossref","unstructured":"He, H., Singh, A.K.: Graphs-at-a-time: Query language and access methods for graph databases. In: SIGMOD, pp. 405\u2013418 (2008)","DOI":"10.1145\/1376616.1376660"},{"issue":"11","key":"669_CR12","doi-asserted-by":"publisher","first-page":"1111","DOI":"10.14778\/3402707.3402746","volume":"4","author":"H Herodotou","year":"2011","unstructured":"Herodotou, H., Babu, S.: Profiling, what-if analysis, and cost-based optimization of mapreduce programs. Proc. VLDB Endow. 4(11), 1111\u20131122 (2011)","journal-title":"Proc. VLDB Endow."},{"key":"669_CR13","doi-asserted-by":"crossref","unstructured":"Hu, X., Tao, Y., Chung, C.W.: Massive graph triangulation. In: SIGMOD, p. 325\u2013336 (2013)","DOI":"10.1145\/2463676.2463704"},{"key":"669_CR14","doi-asserted-by":"crossref","unstructured":"Huang, J., Venkatraman, K., Abadi, D.J.: Query optimization of distributed pattern matching. In: ICDE, pp. 64\u201375 (2014)","DOI":"10.1109\/ICDE.2014.6816640"},{"key":"669_CR15","doi-asserted-by":"crossref","unstructured":"Kyrola, A.: Drunkardmob: Billions of random walks on just a pc. In: RecSys, pp. 257\u2013264 (2013)","DOI":"10.1145\/2507157.2507173"},{"key":"669_CR16","volume-title":"Google\u2019s PageRank and Beyond: The Science of Search Engine Rankings, Chapter The Mathematics Guide","author":"AN Langville","year":"2011","unstructured":"Langville, A.N., Meyer, C.D.: Google\u2019s PageRank and Beyond: The Science of Search Engine Rankings, Chapter The Mathematics Guide. Princeton University Press, Princeton (2011)"},{"issue":"1\u20133","key":"669_CR17","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1016\/j.tcs.2008.07.017","volume":"407","author":"M Latapy","year":"2008","unstructured":"Latapy, M.: Main-memory triangle computations for very large (sparse (power-law)) graphs. Theor. Comput. Sci. 407(1\u20133), 458\u2013473 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"669_CR18","doi-asserted-by":"crossref","unstructured":"Li, R.H., Yu, J.X., Qin, L., Mao, R., Jin, T.: On random walk based graph sampling. In: ICDE, pp. 927\u2013938 (2015)","DOI":"10.1109\/ICDE.2015.7113345"},{"issue":"5","key":"669_CR19","doi-asserted-by":"publisher","first-page":"52101","DOI":"10.1007\/s11432-018-9511-1","volume":"62","author":"X Li","year":"2019","unstructured":"Li, X., Zhuang, Y., Fu, Y., He, X.: A trust-aware random walk model for return propensity estimation and consumer anomaly scoring in online shopping. Sci. China Inf. Sci. 62(5), 52101 (2019)","journal-title":"Sci. China Inf. Sci."},{"key":"669_CR20","doi-asserted-by":"crossref","unstructured":"Liben-Nowell, D., Kleinberg, J.: The link prediction problem for social networks. In: CIKM, pp. 556\u2013559 (2003)","DOI":"10.1145\/956863.956972"},{"key":"669_CR21","doi-asserted-by":"crossref","unstructured":"Lim, S., Ryu, S., Kwon, S., Jung, K., Lee, J.G.: Linkscan*: Overlapping community detection using the link-space transformation. In: ICDE, pp. 292\u2013303 (2014)","DOI":"10.1109\/ICDE.2014.6816659"},{"issue":"12","key":"669_CR22","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.14778\/2994509.2994519","volume":"9","author":"H Liu","year":"2016","unstructured":"Liu, H., Xiao, D., Didwania, P., Eltabakh, M.Y.: Exploiting soft and hard correlations in big data query optimization. Proc. VLDB Endow. 9(12), 1005\u20131016 (2016)","journal-title":"Proc. VLDB Endow."},{"key":"669_CR23","unstructured":"Lombardo, G., Poggi, A.: A scalable and distributed actor-based version of the node2vec algorithm. In: WOA (2019)"},{"key":"669_CR24","doi-asserted-by":"crossref","unstructured":"Malewicz, G., Austern, M.H., Bik, A.J., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G.: Pregel: A system for large-scale graph processing. In: SIGMOD, pp. 135\u2013146 (2010)","DOI":"10.1145\/1807167.1807184"},{"issue":"1","key":"669_CR25","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/366193.366228","volume":"6","author":"G Marsaglia","year":"1963","unstructured":"Marsaglia, G.: Generating discrete random variables in a computer. Commun. ACM 6(1), 37\u201338 (1963)","journal-title":"Commun. ACM"},{"key":"669_CR26","doi-asserted-by":"publisher","first-page":"4630","DOI":"10.1038\/ncomms5630","volume":"5","author":"R Martin","year":"2014","unstructured":"Martin, R., et al.: Memory in network flows and its effects on spreading dynamics and community detection. Nat. Commun. 5, 4630 (2014)","journal-title":"Nat. Commun."},{"issue":"6","key":"669_CR27","doi-asserted-by":"publisher","first-page":"678","DOI":"10.14778\/2735703.2735707","volume":"8","author":"A Nazi","year":"2015","unstructured":"Nazi, A., Zhou, Z., Thirumuruganathan, S., Zhang, N., Das, G.: Walk, not wait: faster sampling over online social networks. Proc. VLDB Endow. 8(6), 678\u2013689 (2015)","journal-title":"Proc. VLDB Endow."},{"issue":"10","key":"669_CR28","first-page":"1","volume":"63","author":"H Peng","year":"2020","unstructured":"Peng, H., Li, J., Yan, H., Gong, Q., Wang, S., Liu, L., Wang, L., Ren, X.: Dynamic network embedding via incremental skip-gram with negative sampling. Sci. China Inf. Sci. 63(10), 1\u201319 (2020)","journal-title":"Sci. China Inf. Sci."},{"key":"669_CR29","doi-asserted-by":"crossref","unstructured":"Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: Online learning of social representations. In: KDD, pp. 701\u2013710 (2014)","DOI":"10.1145\/2623330.2623732"},{"issue":"2","key":"669_CR30","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/0377-2217(95)00015-I","volume":"83","author":"D Pisinger","year":"1995","unstructured":"Pisinger, D.: A minimal algorithm for the multiple-choice knapsack problem. Eur. J. Op. Res. 83(2), 394\u2013410 (1995)","journal-title":"Eur. J. Op. Res."},{"issue":"3","key":"669_CR31","doi-asserted-by":"crossref","first-page":"528","DOI":"10.1111\/j.2517-6161.1985.tb01383.x","volume":"47","author":"AE Raftery","year":"1985","unstructured":"Raftery, A.E.: A model for high-order markov chains. J. R. Stat. Soc. Ser. B 47(3), 528\u2013539 (1985)","journal-title":"J. R. Stat. Soc. Ser. B"},{"key":"669_CR32","volume-title":"Monte Carlo Statistical Methods","author":"CP Robert","year":"2010","unstructured":"Robert, C.P., Casella, G.: Monte Carlo Statistical Methods. Springer Publishing Company, New York (2010)"},{"key":"669_CR33","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003","volume-title":"Iterative Methods for Sparse Linear Systems","author":"Y Saad","year":"2003","unstructured":"Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2003)","edition":"2"},{"issue":"23194","key":"669_CR34","first-page":"1","volume":"5","author":"V Salnikov","year":"2016","unstructured":"Salnikov, V., Schaub, M.T., Lambiotte, R.: Using higher-order markov models to reveal flow-based communities in networks. Sci. Rep. 5(23194), 1\u201313 (2016)","journal-title":"Sci. Rep."},{"key":"669_CR35","doi-asserted-by":"crossref","unstructured":"Sengupta, N., Bagchi, A., Ramanath, M., Bedathur, S.: Arrow: Approximating reachability using random walks over web-scale graphs. In: ICDE, pp. 470\u2013481 (2019)","DOI":"10.1109\/ICDE.2019.00049"},{"issue":"8","key":"669_CR36","doi-asserted-by":"publisher","first-page":"838","DOI":"10.14778\/2757807.2757809","volume":"8","author":"Y Shao","year":"2015","unstructured":"Shao, Y., Cui, B., Chen, L., Liu, M., Xie, X.: An efficient similarity search framework for simrank over large dynamic graphs. Proc. VLDB Endow. 8(8), 838\u2013849 (2015)","journal-title":"Proc. VLDB Endow."},{"key":"669_CR37","doi-asserted-by":"crossref","unstructured":"Shao, Y., Cui, B., Chen, L., Ma, L., Yao, J., Xu, N.: Parallel subgraph listing in a large-scale graph. In: SIGMOD, pp. 625\u2013636 (2014)","DOI":"10.1145\/2588555.2588557"},{"key":"669_CR38","doi-asserted-by":"crossref","unstructured":"Shao, Y., Huang, S., Miao, X., Cui, B., Chen, L.: Memory-aware framework for efficient second-order random walk on large graphs. In: SIGMOD, pp. 1797\u20131812 (2020)","DOI":"10.1145\/3318464.3380562"},{"issue":"3","key":"669_CR39","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1287\/opre.27.3.503","volume":"27","author":"P Sinha","year":"1979","unstructured":"Sinha, P., Zoltners, A.A.: The multiple-choice knapsack problem. Op. Res. 27(3), 503\u2013515 (1979)","journal-title":"Op. Res."},{"issue":"2","key":"669_CR40","doi-asserted-by":"publisher","first-page":"1626","DOI":"10.14778\/1687553.1687609","volume":"2","author":"A Thusoo","year":"2009","unstructured":"Thusoo, A., Sarma, J.S., Jain, N., Shao, Z., Chakka, P., Anthony, S., Liu, H., Wyckoff, P., Murthy, R.: Hive: a warehousing solution over a map-reduce framework. Proc. VLDB Endow. 2(2), 1626\u20131629 (2009)","journal-title":"Proc. VLDB Endow."},{"key":"669_CR41","doi-asserted-by":"crossref","unstructured":"Tsitsulin, A., Mottin, D., Karras, P., M\u00fcller, E.: Verse: Versatile graph embeddings from similarity measures. In: WWW, pp. 539\u2013548 (2018)","DOI":"10.1145\/3178876.3186120"},{"key":"669_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4018\/jdwm.2007070101","volume":"2007","author":"G Tsoumakas","year":"2007","unstructured":"Tsoumakas, G., Katakis, I.: Multi-label classification: an overview. Int. J. Data Warehous. Min. 2007, 1\u201313 (2007)","journal-title":"Int. J. Data Warehous. Min."},{"issue":"3","key":"669_CR43","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1145\/355744.355749","volume":"3","author":"AJ Walker","year":"1977","unstructured":"Walker, A.J.: An efficient method for generating discrete random variables with general distributions. ACM Trans. Math. Softw. 3(3), 253\u2013256 (1977)","journal-title":"ACM Trans. Math. Softw."},{"key":"669_CR44","unstructured":"Wang, R., Li, Y., Xie, H., Xu, Y., Lui, J.C.S.: Graphwalker: An i\/o-efficient and resource-friendly graph analytic system for fast and scalable random walks. In: ATC, pp. 559\u2013571 (2020)"},{"issue":"1","key":"669_CR45","doi-asserted-by":"publisher","first-page":"13","DOI":"10.14778\/3015270.3015272","volume":"10","author":"Y Wu","year":"2016","unstructured":"Wu, Y., Bian, Y., Zhang, X.: Remember where you came from: on the second-order random walk based proximity measures. Proc. VLDB Endow. 10(1), 13\u201324 (2016)","journal-title":"Proc. VLDB Endow."},{"key":"669_CR46","doi-asserted-by":"crossref","unstructured":"Xu, J., Wickramarathne, T., Chawla, N.V.: Representing higher-order dependencies in networks. In: Sci. Adv. (2016)","DOI":"10.1126\/sciadv.1600028"},{"key":"669_CR47","doi-asserted-by":"crossref","unstructured":"Yang, K., Zhang, M., Chen, K., Ma, X., Bai, Y., Jiang, Y.: Knightking: a fast distributed graph random walk engine. In: SOSP, pp. 524\u2013537 (2019)","DOI":"10.1145\/3341301.3359634"},{"issue":"6","key":"669_CR48","doi-asserted-by":"publisher","first-page":"1412","DOI":"10.1287\/opre.28.6.1412","volume":"28","author":"E Zemel","year":"1980","unstructured":"Zemel, E.: The linear multiple choice knapsack problem. Op. Res. 28(6), 1412\u20131423 (1980)","journal-title":"Op. Res."},{"issue":"1\u20132","key":"669_CR49","doi-asserted-by":"publisher","first-page":"340","DOI":"10.14778\/1920841.1920887","volume":"3","author":"P Zhao","year":"2010","unstructured":"Zhao, P., Han, J.: On graph query optimization in large networks. Proc. VLDB Endow. 3(1\u20132), 340\u2013351 (2010)","journal-title":"Proc. VLDB Endow."},{"key":"669_CR50","unstructured":"Zhou, D., Niu, S., Chen, S.: Efficient graph computation for node2vec. CoRR abs\/1805.00280 (2018)"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00669-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-021-00669-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00669-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T10:55:19Z","timestamp":1725015319000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-021-00669-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,7]]},"references-count":50,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["669"],"URL":"https:\/\/doi.org\/10.1007\/s00778-021-00669-2","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,7]]},"assertion":[{"value":"9 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 February 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 April 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}