{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:07:19Z","timestamp":1775912839008,"version":"3.50.1"},"reference-count":79,"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":"Guangdong Talent Program","award":["2021QN02X826"],"award-info":[{"award-number":["2021QN02X826"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62102341"],"award-info":[{"award-number":["62102341"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Basic and Applied Basic Research Fund in Guangdong Province","award":["2022A1515010166"],"award-info":[{"award-number":["2022A1515010166"]}]},{"name":"Shenzhen Science and Technology Program","award":["ZDSYS20211021111415025"],"award-info":[{"award-number":["ZDSYS20211021111415025"]}]},{"name":"Shenzhen Science and Technology Program","award":["JCYJ20220530143602006"],"award-info":[{"award-number":["JCYJ20220530143602006"]}]},{"name":"Australian Research Council (ARC) Discovery Project","award":["DP230101534"],"award-info":[{"award-number":["DP230101534"]}]},{"name":"Australian Research Council Future Fellowship","award":["FT210100303"],"award-info":[{"award-number":["FT210100303"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>Spatial objects often come with textual information, such as Points of Interest (POIs) with their descriptions, which are referred to as geo-textual data. To retrieve such data, spatial keyword queries that take into account both spatial proximity and textual relevance have been extensively studied. Existing indexes designed for spatial keyword queries are mostly built based on the geo-textual data without considering the distribution of queries already received. However, previous studies have shown that utilizing the known query distribution can improve the index structure for future query processing. In this paper, we propose WISK, a learned index for spatial keyword queries, which self-adapts for optimizing querying costs given a query workload. One key challenge is how to utilize both structured spatial attributes and unstructured textual information during learning the index. We first divide the data objects into partitions, aiming to minimize the processing costs of the given query workload. We prove the NP-hardness of the partitioning problem and propose a machine learning model to find the optimal partitions. Then, to achieve more pruning power, we build a hierarchical structure based on the generated partitions in a bottom-up manner with a reinforcement learning-based approach. We conduct extensive experiments on real-world datasets and query workloads with various distributions, and the results show that WISK outperforms all competitors, achieving up to 8\u00d7 speedup in querying time with comparable storage overhead.<\/jats:p>","DOI":"10.1145\/3589332","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":21,"title":["WISK: A Workload-aware Learned Index for Spatial Keyword Queries"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-0107-4915","authenticated-orcid":false,"given":"Yufan","family":"Sheng","sequence":"first","affiliation":[{"name":"University of New South Wales, Sydney, NSW, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3519-7013","authenticated-orcid":false,"given":"Xin","family":"Cao","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, NSW, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5047-8593","authenticated-orcid":false,"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0984-1629","authenticated-orcid":false,"given":"Kaiqi","family":"Zhao","sequence":"additional","affiliation":[{"name":"University of Auckland, Auckland, New Zealand"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6501-9050","authenticated-orcid":false,"given":"Jianzhong","family":"Qi","sequence":"additional","affiliation":[{"name":"The University of Melbourne, Melbourne, VIC, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4430-6373","authenticated-orcid":false,"given":"Gao","family":"Cong","sequence":"additional","affiliation":[{"name":"Nanyang Technological Univesity, Singapore, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6572-2600","authenticated-orcid":false,"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, NSW, Australia"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170072"},{"key":"e_1_2_2_2_1","unstructured":"Rakesh Agrawal Heikki Mannila Ramakrishnan Srikant Hannu Toivonen A Inkeri Verkamo et al. 1996. Fast discovery of association rules. Vol. 12. AAAI\/MIT Press Menlo Park CA 307--328."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.07.063"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781118445112.stat07975"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375686"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989363"},{"key":"e_1_2_2_8_1","volume-title":"A sigmoidal approximation for chance-constrained nonlinear programs. arXiv preprint arXiv:2004.02402","author":"Cao Yankai","year":"2020","unstructured":"Yankai Cao and Victor M Zavala. 2020. A sigmoidal approximation for chance-constrained nonlinear programs. arXiv preprint arXiv:2004.02402 (2020)."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2013.2275077"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535569.2448955"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142505"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00661-w"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063641"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2016.7495640"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687666"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497474"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425880"},{"key":"e_1_2_2_19_1","volume-title":"Kim-Kwang Raymond Choo, and Hai Jin","author":"Ding Xiaofeng","year":"2022","unstructured":"Xiaofeng Ding, Yinting Zheng, Zuan Wang, Kim-Kwang Raymond Choo, and Hai Jin. 2022. A learned spatial textual index for efficient keyword queries. Journal of Intelligent Information Systems (2022), 1--25."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00035"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3377000.3377005"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588917"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/646366.689307"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/335191.335372"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDBM.2007.22"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983751"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517896"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622737.1622748"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/2020.emnlp-main.175"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15364-8_37"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_2_2_33_1","unstructured":"Stephen Cole Kleene. 1952. Introduction to metamathematics. (1952)."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2020.12.023"},{"key":"e_1_2_2_35_1","volume-title":"The Laplace distribution and generalizations: a revisit with applications to communications, economics, engineering, and finance","author":"Kotz Samuel","unstructured":"Samuel Kotz, Tomasz Kozubowski, and Krzysztof Podg\u00f3rski. 2001. The Laplace distribution and generalizations: a revisit with applications to communications, economics, engineering, and finance. Springer Science & Business Media."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457542"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389703"},{"key":"e_1_2_2_39_1","unstructured":"Timothy P Lillicrap Jonathan J Hunt Alexander Pritzel Nicolas Heess Tom Erez Yuval Tassa David Silver and Daan Wierstra. 2015. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196908"},{"key":"e_1_2_2_41_1","volume-title":"Aref","author":"Mahmood Ahmed R.","year":"2019","unstructured":"Ahmed R. Mahmood and Walid G. Aref. 2019. Scalable Processing of Spatial-Keyword Queries. Morgan & Claypool Publishers."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_2_43_1","volume-title":"Convergence of Q-learning: A simple proof","author":"Melo Francisco S","year":"2001","unstructured":"Francisco S Melo. 2001. Convergence of Q-learning: A simple proof. Institute Of Systems and Robotics, Tech. Rep (2001), 1--4."},{"key":"e_1_2_2_44_1","volume-title":"Nature","volume":"518","author":"Mnih Volodymyr","year":"2015","unstructured":"Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. 2015. Human-level control through deep reinforcement learning. Nature, Vol. 518, 7540 (2015), 529--533."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_2_46_1","volume-title":"On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems","author":"Ng Andrew","year":"2001","unstructured":"Andrew Ng, Michael Jordan, and Yair Weiss. 2001. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, Vol. 14 (2001)."},{"key":"e_1_2_2_47_1","volume-title":"Advances in Neural Information Processing Systems","volume":"32","author":"Paszke Adam","year":"2019","unstructured":"Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, Vol. 32."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340964.3340976"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014731"},{"key":"e_1_2_2_50_1","unstructured":"Martin L Puterman. 2014. Markov decision processes: discrete stochastic dynamic programming. (2014)."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407829"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22922-0_13"},{"key":"e_1_2_2_53_1","volume-title":"Online algorithms and stochastic approximations","author":"Saad David","unstructured":"David Saad. 1998. Online algorithms and stochastic approximations. Vol. 5. Cambridge Univ. Press Cambridge, UK, 6."},{"key":"e_1_2_2_54_1","volume-title":"Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.","author":"Silver David","year":"2016","unstructured":"David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. 2016. Mastering the game of Go with deep neural networks and tree search. Nature, Vol. 529, 7587 (2016), 484--489."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277741.1277857"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610515"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0263574799281520"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3469830.3470897"},{"key":"e_1_2_2_59_1","volume-title":"Encyclopedia of Machine Learning, Claude Sammut and Geoffrey I","author":"Toivonen Hannu","unstructured":"Hannu Toivonen. 2010. Frequent Itemset. In Encyclopedia of Machine Learning, Claude Sammut and Geoffrey I. Webb (Eds.). Springer, 418."},{"key":"e_1_2_2_60_1","volume-title":"Tree based discretization for continuous state space reinforcement learning. Aaai\/iaai","author":"Uther William TB","year":"1998","unstructured":"William TB Uther and Manuela M Veloso. 1998. Tree based discretization for continuous state space reinforcement learning. Aaai\/iaai, Vol. 98 (1998), 769--774."},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_13"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2019.00121"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461552"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735471.2735472"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735471.2735472"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00065"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992698"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.172"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457393"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526128"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313635"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00048"},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389770"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544884"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452419"},{"key":"e_1_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526155"},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/3469830.3470892"},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i1.16155"},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/1099554.1099584"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589332","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589332","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:14Z","timestamp":1750178774000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589332"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":79,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589332"],"URL":"https:\/\/doi.org\/10.1145\/3589332","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}