{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:33:11Z","timestamp":1768109591674,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":78,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T00:00:00Z","timestamp":1654819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"EPSRC Centre for Doctoral Training in Pervasive Parallelism","award":["EP\/L01503X\/1"],"award-info":[{"award-number":["EP\/L01503X\/1"]}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["652976"],"award-info":[{"award-number":["652976"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Royal Society Wolfson Research Merit Award","award":["WRM\/R1\/180014"],"award-info":[{"award-number":["WRM\/R1\/180014"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62002236"],"award-info":[{"award-number":["62002236"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,10]]},"DOI":"10.1145\/3514221.3517862","type":"proceedings-article","created":{"date-parts":[[2022,6,12]],"date-time":"2022-06-12T02:33:49Z","timestamp":1655001229000},"page":"1726-1740","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["A Hierarchical Contraction Scheme for Querying Big Graphs"],"prefix":"10.1145","author":[{"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[{"name":"University of Edinburgh, Shenzhen Institute of Computing Sciences, & Beihang University, Edinburgh, United Kingdom"}]},{"given":"Yuanhao","family":"Li","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}]},{"given":"Muyang","family":"Liu","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}]},{"given":"Can","family":"Lu","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Computing Sciences, Shenzhen, China"}]}],"member":"320","published-online":{"date-parts":[[2022,6,11]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"2006. Traffic. http:\/\/www.dis.uniroma1.it\/challenge9\/download.shtml."},{"key":"e_1_3_2_2_2_1","unstructured":"2006. UKWeb. http:\/\/law.di.unimi.it\/webdata\/uk-union-2006-06--2007-05\/."},{"key":"e_1_3_2_2_3_1","unstructured":"2012. Friendster. https:\/\/snap.stanford.edu\/data\/com-Friendster.html."},{"key":"e_1_3_2_2_4_1","unstructured":"2020 a. GRAPE. https:\/\/github.com\/alibaba\/libgrape-lite.git."},{"key":"e_1_3_2_2_5_1","unstructured":"2020 b. GraphScope. https:\/\/graphscope.io\/."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204035"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Renzo Angles Marcelo Arenas Pablo Barcel\u00f3 Peter A. Boncz George H. L. Fletcher Claudio Gutierrez Tobias Lindaaker Marcus Paradies Stefan Plantikow Juan F. Sequeda Oskar van Rest and Hannes Voigt. 2018. G-CORE: A Core for Future Graph Query Languages. In SIGMOD. 1421--1432.","DOI":"10.1145\/3183713.3190654"},{"key":"e_1_3_2_2_8_1","first-page":"564","article-title":"Objectrank: Authority-based keyword search in databases","volume":"4","author":"Balmin Andrey","year":"2004","unstructured":"Andrey Balmin, Vagelis Hristidis, and Yannis Papakonstantinou. 2004. Objectrank: Authority-based keyword search in databases. In VLDB, Vol. 4. 564--575.","journal-title":"VLDB"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"crossref","unstructured":"Pablo Barcel\u00f3 Baeza. 2013. Querying graph databases. In PODS. 175--188.","DOI":"10.1145\/2463664.2465216"},{"key":"e_1_3_2_2_10_1","volume-title":"Engineering label-constrained shortest-path algorithms","author":"Barrett Chris","unstructured":"Chris Barrett, Keith Bisset, Martin Holzer, Goran Konjevod, Madhav Marathe, and Dorothea Wagner. 2008. Engineering label-constrained shortest-path algorithms. In AAIM. Springer, 27--37."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798337716"},{"key":"e_1_3_2_2_12_1","volume-title":"A survey on PageRank computing. Internet mathematics","author":"Berkhin Pavel","year":"2005","unstructured":"Pavel Berkhin. 2005. A survey on PageRank computing. Internet mathematics, Vol. 2, 1 (2005), 73--120."},{"key":"e_1_3_2_2_13_1","volume-title":"AAAI Workshop on Agent Organizations: Theory and Practice.","author":"Berry Nina","year":"2004","unstructured":"Nina Berry, Teresa Ko, Tim Moy, Julienne Smrcka, Jessica Turnley, and Ben Wu. 2004. Emergent clique formation in terrorist recruitment. In AAAI Workshop on Agent Organizations: Theory and Practice."},{"key":"e_1_3_2_2_14_1","volume-title":"Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations. CoRR","author":"Besta Maciej","year":"2018","unstructured":"Maciej Besta and Torsten Hoefler. 2018. Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations. CoRR, Vol. abs\/1806.01799 (2018)."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Paolo Boldi and Sebastiano Vigna. 2004. The WebGraph Framework I: Compression techniques. In WWW. 595--602.","DOI":"10.1145\/988672.988752"},{"key":"e_1_3_2_2_16_1","volume-title":"Modern graph theory","author":"Bollob\u00e1s B\u00e9la","unstructured":"B\u00e9la Bollob\u00e1s. 2013. Modern graph theory. Vol. 184. Springer Science & Business Media."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Yang Cao and Wenfei Fan. 2016. An Effective Syntax for Bounded Relational Queries. In SIGMOD.","DOI":"10.1145\/2882903.2882942"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Yang Cao Wenfei Fan and Ruizhe Huang. 2015. Making Pattern Queries Bounded in Big Graphs. In ICDE.","DOI":"10.1109\/ICDE.2015.7113281"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Yang Cao Wenfei Fan Yanghao Wang and Ke Yi. 2020. Querying Shared Data with Security Heterogeneity. In SIGMOD. 575--585.","DOI":"10.1145\/3318464.3389784"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3058748"},{"key":"e_1_3_2_2_22_1","volume-title":"Nxgraph: An efficient graph processing system on a single machine","author":"Chi Yuze","year":"2016","unstructured":"Yuze Chi, Guohao Dai, Yu Wang, Guangyu Sun, Guoliang Li, and Huazhong Yang. 2016. Nxgraph: An efficient graph processing system on a single machine. In ICDE. IEEE, 409--420."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"crossref","unstructured":"Sara Cohen. 2016. Data management for social networking. In PODS. 165--177.","DOI":"10.1145\/2902251.2902306"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_3_2_2_25_1","volume-title":"Introduction to algorithms","author":"Cormen Thomas H","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2009. Introduction to algorithms. MIT press."},{"key":"e_1_3_2_2_26_1","unstructured":"Wenfei Fan Floris Geerts Yang Cao and Ting Deng. 2015a. Querying Big Data by Accessing Small Data. In PODS."},{"key":"e_1_3_2_2_27_1","unstructured":"Wenfei Fan Chunming Hu and Chao Tian. 2017. Incremental graph computations: Doable and undoable. In SIGMOD."},{"key":"e_1_3_2_2_28_1","unstructured":"Wenfei Fan Jianzhong Li Xin Wang and Yinghui Wu. 2012. Query preserving graph compression. In SIGMOD. 157--168."},{"key":"e_1_3_2_2_29_1","unstructured":"Wenfei Fan Yuanhao Li Muyang Liu and Can Lu. 2021. Making Graphs Compact by Lossless Contraction. (2021). SIGMOD."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732983"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824048"},{"key":"e_1_3_2_2_32_1","unstructured":"Wenfei Fan Yinghui Wu and Jingbo Xu. 2016. Functional dependencies for graphs. In SIGMOD."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3282488"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190657"},{"key":"e_1_3_2_2_35_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey Michael","unstructured":"Michael Garey and David Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness .W. H. Freeman and Company."},{"key":"e_1_3_2_2_36_1","volume-title":"Powergraph: Distributed graph-parallel computation on natural graphs. In OSDI. 17--30.","author":"Gonzalez Joseph E","year":"2012","unstructured":"Joseph E Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. Powergraph: Distributed graph-parallel computation on natural graphs. In OSDI. 17--30."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.009"},{"key":"e_1_3_2_2_38_1","unstructured":"William L Hamilton Rex Ying and Jure Leskovec. 2017. Inductive representation learning on large graphs. (2017)."},{"key":"e_1_3_2_2_39_1","unstructured":"Wook-Shin Han Jinsoo Lee and Jeong-Hoon Lee. 2013. Turbo$_rm iso$: Towards ultrafast and robust subgraph isomorphism search in large graph databases. In SIGMOD."},{"key":"e_1_3_2_2_40_1","volume-title":"Fast connected-component labeling. Pattern recognition","author":"He Lifeng","year":"2009","unstructured":"Lifeng He, Yuyan Chao, Kenji Suzuki, and Kesheng Wu. 2009. Fast connected-component labeling. Pattern recognition, Vol. 42, 9 (2009), 1977--1987."},{"key":"e_1_3_2_2_41_1","first-page":"945","article-title":"Partially labeled classification with Markov random walks","volume":"14","author":"Tommi Jaakkola Martin Szummer","year":"2002","unstructured":"Martin Szummer Tommi Jaakkola and Martin Szummer. 2002. Partially labeled classification with Markov random walks. NIPS, Vol. 14 (2002), 945--952.","journal-title":"NIPS"},{"key":"e_1_3_2_2_42_1","unstructured":"Ruoming Jin Yang Xiang Ning Ruan and Haixun Wang. 2008. Efficiently answering reachability queries on very large directed graphs. In SIGMOD. 595--608."},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"crossref","unstructured":"U Kang Mary McGlohon Leman Akoglu and Christos Faloutsos. 2010. Patterns on the connected components of terabyte-scale graphs. In ICDM. 875--880.","DOI":"10.1109\/ICDM.2010.121"},{"key":"e_1_3_2_2_44_1","volume-title":"Semi-supervised classification with graph convolutional networks. ICLR","author":"Kipf Thomas N","year":"2016","unstructured":"Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. ICLR (2016)."},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00286-3"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"crossref","unstructured":"Walter Kropatsch. 1996. Building irregular pyramids by dual-graph contraction. In Vision Image and Signal Processing.","DOI":"10.1049\/ip-vis:19952115"},{"key":"e_1_3_2_2_47_1","unstructured":"Aapo Kyrola Guy E. Blelloch and Carlos Guestrin. 2012. GraphChi: Large-Scale Graph Computation on Just a PC. In OSDI. 31--46."},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"crossref","unstructured":"Theodoros Lappas Kun Liu and Evimaria Terzi. 2009. Finding a team of experts in social networks. In KDD.","DOI":"10.1145\/1557019.1557074"},{"key":"e_1_3_2_2_49_1","volume-title":"GraSS: Graph structure summarization","author":"LeFevre Kristen","unstructured":"Kristen LeFevre and Evimaria Terzi. 2010. GraSS: Graph structure summarization. In SDM. SIAM, 454--465."},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.3233\/SW-140134"},{"key":"e_1_3_2_2_51_1","volume-title":"Bioinformatics","volume":"21","author":"Leser Ulf","year":"2005","unstructured":"Ulf Leser. 2005. A query language for biological networks. Bioinformatics, Vol. 21, suppl_2 (2005), ii33--ii39."},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"crossref","unstructured":"Jure Leskovec Jon M. Kleinberg and Christos Faloutsos. 2005. Graphs over time: Densification laws shrinking diameters and possible explanations. In SIGKDD.","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_3_2_2_53_1","unstructured":"Kingsly Leung and Christopher Leckie. 2005. Unsupervised anomaly detection in network intrusion detection using clusters. In ACSW."},{"key":"e_1_3_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186727"},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_3_2_2_56_1","volume-title":"Mosaic: Processing a trillion-edge graph on a single machine. In EuroSys. 527--543.","author":"Maass Steffen","year":"2017","unstructured":"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 EuroSys. 527--543."},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"crossref","unstructured":"Antonio Maccioni and Daniel J Abadi. 2016. Scalable pattern matching over compressed graphs via dedensification. In SIGKDD. 1755--1764.","DOI":"10.1145\/2939672.2939856"},{"key":"e_1_3_2_2_58_1","unstructured":"Wim Martens and Tina Trautner. 2018. Evaluation and enumeration problems for regular path queries. In ICDT. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_2_59_1","unstructured":"Julian McAuley and Jure Leskovec. 2012. Learning to Discover Social Circles in Ego Networks. In NIPS."},{"key":"e_1_3_2_2_60_1","unstructured":"Frank McSherry Michael Isard and Derek Gordon Murray. 2015. Scalability! But at what COST?. In HotOS."},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1561\/106.00000003"},{"key":"e_1_3_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-011-0224-z"},{"key":"e_1_3_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"key":"e_1_3_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0046"},{"key":"e_1_3_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00079-8"},{"key":"e_1_3_2_2_67_1","volume-title":"Program analysis via graph reachability. Information and software technology","author":"Reps Thomas","year":"1998","unstructured":"Thomas Reps. 1998. Program analysis via graph reachability. Information and software technology, Vol. 40, 11--12 (1998), 701--726."},{"key":"e_1_3_2_2_68_1","volume-title":"SoQL: A language for querying and creating data in social networks","author":"Ronen Royi","unstructured":"Royi Ronen and Oded Shmueli. 2009. SoQL: A language for querying and creating data in social networks. In ICDE. IEEE, 1595--1602."},{"key":"e_1_3_2_2_70_1","doi-asserted-by":"crossref","unstructured":"Stergios Stergiou Dipen Rughwani and Kostas Tsioutsiouliklis. 2018. Shortcutting label propagation for distributed connected components. In WSDM. 540--546.","DOI":"10.1145\/3159652.3159696"},{"key":"e_1_3_2_2_71_1","series-title":"SIAM journal on computing","volume-title":"Depth-first search and linear graph algorithms","author":"Tarjan Robert","year":"1972","unstructured":"Robert Tarjan. 1972. Depth-first search and linear graph algorithms. SIAM journal on computing, Vol. 1, 2 (1972), 146--160."},{"key":"e_1_3_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"},{"key":"e_1_3_2_2_73_1","doi-asserted-by":"crossref","unstructured":"Yuanyuan Tian Richard A Hankins and Jignesh M Patel. 2008. Efficient aggregation for graph summarization. In SIGMOD. 567--580.","DOI":"10.1145\/1376616.1376675"},{"key":"e_1_3_2_2_74_1","volume-title":"George HL Fletcher, and Yuichi Yoshida","author":"Valstar Lucien DJ","year":"2017","unstructured":"Lucien DJ Valstar, George HL Fletcher, and Yuichi Yoshida. 2017. Landmark indexing for evaluation of label-constrained reachability queries. In SIGMOD. 345--358."},{"key":"e_1_3_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/2960414.2960421"},{"key":"e_1_3_2_2_76_1","unstructured":"W3C Recommendation. 2008. SPARQL Query Language for RDF. sl https:\/\/www.w3.org\/TR\/rdf-sparql-query\/."},{"key":"e_1_3_2_2_77_1","doi-asserted-by":"crossref","unstructured":"Da Yan James Cheng Yi Lu and Wilfred Ng. 2015. Effective techniques for message reduction and load balancing in distributed graph computation. In WWW. 1307--1317.","DOI":"10.1145\/2736277.2741096"},{"key":"e_1_3_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.11.712"},{"key":"e_1_3_2_2_79_1","doi-asserted-by":"crossref","unstructured":"Quan Yuan Gao Cong and Aixin Sun. 2014. Graph-based point-of-interest recommendation with geographical and temporal influences. In CIKM. 659--668.","DOI":"10.1145\/2661829.2661983"},{"key":"e_1_3_2_2_80_1","volume-title":"Gemini: A computation-centric distributed graph processing system. In OSDI. 301--316.","author":"Zhu Xiaowei","year":"2016","unstructured":"Xiaowei Zhu, Wenguang Chen, Weimin Zheng, and Xiaosong Ma. 2016. Gemini: A computation-centric distributed graph processing system. In OSDI. 301--316."}],"event":{"name":"SIGMOD\/PODS '22: International Conference on Management of Data","location":"Philadelphia PA USA","acronym":"SIGMOD\/PODS '22","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 2022 International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514221.3517862","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3514221.3517862","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:36Z","timestamp":1750188636000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514221.3517862"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,10]]},"references-count":78,"alternative-id":["10.1145\/3514221.3517862","10.1145\/3514221"],"URL":"https:\/\/doi.org\/10.1145\/3514221.3517862","relation":{},"subject":[],"published":{"date-parts":[[2022,6,10]]},"assertion":[{"value":"2022-06-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}