{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:12:21Z","timestamp":1750219941673,"version":"3.41.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF of China for Joint Fund Project","award":["U1936218; GD-NSF 2019B1515130001, and 2023A1515030273"],"award-info":[{"award-number":["U1936218; GD-NSF 2019B1515130001, and 2023A1515030273"]}]},{"name":"HKRGC","award":["12201119, 12201518, 12232716, 12202221, and C2004-21GF"],"award-info":[{"award-number":["12201119, 12201518, 12232716, 12202221, and C2004-21GF"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62072132, and 92067104"],"award-info":[{"award-number":["62072132, and 92067104"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>This paper studies privacy preserving graph pattern query services in a cloud computing paradigm. In such a paradigm, data owner stores the large data graph to a powerful cloud hosted by a service provider (SP) and users send their queries to SP for query processing. However, as SP may not always be trusted, the sensitive information of users' queries, importantly, the query structures, should be protected. In this paper, we study how to outsource the localized graph pattern queries (LGPQs) on the SP side with privacy preservation. LGPQs include a rich set of semantics, such as subgraph homomorphism, subgraph isomorphism, and strong simulation, for which each matched graph pattern is located in a subgraph called ball that have a restriction on its size. To provide privacy preserving query service for LGPQs, this paper proposes the first framework, called Prilo, that enables users to privately obtain the query results. To further optimize Prilo, we propose Prilo* that comprises the first bloom filter for trees in the trust execution environment (TEE) on SP, a query-oblivious twiglet-based technique for pruning non-answers, and a secure retrieval scheme of balls that enables user to obtain query results early. We conduct detailed experiments on real world datasets to show that Prilo* is on average 4x faster than the baseline, and meanwhile, preserves query privacy.<\/jats:p>","DOI":"10.1145\/3589274","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-27","source":"Crossref","is-referenced-by-count":2,"title":["A Framework for Privacy Preserving Localized Graph Pattern Query Processing"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8999-0623","authenticated-orcid":false,"given":"Lyu","family":"Xu","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8381-336X","authenticated-orcid":false,"given":"Byron","family":"Choi","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6358-2333","authenticated-orcid":false,"given":"Yun","family":"Peng","sequence":"additional","affiliation":[{"name":"Guangzhou University, Guangzhou, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9404-5848","authenticated-orcid":false,"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1957-8016","authenticated-orcid":false,"given":"Sourav","family":"S Bhowmick","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Alex Averbuch, Altan Birler, Peter Boncz, M\u00e1rton B\u00far, Orri Erling, Andrey Gubichev, Vlad Haprian, Moritz Kaufmann, et al.","author":"Angles Renzo","year":"2020","unstructured":"Renzo Angles, J\u00e1nos Benjamin Antal, Alex Averbuch, Altan Birler, Peter Boncz, M\u00e1rton B\u00far, Orri Erling, Andrey Gubichev, Vlad Haprian, Moritz Kaufmann, et al. 2020. The LDBC social network benchmark. arXiv (2020)."},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI)","volume":"16","author":"Arnautov Sergei","year":"2016","unstructured":"Sergei Arnautov, Bohdan Trach, Franz Gregor, Thomas Knauth, Andre Martin, Christian Priebe, Joshua Lind, Divya Muthukumaran, Dan O'keeffe, Mark Stillwell, et al. 2016. SCONE: Secure linux containers with intel SGX. In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI), Vol. 16. 689--703."},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST). 173--190","author":"Bailleu Maurice","year":"2019","unstructured":"Maurice Bailleu, J\u00f6rg Thalheim, Pramod Bhatotia, Christof Fetzer, Michio Honda, and Kapil Vaswani. 2019. SPEICHER: Securing LSM-based key-value stores using shielded execution. In Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST). 173--190."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407854"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature09204"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88313-5_13"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00558-9"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2457317.2457338"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2011.84"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882956"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_2_12_1","volume-title":"Intel SGX explained. Cryptology ePrint Archive","author":"Costan Victor","year":"2016","unstructured":"Victor Costan and Srinivas Devadas. 2016. Intel SGX explained. Cryptology ePrint Archive (2016)."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00029"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380585"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2399292"},{"volume-title":"IEEE 31st International Conference on Data Engineering (ICDE). 339--350","author":"Fan Zhe","key":"e_1_2_2_16_1","unstructured":"Zhe Fan, Byron Choi, Jianliang Xu, and Sourav S. Bhowmick. 2015b. Asymmetric structure-preserving subgraph queries for large graphs. In IEEE 31st International Conference on Data Engineering (ICDE). 339--350."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91452-7_20"},{"key":"e_1_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Craig Gentry and Dan Boneh. 2009. A fully homomorphic encryption scheme.","DOI":"10.1145\/1536414.1536440"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213871"},{"key":"e_1_2_2_21_1","volume-title":"Privacy and efficiency guaranteed social subgraph matching. The VLDB Journal (VLDBJ)","author":"Huang Kai","year":"2021","unstructured":"Kai Huang, Haibo Hu, Shuigeng Zhou, Jihong Guan, Qingqing Ye, and Xiaofang Zhou. 2021. Privacy and efficiency guaranteed social subgraph matching. The VLDB Journal (VLDBJ) (2021), 1--22."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2020.02.031"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457265"},{"key":"e_1_2_2_24_1","volume-title":"Fast subgraph query processing and subgraph matching via static and dynamic equivalences. The VLDB Journal (VLDBJ)","author":"Kim Hyunjoon","year":"2022","unstructured":"Hyunjoon Kim, Yunyoung Choi, Kunsoo Park, Xuemin Lin, Seok-Hee Hong, and Wook-Shin Han. 2022. Fast subgraph query processing and subgraph matching via static and dynamic equivalences. The VLDB Journal (VLDBJ) (2022), 1--26."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2017.07.005"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809985"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.4161\/auto.6398"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3321705.3329803"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448946"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00065"},{"key":"e_1_2_2_31_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452839"},{"key":"e_1_2_2_33_1","unstructured":"Yehuda Lindell and Jonathan Katz. 2014. Introduction to modern cryptography."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113273"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.117"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2014.6848003"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528937"},{"key":"e_1_2_2_38_1","unstructured":"Robin Milner. 1989. Communication and concurrency."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2015.30"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/157485.164556"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48910-X_16"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196902"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2836(03)00239-0"},{"volume-title":"IEEE 24th International Conference on Data Engineering (ICDE). 963--972","author":"Tian Yuanyuan","key":"e_1_2_2_44_1","unstructured":"Yuanyuan Tian and Jignesh M. Patel. 2008. Tale: A tool for approximate large graph matching. In IEEE 24th International Conference on Data Engineering (ICDE). 963--972."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554826"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2022.3201392"},{"key":"e_1_2_2_48_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TKDE.2022.3185079","article-title":"Privacy-preserving analytics on decentralized social graphs: The case of eigendecomposition","volume":"1","author":"Wang Songlei","year":"2022","unstructured":"Songlei Wang, Yifeng Zheng, Xiaohua Jia, and Xun Yi. 2022c. Privacy-preserving analytics on decentralized social graphs: The case of eigendecomposition. IEEE Transactions on Knowledge and Data Engineering (TKDE) 1 (2022), 1--15.","journal-title":"IEEE Transactions on Knowledge and Data Engineering (TKDE)"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00062"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476283"},{"key":"e_1_2_2_51_1","unstructured":"Lyu Xu Byron Choi Yun Peng Jianliang Xu and Sourav S Bhowmick. 2023. Technical report: A framework for privacy preserving localized graph pattern query processing. https:\/\/www.comp.hkbu.edu.hk\/%7Ecslyuxu\/prilo2023tr.pdf."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00133"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.07.082"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2022.3152395"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457308"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687727"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589274","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589274","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:54Z","timestamp":1750182534000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589274"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":57,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589274"],"URL":"https:\/\/doi.org\/10.1145\/3589274","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}