{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T05:08:45Z","timestamp":1755839325176,"version":"3.41.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,2,20]],"date-time":"2023-02-20T00:00:00Z","timestamp":1676851200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong RGC","award":["HKBU 12200021, 22200320, and 12201318"],"award-info":[{"award-number":["HKBU 12200021, 22200320, and 12201318"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>\n            The COVID-19 pandemic has caused the society lockdowns and a large number of deaths in many countries. Potential transmission cluster discovery is to find all suspected users with infections, which is greatly needed to fast discover virus transmission chains so as to prevent an outbreak of COVID-19 as early as possible. In this article, we study the problem of potential transmission cluster discovery based on the spatio-temporal logs. Given a query of patient user\n            <jats:italic>q<\/jats:italic>\n            and a timestamp of confirmed infection\n            <jats:italic>\n              t\n              <jats:sub>q<\/jats:sub>\n            <\/jats:italic>\n            , the problem is to find all potential infected users who have close social contacts to user\n            <jats:italic>q<\/jats:italic>\n            before time\n            <jats:italic>\n              t\n              <jats:sub>q<\/jats:sub>\n            <\/jats:italic>\n            . We motivate and formulate the potential transmission cluster model, equipped with a detailed analysis of transmission cluster property and particular model usability. To identify potential clusters, one straightforward method is to compute all close contacts on-the-fly, which is simple but inefficient caused by scanning spatio-temporal logs many times. To accelerate the efficiency, we propose two indexing algorithms by constructing a multigraph index and an advanced BCG-index. Leveraging two well-designed techniques of spatio-temporal compression and graph partition on bipartite contact graphs, our BCG-index approach achieves a good balance of index construction and online query processing to fast discover potential transmission cluster. We theoretically analyze and compare the algorithm complexity of three proposed approaches. Extensive experiments on real-world check-in datasets and COVID-19 confirmed cases in the United States validate the effectiveness and efficiency of our potential transmission cluster model and algorithms.\n          <\/jats:p>","DOI":"10.1145\/3538492","type":"journal-article","created":{"date-parts":[[2022,5,24]],"date-time":"2022-05-24T13:23:44Z","timestamp":1653398624000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Novel Graph Indexing Approach for Uncovering Potential COVID-19 Transmission Clusters"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0655-8809","authenticated-orcid":false,"given":"Xuliang","family":"Zhu","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University, Kowloon Tong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3650-0301","authenticated-orcid":false,"given":"Xin","family":"Huang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Kowloon Tong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7465-9153","authenticated-orcid":false,"given":"Longxu","family":"Sun","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Kowloon Tong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8669-9064","authenticated-orcid":false,"given":"Jiming","family":"Liu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Kowloon Tong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,2,20]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467197"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064032"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-018-0627-5"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3161602"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3412865"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403358"},{"key":"e_1_3_2_9_2","first-page":"138","volume-title":"Proceedings of the International Workshop on Mobility Analytics for Spatio-Temporal and Social Data","author":"Francalanci Chiara","year":"2017","unstructured":"Chiara Francalanci, Barbara Pernici, and Gabriele Scalia. 2017. Exploratory spatio-temporal queries in evolving information. In Proceedings of the International Workshop on Mobility Analytics for Spatio-Temporal and Social Data. 138\u2013156."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401429"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1011"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3412863"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1201\/9781420057140"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3412860"},{"key":"e_1_3_2_16_2","volume-title":"Graph Theory","author":"Harary Frank","year":"1991","unstructured":"Frank Harary. 1991. Graph Theory. Addison-Wesley."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976700.56"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3412864"},{"key":"e_1_3_2_20_2","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved June 2022 from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2019.2960835"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/ab8e5e"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.chaos.2021.111294"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403122"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.eclinm.2021.100929"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.eclinm.2020.100354"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415489"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014080"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-293-5"},{"key":"e_1_3_2_30_2","unstructured":"Lukas M. Marti Michael P. Dal Santo and Ronald Keryuan Huang. 2016. Modeling significant locations. US Patent 9 267 805."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10676-020-09572-w"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.visinf.2017.01.007"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330937"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2002.994706"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-73216-5_26"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3459237"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3408066.3408086"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467157"},{"key":"e_1_3_2_39_2","first-page":"431","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Tao Yufei","year":"2001","unstructured":"Yufei Tao and Dimitris Papadias. 2001. The mv3r-tree: A spatio-temporal access method for timestamp and interval queries. In Proceedings of the International Conference on Very Large Data Bases. 431\u2013440."},{"key":"e_1_3_2_40_2","unstructured":"The New York Times. 2021. Coronavirus (Covid-19) Data in the United States. Retrieved June 2022 from https:\/\/github.com\/nytimes\/covid-19-data."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/MCI.2020.3019873"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.3003750"},{"key":"e_1_3_2_43_2","unstructured":"WHO. 2020. Retrieved June 2022 from https:\/\/www.who.int\/docs\/default-source\/coronaviruse\/situation-reports\/20200306-sitrep-46-covid-19.pdf?sfvrsn=96b04adf_4."},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.171"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363809"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498236"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2690299"},{"key":"e_1_3_2_48_2","first-page":"643","volume-title":"Proceedings of the IEEE International Conference on Data Engineering","author":"Xiong Xiaopeng","year":"2005","unstructured":"Xiaopeng Xiong, Mohamed F. Mokbel, and Walid G. Aref. 2005. Sea-cnn: Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases. In Proceedings of the IEEE International Conference on Data Engineering. 643\u2013654."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/S2213-2600(20)30076-X"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313635"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnca.2015.05.010"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/2814575"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2017.95"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00572-x"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3538492","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3538492","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:14Z","timestamp":1750186814000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3538492"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,20]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3538492"],"URL":"https:\/\/doi.org\/10.1145\/3538492","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2023,2,20]]},"assertion":[{"value":"2021-06-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-08","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}