{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T09:02:59Z","timestamp":1775638979478,"version":"3.50.1"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>Location-based services for moving objects are close to our lives. For example, ride-sharing services, micro-mobility services, navigation and traffic management, delivery services, and autonomous driving are all based on moving objects. The efficient management of such moving objects is therefore getting more and more important. The main challenge is the handling of a large number of location-update queries with scan queries. To address this challenge, we propose a novel in-memory grid indexing system, Waffle, for moving objects. Waffle divides a geographical space into fixed-sized cells. For efficient query processing, Waffle forms chunks, each of which consists of neighboring cells. Such a Waffle index is defined by several configuration knobs. A knob configuration has a significant impact on the performance of Waffle, and an appropriate configuration may change as objects continuously move. Therefore, we propose an online configuration tuning system, WaffleMaker, that automatically determines not only knob values but also when to change knob values, as a part of Waffle. Using a configuration determined by WaffleMaker, Waffle rebuilds the current index without blocking user queries based on a concurrency control scheme. Through extensive experiments, we show that Waffle performed better than the existing methods, and WaffleMaker automatically tuned configuration knob values.<\/jats:p>","DOI":"10.14778\/3551793.3551800","type":"journal-article","created":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T22:25:03Z","timestamp":1664490303000},"page":"2375-2388","source":"Crossref","is-referenced-by-count":13,"title":["Waffle"],"prefix":"10.14778","volume":"15","author":[{"given":"Dalsu","family":"Choi","sequence":"first","affiliation":[{"name":"Korea University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hyunsik","family":"Yoon","sequence":"additional","affiliation":[{"name":"Korea University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hyubjin","family":"Lee","sequence":"additional","affiliation":[{"name":"Korea University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yon Dohn","family":"Chung","sequence":"additional","affiliation":[{"name":"Korea University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,9,29]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21--26 June 2014 (JMLR Workshop and Conference Proceedings)","volume":"32","author":"Agarwal Alekh","unstructured":"Alekh Agarwal , Daniel J. Hsu , Satyen Kale , John Langford , Lihong Li , and Robert E. Schapire . 2014. Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits . In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21--26 June 2014 (JMLR Workshop and Conference Proceedings) , Vol. 32 . JMLR.org, 1638--1646. http:\/\/proceedings.mlr.press\/v32\/agarwalb14.html Alekh Agarwal, Daniel J. Hsu, Satyen Kale, John Langford, Lihong Li, and Robert E. Schapire. 2014. Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21--26 June 2014 (JMLR Workshop and Conference Proceedings), Vol. 32. JMLR.org, 1638--1646. http:\/\/proceedings.mlr.press\/v32\/agarwalb14.html"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064029"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450992"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457404"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324957"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425880"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02982-0_14"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687767"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.6086\/N1H99379#mbr=9qwesvg4,9qxq6f81"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"e_1_2_1_11_1","volume-title":"Courville","author":"Goodfellow Ian J.","year":"2016","unstructured":"Ian J. Goodfellow , Yoshua Bengio , and Aaron C . Courville . 2016 . Deep Learning. MIT Press . http:\/\/www.deeplearningbook.org\/ Ian J. Goodfellow, Yoshua Bengio, and Aaron C. Courville. 2016. Deep Learning. MIT Press. http:\/\/www.deeplearningbook.org\/"},{"key":"e_1_2_1_12_1","volume-title":"The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data. CoRR abs\/2103.04541","author":"Gu Tu","year":"2021","unstructured":"Tu Gu , Kaiyu Feng , Gao Cong , Cheng Long , Zheng Wang , and Sheng Wang . 2021. The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data. CoRR abs\/2103.04541 ( 2021 ). arXiv:2103.04541 https:\/\/arxiv.org\/abs\/2103.04541 Tu Gu, Kaiyu Feng, Gao Cong, Cheng Long, Zheng Wang, and Sheng Wang. 2021. The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data. CoRR abs\/2103.04541 (2021). arXiv:2103.04541 https:\/\/arxiv.org\/abs\/2103.04541"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2020.01.009"},{"key":"e_1_2_1_14_1","volume-title":"Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018","author":"Kannan Sampath","year":"2018","unstructured":"Sampath Kannan , Jamie Morgenstern , Aaron Roth , Bo Waggoner , and Zhiwei Steven Wu . 2018 . A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem . In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 , NeurIPS 2018, December 3--8, 2018, Montr\u00e9al, Canada. 2231--2241. https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/2cfd4560539f887a5e420412b370b361-Abstract.html Sampath Kannan, Jamie Morgenstern, Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu. 2018. A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3--8, 2018, Montr\u00e9al, Canada. 2231--2241. https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/2cfd4560539f887a5e420412b370b361-Abstract.html"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_16_1","article-title":"Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting","volume":"21","author":"Krishnamurthy Akshay","year":"2020","unstructured":"Akshay Krishnamurthy , John Langford , Aleksandrs Slivkins , and Chicheng Zhang . 2020 . Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting . The Journal of Machine Learning Research 21 (2020), 137:1--137:45. http:\/\/jmlr.org\/papers\/v21\/19-650.html Akshay Krishnamurthy, John Langford, Aleksandrs Slivkins, and Chicheng Zhang. 2020. Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting. The Journal of Machine Learning Research 21 (2020), 137:1--137:45. http:\/\/jmlr.org\/papers\/v21\/19-650.html","journal-title":"The Journal of Machine Learning Research"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3412106"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems","author":"Langford John","year":"2007","unstructured":"John Langford and Tong Zhang . 2007 . The Epoch-Greedy Algorithm for Multi-armed Bandits with Side Information. In Advances in Neural Information Processing Systems 20 , Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems , Vancouver, British Columbia, Canada, December 3--6 , 2007. Curran Associates, Inc., 817--824. https:\/\/proceedings.neurips.cc\/paper\/2007\/hash\/4b04a686b0ad13dce35fa99fa4161c65-Abstract.html John Langford and Tong Zhang. 2007. The Epoch-Greedy Algorithm for Multi-armed Bandits with Side Information. In Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 3--6, 2007. Curran Associates, Inc., 817--824. https:\/\/proceedings.neurips.cc\/paper\/2007\/hash\/4b04a686b0ad13dce35fa99fa4161c65-Abstract.html"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352129"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772758"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389703"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-020-01674-8"},{"key":"e_1_2_1_23_1","volume-title":"4th International Conference on Learning Representations, ICLR","author":"Lillicrap Timothy P.","year":"2016","unstructured":"Timothy P. Lillicrap , Jonathan J. Hunt , Alexander Pritzel , Nicolas Heess , Tom Erez , Yuval Tassa , David Silver , and Daan Wierstra . 2016. Continuous Control with Deep Reinforcement Learning . In 4th International Conference on Learning Representations, ICLR 2016 , San Juan, Puerto Rico , May 2--4, 2016, Conference Track Proceedings . http:\/\/arxiv.org\/abs\/1509.02971 Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. 2016. Continuous Control with Deep Reinforcement Learning. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2--4, 2016, Conference Track Proceedings. http:\/\/arxiv.org\/abs\/1509.02971"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2010, Chia Laguna Resort, Sardinia, Italy, May 13--15, 2010 (JMLR Proceedings)","volume":"9","author":"Lu Tyler","year":"2010","unstructured":"Tyler Lu , D\u00e1vid P\u00e1l , and Martin Pal . 2010 . Contextual Multi-Armed Bandits . In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2010, Chia Laguna Resort, Sardinia, Italy, May 13--15, 2010 (JMLR Proceedings) , Vol. 9 . JMLR.org, 485--492. http:\/\/proceedings.mlr.press\/v9\/lu10a.html Tyler Lu, D\u00e1vid P\u00e1l, and Martin Pal. 2010. Contextual Multi-Armed Bandits. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2010, Chia Laguna Resort, Sardinia, Italy, May 13--15, 2010 (JMLR Proceedings), Vol. 9. JMLR.org, 485--492. http:\/\/proceedings.mlr.press\/v9\/lu10a.html"},{"key":"e_1_2_1_25_1","volume-title":"Efficient Contextual Bandits with Continuous Actions. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Majzoubi Maryam","year":"2020","unstructured":"Maryam Majzoubi , Chicheng Zhang , Rajan Chari , Akshay Krishnamurthy , John Langford , and Aleksandrs Slivkins . 2020 . Efficient Contextual Bandits with Continuous Actions. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 , NeurIPS 2020, December 6--12, 2020, virtual. https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/033cc385728c51d97360020ed57776f0-Abstract.html Maryam Majzoubi, Chicheng Zhang, Rajan Chari, Akshay Krishnamurthy, John Langford, and Aleksandrs Slivkins. 2020. Efficient Contextual Bandits with Continuous Actions. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6--12, 2020, virtual. https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/033cc385728c51d97360020ed57776f0-Abstract.html"},{"key":"e_1_2_1_26_1","volume-title":"Riedmiller","author":"Mnih Volodymyr","year":"2013","unstructured":"Volodymyr Mnih , Koray Kavukcuoglu , David Silver , Alex Graves , Ioannis Antonoglou , Daan Wierstra , and Martin A . Riedmiller . 2013 . Playing Atari with Deep Reinforcement Learning. CoRR abs\/1312.5602 (2013). arXiv:1312.5602 http:\/\/arxiv.org\/abs\/1312.5602 Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. 2013. Playing Atari with Deep Reinforcement Learning. CoRR abs\/1312.5602 (2013). arXiv:1312.5602 http:\/\/arxiv.org\/abs\/1312.5602"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00058"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407829"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2014.7"},{"key":"e_1_2_1_31_1","volume-title":"Introduction to Probability and Statistics for Engineers and Scientists","author":"Ross Sheldon M","unstructured":"Sheldon M Ross . 2020. Introduction to Probability and Statistics for Engineers and Scientists . Academic Press . Sheldon M Ross. 2020. Introduction to Probability and Statistics for Engineers and Scientists. Academic Press."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3410566.3410603"},{"key":"e_1_2_1_33_1","volume-title":"Prioritized Experience Replay. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2--4, 2016, Conference Track Proceedings. http:\/\/arxiv.org\/abs\/1511","author":"Schaul Tom","year":"2016","unstructured":"Tom Schaul , John Quan , Ioannis Antonoglou , and David Silver . 2016 . Prioritized Experience Replay. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2--4, 2016, Conference Track Proceedings. http:\/\/arxiv.org\/abs\/1511 .05952 Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. 2016. Prioritized Experience Replay. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2--4, 2016, Conference Track Proceedings. http:\/\/arxiv.org\/abs\/1511.05952"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22922-0_12"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653805"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213842"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature16961"},{"key":"e_1_2_1_38_1","volume-title":"Contextual Bandits with Similarity Information. In COLT 2011 - The 24th Annual Conference on Learning Theory, June 9--11, 2011, Budapest, Hungary (JMLR Proceedings)","volume":"19","author":"Slivkins Aleksandrs","year":"2011","unstructured":"Aleksandrs Slivkins . 2011 . Contextual Bandits with Similarity Information. In COLT 2011 - The 24th Annual Conference on Learning Theory, June 9--11, 2011, Budapest, Hungary (JMLR Proceedings) , Vol. 19 . JMLR.org, 679--702. http:\/\/proceedings.mlr.press\/v19\/slivkins11a\/slivkins11a.pdf Aleksandrs Slivkins. 2011. Contextual Bandits with Similarity Information. In COLT 2011 - The 24th Annual Conference on Learning Theory, June 9--11, 2011, Budapest, Hungary (JMLR Proceedings), Vol. 19. JMLR.org, 679--702. http:\/\/proceedings.mlr.press\/v19\/slivkins11a\/slivkins11a.pdf"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339503"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450984"},{"key":"e_1_2_1_41_1","volume-title":"On the Theory of the Brownian Motion. Physical review 36, 5","author":"Uhlenbeck George E","year":"1930","unstructured":"George E Uhlenbeck and Leonard S Ornstein . 1930. On the Theory of the Brownian Motion. Physical review 36, 5 ( 1930 ), 823. George E Uhlenbeck and Leonard S Ornstein. 1930. On the Theory of the Brownian Motion. Physical review 36, 5 (1930), 823."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2019.00121"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2016.46"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300085"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3469830.3470892"},{"key":"e_1_2_1_46_1","first-page":"1","article-title":"Processing Continuous k-nearest Neighbor Queries in Location-dependent Application","volume":"6","author":"Zhang Wei","year":"2006","unstructured":"Wei Zhang , Jianzhong Li , and Haiwei Pan . 2006 . Processing Continuous k-nearest Neighbor Queries in Location-dependent Application . International Journal of Computer Science and Network Security 6 , 3 (2006), 1 -- 9 . Wei Zhang, Jianzhong Li, and Haiwei Pan. 2006. Processing Continuous k-nearest Neighbor Queries in Location-dependent Application. International Journal of Computer Science and Network Security 6, 3 (2006), 1--9.","journal-title":"International Journal of Computer Science and Network Security"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457291"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3551793.3551800","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:24:02Z","timestamp":1672223042000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3551793.3551800"}},"subtitle":["in-memory grid index for moving objects with reinforcement learning-based configuration tuning system"],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":47,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.14778\/3551793.3551800"],"URL":"https:\/\/doi.org\/10.14778\/3551793.3551800","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,7]]}}}