{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T07:10:05Z","timestamp":1771917005778,"version":"3.50.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:p>\n            Instant spatial keyword queries return the results as soon as users type in some characters instead of a complete keyword, which allow users to query the geo-textual data in a\n            <jats:italic>type-as-you-search<\/jats:italic>\n            manner. However, the existing methods of instant spatial keyword queries suffer from several limitations. For example, the existing methods do not consider the typographical errors of input keywords, and cannot be applied to the road networks. To overcome these limitations, in this paper, we propose a new query type, i.e., instant error-tolerant spatial keyword queries on road networks. To answer the queries efficiently, we present a framework, termed as Task, which consists of index component, query component, and update component. In the index component, we design a novel index called reverse 2-hop label based trie, which seamlessly integrates spatial and textual information for each vertex of the road network. Based on our proposed index, we devise efficient algorithms to progressively return and update the query results in the query component and update component, respectively. Finally, we conduct extensive experiments on real-world road networks to evaluate the performance of our presented Task. Empirical results show that our proposed index and algorithms are up to 1--2 orders of magnitude faster than the baseline.\n          <\/jats:p>","DOI":"10.14778\/3603581.3603584","type":"journal-article","created":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T19:06:48Z","timestamp":1691521608000},"page":"2418-2430","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Task: An Efficient Framework for Instant Error-Tolerant Spatial Keyword Queries on Road Networks"],"prefix":"10.14778","volume":"16","author":[{"given":"Chengyang","family":"Luo","sequence":"first","affiliation":[{"name":"Zhejiang University"}]},{"given":"Qing","family":"Liu","sequence":"additional","affiliation":[{"name":"Zhejiang University"}]},{"given":"Yunjun","family":"Gao","sequence":"additional","affiliation":[{"name":"Zhejiang University"}]},{"given":"Lu","family":"Chen","sequence":"additional","affiliation":[{"name":"Zhejiang University"}]},{"given":"Ziheng","family":"Wei","sequence":"additional","affiliation":[{"name":"Huawei Cloud Computing Technologies Co., Ltd"}]},{"given":"Congcong","family":"Ge","sequence":"additional","affiliation":[{"name":"Huawei Cloud Computing Technologies Co., Ltd"}]}],"member":"320","published-online":{"date-parts":[[2023,8,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2894140"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Takuya Akiba Yoichi Iwata and Yuichi Yoshida. 2013. Fast Exact Shortest-path Distance Queries on Large Networks by Pruned Landmark Labeling. In SIGMOD. 349--360.  Takuya Akiba Yoichi Iwata and Yuichi Yoshida. 2013. Fast Exact Shortest-path Distance Queries on Large Networks by Pruned Landmark Labeling. In SIGMOD. 349--360.","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_3_1","volume-title":"Type Less","author":"Bast Hannah","unstructured":"Hannah Bast and Ingmar Weber . 2006. Type Less , Find More : Fast Autocompletion Search with A Succinct Index. In SIGIR. 364--371. Hannah Bast and Ingmar Weber. 2006. Type Less, Find More: Fast Autocompletion Search with A Succinct Index. In SIGIR. 364--371."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.117"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535569.2448955"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Lei Chen Jianliang Xu Xin Lin Christian S. Jensen and Haibo Hu. 2016. Answering Why-not Spatial Keyword Top-k Queries via Keyword Adaption. In ICDE. 697--708.  Lei Chen Jianliang Xu Xin Lin Christian S. Jensen and Haibo Hu. 2016. Answering Why-not Spatial Keyword Top- k Queries via Keyword Adaption. In ICDE. 697--708.","DOI":"10.1109\/ICDE.2016.7498282"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00661-w"},{"key":"e_1_2_1_8_1","volume-title":"Minhao Jiang, Eric Lo, and Pengfei Zhang.","author":"Chen Zitong","year":"2021","unstructured":"Zitong Chen , Ada Wai-Chee Fu , Minhao Jiang, Eric Lo, and Pengfei Zhang. 2021 . P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators. In SIGMOD. 313--325. Zitong Chen, Ada Wai-Chee Fu, Minhao Jiang, Eric Lo, and Pengfei Zhang. 2021. P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators. In SIGMOD. 313--325."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2975998"},{"key":"e_1_2_1_10_1","unstructured":"Edith Cohen Eran Halperin Haim Kaplan and Uri Zwick. 2002. Reachability and Distance Queries via 2-Hop Labels. In SODA. 937--946.  Edith Cohen Eran Halperin Haim Kaplan and Uri Zwick. 2002. Reachability and Distance Queries via 2-Hop Labels. In SODA. 937--946."},{"key":"e_1_2_1_11_1","volume-title":"Jensen","author":"Cong Gao","year":"2016","unstructured":"Gao Cong and Christian S . Jensen . 2016 . Querying Geo-textual Data: Spatial Keyword Queries and Beyond. In SIGMOD. 2207--2212. Gao Cong and Christian S. Jensen. 2016. Querying Geo-textual Data: Spatial Keyword Queries and Beyond. In SIGMOD. 2207--2212."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687666"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2977797.2977808"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00627-4"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536346"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2365820"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2015.2477837"},{"key":"e_1_2_1_18_1","first-page":"181","article-title":"An Efficient Algorithm for Location-aware Query Autocompletion. IEICE","volume":"1","author":"Hu Sheng","year":"2018","unstructured":"Sheng Hu , Chuan Xiao , and Yoshiharu Ishikawa . 2018 . An Efficient Algorithm for Location-aware Query Autocompletion. IEICE Trans. Inf. Syst. 101-D , 1 (2018), 181 -- 192 . Sheng Hu, Chuan Xiao, and Yoshiharu Ishikawa. 2018. An Efficient Algorithm for Location-aware Query Autocompletion. IEICE Trans. Inf. Syst. 101-D, 1 (2018), 181--192.","journal-title":"Trans. Inf. Syst. 101-D"},{"key":"e_1_2_1_19_1","first-page":"17","article-title":"Location-based Instant Search","volume":"6809","author":"Ji Shengyue","year":"2011","unstructured":"Shengyue Ji and Chen Li . 2011 . Location-based Instant Search . In SSDBM , Vol. 6809. 17 -- 36 . Shengyue Ji and Chen Li. 2011. Location-based Instant Search. In SSDBM, Vol. 6809. 17--36.","journal-title":"SSDBM"},{"key":"e_1_2_1_20_1","volume-title":"Ada Wai-Chee Fu, and Raymond Chi-Wing Wong","author":"Jiang Minhao","year":"2015","unstructured":"Minhao Jiang , Ada Wai-Chee Fu, and Raymond Chi-Wing Wong . 2015 . Exact Top-k Nearest Keyword Search in Large Networks. In SIGMOD. 393--404. Minhao Jiang, Ada Wai-Chee Fu, and Raymond Chi-Wing Wong. 2015. Exact Top-k Nearest Keyword Search in Large Networks. In SIGMOD. 393--404."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.148"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Guoliang Li Shengyue Ji Chen Li and Jianhua Feng. 2009. Efficient Type-ahead Search on Relational Data: A TASTIER approach. In SIGMOD. 695--706.  Guoliang Li Shengyue Ji Chen Li and Jianhua Feng. 2009. Efficient Type-ahead Search on Relational Data: A TASTIER approach. In SIGMOD. 695--706.","DOI":"10.1145\/1559845.1559918"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0218-x"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1145\/3186728.3164141","article-title":"An Experimental Study on Hub Labeling based Shortest Path Algorithms","volume":"11","author":"Li Ye","year":"2017","unstructured":"Ye Li , Leong Hou U, Man Lung Yiu , and Ngai Meng Kou . 2017 . An Experimental Study on Hub Labeling based Shortest Path Algorithms . Proc. VLDB Endow. 11 , 4 (2017), 445 -- 457 . Ye Li, Leong Hou U, Man Lung Yiu, and Ngai Meng Kou. 2017. An Experimental Study on Hub Labeling based Shortest Path Algorithms. Proc. VLDB Endow. 11, 4 (2017), 445--457.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_25_1","unstructured":"Zijian Li Lei Chen and Yue Wang. 2019. G*-Tree: An Efficient Spatial Index on Road Networks. In ICDE. 268--279.  Zijian Li Lei Chen and Yue Wang. 2019. G*-Tree: An Efficient Spatial Index on Road Networks. In ICDE. 268--279."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.149"},{"key":"e_1_2_1_27_1","article-title":"Efficient Algorithms and Cost Models for Reverse Spatial-keyword k-nearest Neighbor Search","volume":"39","author":"Lu Ying","year":"2014","unstructured":"Ying Lu , Jiaheng Lu , Gao Cong , Wei Wu , and Cyrus Shahabi . 2014 . Efficient Algorithms and Cost Models for Reverse Spatial-keyword k-nearest Neighbor Search . ACM Trans. Database Syst. 39 , 2 (2014), 13:1--13:46. Ying Lu, Jiaheng Lu, Gao Cong, Wei Wu, and Cyrus Shahabi. 2014. Efficient Algorithms and Cost Models for Reverse Spatial-keyword k-nearest Neighbor Search. ACM Trans. Database Syst. 39, 2 (2014), 13:1--13:46.","journal-title":"ACM Trans. Database Syst."},{"key":"e_1_2_1_28_1","volume-title":"Task: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks. https:\/\/github.com\/ZJU-DAILY\/TASK\/blob\/main\/paper\/PVLDB2023.pdf","author":"Luo Chengyang","year":"2023","unstructured":"Chengyang Luo , Qing Liu , Yunjun Gao , Lu Chen , Ziheng Wei , and Congcong Ge . 2023 . Task: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks. https:\/\/github.com\/ZJU-DAILY\/TASK\/blob\/main\/paper\/PVLDB2023.pdf Chengyang Luo, Qing Liu, Yunjun Gao, Lu Chen, Ziheng Wei, and Congcong Ge. 2023. Task: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks. https:\/\/github.com\/ZJU-DAILY\/TASK\/blob\/main\/paper\/PVLDB2023.pdf"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Dian Ouyang Lu Qin Lijun Chang Xuemin Lin Ying Zhang and Qing Zhu. 2018. When Hierarchy Meets 2-Hop-labeling: Efficient Shortest Distance Queries on Road Networks. In SIGMOD. 709--724.  Dian Ouyang Lu Qin Lijun Chang Xuemin Lin Ying Zhang and Qing Zhu. 2018. When Hierarchy Meets 2-Hop-labeling: Efficient Shortest Distance Queries on Road Networks. In SIGMOD. 709--724.","DOI":"10.1145\/3183713.3196913"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536217"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00595-4"},{"key":"e_1_2_1_32_1","volume-title":"Rocha-Junior and Kjetil N\u00f8rv\u00e5g","author":"Jo\u00e3o","year":"2012","unstructured":"Jo\u00e3o B. Rocha-Junior and Kjetil N\u00f8rv\u00e5g . 2012 . Top-k Spatial Keyword Queries on Road Networks. In EDBT. 168--179. Jo\u00e3o B. Rocha-Junior and Kjetil N\u00f8rv\u00e5g. 2012. Top-k Spatial Keyword Queries on Road Networks. In EDBT. 168--179."},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Senjuti Basu Roy and Kaushik Chakrabarti. 2011. Location-aware Type Ahead Search on Spatial Databases: Semantics and Efficiency. In SIGMOD. 361--372.  Senjuti Basu Roy and Kaushik Chakrabarti. 2011. Location-aware Type Ahead Search on Spatial Databases: Semantics and Efficiency. In SIGMOD. 361--372.","DOI":"10.1145\/1989323.1989362"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Jin Wang and Chunbin Lin. 2020. Fast Error-tolerant Location-aware Query Autocompletion. In ICDE. 1998--2001.  Jin Wang and Chunbin Lin. 2020. Fast Error-tolerant Location-aware Query Autocompletion. In ICDE. 1998--2001.","DOI":"10.1109\/ICDE48307.2020.00223"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0453-2"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536339"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00583-8"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Junye Yang Yong Zhang Xiaofang Zhou Jin Wang Huiqi Hu and Chunxiao Xing. 2019. A Hierarchical Framework for Top-k Location-aware Error-tolerant Keyword Search. In ICDE. 986--997.  Junye Yang Yong Zhang Xiaofang Zhou Jin Wang Huiqi Hu and Chunxiao Xing. 2019. A Hierarchical Framework for Top- k Location-aware Error-tolerant Keyword Search. In ICDE. 986--997.","DOI":"10.1109\/ICDE.2019.00092"},{"key":"e_1_2_1_39_1","volume-title":"Muhammad Aamir Cheema, and Xiaoyang Wang","author":"Zhang Chengyuan","year":"2014","unstructured":"Chengyuan Zhang , Ying Zhang , Wenjie Zhang , Xuemin Lin , Muhammad Aamir Cheema, and Xiaoyang Wang . 2014 . Diversified Spatial Keyword Search on Road Networks. In EDBT. 367--378. Chengyuan Zhang, Ying Zhang, Wenjie Zhang, Xuemin Lin, Muhammad Aamir Cheema, and Xiaoyang Wang. 2014. Diversified Spatial Keyword Search on Road Networks. In EDBT. 367--378."},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Mengxuan Zhang Lei Li Wen Hua Rui Mao Pingfu Chao and Xiaofang Zhou. 2021. Dynamic Hub Labeling for Road Networks. In ICDE. 336--347.  Mengxuan Zhang Lei Li Wen Hua Rui Mao Pingfu Chao and Xiaofang Zhou. 2021. Dynamic Hub Labeling for Road Networks. In ICDE. 336--347.","DOI":"10.1109\/ICDE51399.2021.00036"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Mengxuan Zhang Lei Li Wen Hua and Xiaofang Zhou. 2021. Efficient 2-Hop Labeling Maintenance in Dynamic Small-world Networks. In ICDE. 133--144.  Mengxuan Zhang Lei Li Wen Hua and Xiaofang Zhou. 2021. Efficient 2-Hop Labeling Maintenance in Dynamic Small-world Networks. In ICDE. 133--144.","DOI":"10.1109\/ICDE51399.2021.00019"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476267"},{"key":"e_1_2_1_43_1","article-title":"Towards Efficient Framework for Time-aware Spatial Keyword Queries on Road Networks","volume":"36","author":"Zhao Jingwen","year":"2018","unstructured":"Jingwen Zhao , Yunjun Gao , Gang Chen , and Rui Chen . 2018 . Towards Efficient Framework for Time-aware Spatial Keyword Queries on Road Networks . ACM Trans. Inf. Syst. 36 , 3 (2018), 24:1--24:48. Jingwen Zhao, Yunjun Gao, Gang Chen, and Rui Chen. 2018. Towards Efficient Framework for Time-aware Spatial Keyword Queries on Road Networks. ACM Trans. Inf. Syst. 36, 3 (2018), 24:1--24:48.","journal-title":"ACM Trans. Inf. Syst."},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Jingwen Zhao Yunjun Gao Gang Chen and Rui Chen. 2018. Why-not Questions on Top-k Geo-social Keyword Queries in Road Networks. In ICDE. 965--976.  Jingwen Zhao Yunjun Gao Gang Chen and Rui Chen. 2018. Why-not Questions on Top- k Geo-social Keyword Queries in Road Networks. In ICDE. 965--976.","DOI":"10.1109\/ICDE.2018.00091"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Jingwen Zhao Yunjun Gao Gang Chen Christian S. Jensen Rui Chen and Deng Cai. 2017. Reverse Top-k Geo-social Keyword Queries in Road Networks. In ICDE. 387--398.  Jingwen Zhao Yunjun Gao Gang Chen Christian S. Jensen Rui Chen and Deng Cai. 2017. Reverse Top- k Geo-social Keyword Queries in Road Networks. In ICDE. 387--398.","DOI":"10.1109\/ICDE.2017.97"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2879819"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Bolong Zheng Kai Zheng Xiaokui Xiao Han Su Hongzhi Yin Xiaofang Zhou and GuoHui Li. 2016. Keyword-aware Continuous kNN Query on Road Networks. In ICDE. 871--882.  Bolong Zheng Kai Zheng Xiaokui Xiao Han Su Hongzhi Yin Xiaofang Zhou and GuoHui Li. 2016. Keyword-aware Continuous k NN Query on Road Networks. In ICDE. 871--882.","DOI":"10.1109\/ICDE.2016.7498297"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Ruicheng Zhong Ju Fan Guoliang Li Kian-Lee Tan and Lizhu Zhou. 2012. Location-aware Instant Search. In CIKM. 385--394.  Ruicheng Zhong Ju Fan Guoliang Li Kian-Lee Tan and Lizhu Zhou. 2012. Location-aware Instant Search. In CIKM. 385--394.","DOI":"10.1145\/2396761.2396812"},{"key":"e_1_2_1_49_1","article-title":"BEVA: An Efficient Query Processing Algorithm for Errortolerant Autocompletion","volume":"41","author":"Zhou Xiaoling","year":"2016","unstructured":"Xiaoling Zhou , Jianbin Qin , Chuan Xiao , Wei Wang , Xuemin Lin , and Yoshiharu Ishikawa . 2016 . BEVA: An Efficient Query Processing Algorithm for Errortolerant Autocompletion . ACM Trans. Database Syst. 41 , 1 (2016), 5:1--5:44. Xiaoling Zhou, Jianbin Qin, Chuan Xiao, Wei Wang, Xuemin Lin, and Yoshiharu Ishikawa. 2016. BEVA: An Efficient Query Processing Algorithm for Errortolerant Autocompletion. ACM Trans. Database Syst. 41, 1 (2016), 5:1--5:44.","journal-title":"ACM Trans. Database Syst."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3603581.3603584","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T19:08:48Z","timestamp":1691521728000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3603581.3603584"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6]]},"references-count":49,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["10.14778\/3603581.3603584"],"URL":"https:\/\/doi.org\/10.14778\/3603581.3603584","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,6]]},"assertion":[{"value":"2023-08-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}