{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T03:27:47Z","timestamp":1762918067573},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,12,9]]},"abstract":"<jats:p>Hub labeling is widely used to improve the latency and throughput of Point-to-Point Shortest Distance (PPSD) queries in graph databases. However, constructing hub labeling, even via the state-of-the-art Pruned Landmark Labeling (PLL) algorithm is computationally intensive. PLL further has a sequential root order label dependency that makes it challenging to parallelize. Hence, the existing parallel approaches are often plagued by label size increase, poor scalability and inability to process large weighted graphs.<\/jats:p>\n          <jats:p>\n            In this paper, we develop novel algorithms that construct the minimal (guaranteed) Canonical Hub Labeling on shared and distributed-memory parallel systems in a scalable and efficient manner. Our key contribution, the PLaNT algorithm, provides an\n            <jats:italic>embarrassingly parallel<\/jats:italic>\n            approach for label construction that scales well beyond the limits of current practice. Our approach\n            <jats:italic>is the first<\/jats:italic>\n            to employ a collaborative label partitioning scheme across multiple nodes of a cluster, for completely in-memory labeling and parallel querying on massive graphs whose labels cannot fit on a single node.\n          <\/jats:p>\n          <jats:p>On a single node with 72-threads, our shared-memory algorithm is up to 47.4X faster than sequential PLL. While our labeling time is comparable to the state-of-the-art shared-memory paraPLL, our label size is 17% smaller on average.<\/jats:p>\n          <jats:p>PLaNT demonstrates superior parallel scalability. It can process significantly larger graphs and construct labeling orders of magnitude faster than the state-of-the-art distributed paraPLL. Compared to the best shared-memory parallel algorithm, it achieves up to 9.5X speedup on a 64 node cluster.<\/jats:p>","DOI":"10.14778\/3372716.3372722","type":"journal-article","created":{"date-parts":[[2020,1,6]],"date-time":"2020-01-06T20:19:37Z","timestamp":1578341977000},"page":"492-505","source":"Crossref","is-referenced-by-count":15,"title":["Planting trees for scalable and efficient canonical hub labeling"],"prefix":"10.14778","volume":"13","author":[{"given":"Kartik","family":"Lakhotia","sequence":"first","affiliation":[{"name":"University of Southern California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajgopal","family":"Kannan","sequence":"additional","affiliation":[{"name":"U.S Army Research Lab"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qing","family":"Dong","sequence":"additional","affiliation":[{"name":"University of Southern California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Viktor","family":"Prasanna","sequence":"additional","affiliation":[{"name":"University of Southern California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,1,6]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"The skitter as links dataset 2019. [Online; accessed 8-April-2019].  The skitter as links dataset 2019. [Online; accessed 8-April-2019]."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1007\/978-3-642-22006-7_58","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Abraham I.","year":"2011"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008623.2008645"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873665"},{"key":"e_1_2_1_6_1","volume-title":"VLDB'99","author":"Ailamaki A.","year":"1999"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973198.14"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568007"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247614"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"R. Albert H. Jeong and A.-L. Barab\u00e1si. Internet: Diameter of the world-wide web. nature 401(6749):130 1999.  R. Albert H. Jeong and A.-L. Barab\u00e1si. Internet: Diameter of the world-wide web. nature 401(6749):130 1999.","DOI":"10.1038\/43601"},{"key":"e_1_2_1_12_1","first-page":"62","volume-title":"International Symposium on Mathematical Foundations of Computer Science","author":"Babenko M.","year":"2015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1671970.1671976"},{"key":"e_1_2_1_15_1","volume-title":"IEEE","author":"Busato F.","year":"2018"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168846"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/s0097539702403098"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_22"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38527-8_4"},{"key":"e_1_2_1_20_1","volume-title":"9th dimacs implementation challenge-shortest paths","author":"Demetrescu C.","year":"2006"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087580"},{"key":"e_1_2_1_22_1","volume-title":"IEEE","author":"Dong Q.","year":"2018"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00025"},{"key":"e_1_2_1_24_1","unstructured":"D. Ferizovic and G. E. Blelloch. Parallel pruned landmark labeling for shortest path queries on unit-weight networks. 2015.  D. Ferizovic and G. E. Blelloch. Parallel pruned landmark labeling for shortest path queries on unit-weight networks. 2015."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2018.00015"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536346"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2791204.2791213"},{"key":"e_1_2_1_28_1","first-page":"17","volume-title":"Presented as part of the 10th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 12)","author":"Gonzalez J. E.","year":"2012"},{"key":"e_1_2_1_29_1","first-page":"599","volume-title":"11th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 14)","author":"Gonzalez J. E.","year":"2014"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755580"},{"key":"e_1_2_1_31_1","volume-title":"Workshop on Social Network Mining & Analysis, ACM KDD","author":"Hangal S.","year":"2010"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"P. E. Hart N. J. Nilsson and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics 4(2):100--107 1968.  P. E. Hart N. J. Nilsson and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics 4(2):100--107 1968.","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_33_1","volume-title":"Springer Science & Business Media","author":"Horvath S.","year":"2011"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732993"},{"key":"e_1_2_1_35_1","volume-title":"Wiley Online Library","author":"Junker B. H.","year":"2008"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_37_1","first-page":"427","volume-title":"2018 USENIX Annual Technical Conference (USENIX ATC 18)","author":"Lakhotia K.","year":"2018"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319877"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3164135.3164141"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626407002843"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_42_1","volume-title":"15th Workshop on Hot Topics in Operating Systems (HotOS {XV})","author":"McSherry F.","year":"2015"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"M. E. Newman. Scientific collaboration networks. ii. shortest paths weighted networks and centrality. Physical review E 64(1):016132 2001.  M. E. Newman. Scientific collaboration networks. ii. shortest paths weighted networks and centrality. Physical review E 64(1):016132 2001.","DOI":"10.1103\/PhysRevE.64.016132"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_2_1_45_1","first-page":"2","volume-title":"Proceedings of the 47th International Conference on Parallel Processing","author":"Qiu K."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti116"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2017.105"},{"key":"e_1_2_1_48_1","first-page":"135","volume-title":"ACM Sigplan Notices","author":"Shun J.","year":"2013"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.biosystems.2014.11.005"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592665.1592675"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.4018\/978-1-61350-053-8.ch009"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915220"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl467"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453934"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-016-0288-4"},{"key":"e_1_2_1_56_1","first-page":"301","volume-title":"12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16)","author":"Zhu X.","year":"2016"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3372716.3372722","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:59:47Z","timestamp":1672221587000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3372716.3372722"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,9]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,9]]}},"alternative-id":["10.14778\/3372716.3372722"],"URL":"https:\/\/doi.org\/10.14778\/3372716.3372722","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,12,9]]}}}