{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T11:11:52Z","timestamp":1781781112340,"version":"3.54.5"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p>\n            Although several spatial indexes achieve fast query processing, they are ineffective for highly dynamic data sets because of costly updates. On the other hand, simple structures that enable efficient updates are slow for spatial queries. In this paper, we propose\n            <jats:italic>Waffle<\/jats:italic>\n            , a workload-aware, query-sensitive spatial index, that effectively accommodates both update- and query-intensive workloads. Waffle combines concepts of the space and data partitioning frameworks, and constitutes a complete indexing solution. In addition to query processing algorithms, it includes: (i) a novel bulk loading method that guarantees optimal disk page utilization on static data, (ii) algorithms for dynamic updates that guarantee zero overlapping of nodes, and (iii) a maintenance mechanism that adjusts the tradeoff between query and update speed, based on the workload and query distribution. An extensive experimental evaluation confirms the superiority of Waffle against state of the art space and data partitioning indexes on update and query efficiency.\n          <\/jats:p>","DOI":"10.14778\/3574245.3574253","type":"journal-article","created":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T23:14:12Z","timestamp":1677021252000},"page":"670-683","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Waffle"],"prefix":"10.14778","volume":"16","author":[{"given":"Moin Hussain","family":"Moti","sequence":"first","affiliation":[{"name":"HKUST, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Panagiotis","family":"Simatis","sequence":"additional","affiliation":[{"name":"HKUST, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dimitris","family":"Papadias","sequence":"additional","affiliation":[{"name":"HKUST, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,2,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363792"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007608"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559929"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/356789.356797"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170075"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1999.754960"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/s10707-008-0052-5","article-title":"Update-efficient indexing of moving objects in road networks","volume":"13","author":"Chen Jidong","year":"2006","unstructured":"Jidong Chen and Xiaofeng Meng . 2006 . Update-efficient indexing of moving objects in road networks . GeoInformatica 13 (2006), 397 -- 424 . Jidong Chen and Xiaofeng Meng. 2006. Update-efficient indexing of moving objects in road networks. GeoInformatica 13 (2006), 397--424.","journal-title":"GeoInformatica"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454229"},{"key":"e_1_2_1_11_1","volume-title":"M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. In VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases","author":"Ciaccia Paolo","year":"1997","unstructured":"Paolo Ciaccia , Marco Patella , and Pavel Zezula . 1997 . M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. In VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases , August 25-29, 1997, Athens, Greece, Matthias Jarke, Michael J. Carey, Klaus R. Dittrich, Frederick H. Lochovsky, Pericles Loucopoulos, and Manfred A. Jeusfeld (Eds.). Morgan Kaufmann , 426--435. http:\/\/www.vldb.org\/conf\/1997\/P426.PDF Paolo Ciaccia, Marco Patella, and Pavel Zezula. 1997. M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. In VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece, Matthias Jarke, Michael J. Carey, Klaus R. Dittrich, Frederick H. Lochovsky, Pericles Loucopoulos, and Manfred A. Jeusfeld (Eds.). Morgan Kaufmann, 426--435. http:\/\/www.vldb.org\/conf\/1997\/P426.PDF"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335414"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425880"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40235-7_16"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355745"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/280277.280279"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/288692.288723"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Second ACM Workshop on Advances in Geographic Information Systems, ACM-GIS","author":"Henrich Andreas","year":"1994","unstructured":"Andreas Henrich . 1994 . A Distance Scan Algorithm for Spatial Access Structures . In Proceedings of the Second ACM Workshop on Advances in Geographic Information Systems, ACM-GIS 1994, Gaithersburg, MD, USA, Niki Pissinou and Kia Makki (Eds.). ACM, 136--143. Andreas Henrich. 1994. A Distance Scan Algorithm for Spatial Access Structures. In Proceedings of the Second ACM Workshop on Advances in Geographic Information Systems, ACM-GIS 1994, Gaithersburg, MD, USA, Niki Pissinou and Kia Makki (Eds.). ACM, 136--143."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Fifteenth International Conference on Very Large Data Bases","author":"Henrich Andreas","year":"1989","unstructured":"Andreas Henrich , Hans-Werner Six , and Peter Widmayer . 1989 . The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects . In Proceedings of the Fifteenth International Conference on Very Large Data Bases , August 22-25, 1989, Amsterdam, The Netherlands, Peter M. G. Apers and Gio Wiederhold (Eds.). Morgan Kaufmann, 45--53. http:\/\/www.vldb.org\/conf\/ 1989\/P045.PDF Andreas Henrich, Hans-Werner Six, and Peter Widmayer. 1989. The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. In Proceedings of the Fifteenth International Conference on Very Large Data Bases, August 22-25, 1989, Amsterdam, The Netherlands, Peter M. G. Apers and Gio Wiederhold (Eds.). Morgan Kaufmann, 45--53. http:\/\/www.vldb.org\/conf\/1989\/P045.PDF"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/320248.320255"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:DAPD.0000013068.25976.88"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/170088.170403"},{"key":"e_1_2_1_25_1","volume-title":"Hilbert R-tree: An Improved R-tree using Fractals. In VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases","author":"Kamel Ibrahim","year":"1994","unstructured":"Ibrahim Kamel and Christos Faloutsos . 1994 . Hilbert R-tree: An Improved R-tree using Fractals. In VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases , September 12-15, 1994, Santiago de Chile, Chile, Jorge B. Bocca, Matthias Jarke, and Carlo Zaniolo (Eds.). Morgan Kaufmann , 500--509. http:\/\/www.vldb.org\/conf\/1994\/P500.PDF Ibrahim Kamel and Christos Faloutsos. 1994. Hilbert R-tree: An Improved R-tree using Fractals. In VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile, Jorge B. Bocca, Matthias Jarke, and Carlo Zaniolo (Eds.). Morgan Kaufmann, 500--509. http:\/\/www.vldb.org\/conf\/1994\/P500.PDF"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253347"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375679"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012088469-8.50074-7"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.144"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02279-1_32"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1997.582015"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389703"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/99935.99949"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066230"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3085504.3085519"},{"key":"e_1_2_1_38_1","unstructured":"OpenStreetMap contributors. 2017. Planet dump retrieved from https:\/\/planet.osm.org. https:\/\/www.openstreetmap.org.  OpenStreetMap contributors. 2017. Planet dump retrieved from https:\/\/planet.osm.org. https:\/\/www.openstreetmap.org."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407829"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397506"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/582318.582321"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223794"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/318898.318900"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335427"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52208-5_28"},{"key":"e_1_2_1_47_1","volume-title":"The Design and Analysis of Spatial Data Structures","author":"Samet Hanan","unstructured":"Hanan Samet . 1990. The Design and Analysis of Spatial Data Structures . Addison-Wesley . Hanan Samet. 1990. The Design and Analysis of Spatial Data Structures. Addison-Wesley."},{"key":"e_1_2_1_48_1","volume-title":"Foundations of multidimensional and metric data structures","author":"Samet Hanan","unstructured":"Hanan Samet . 2006. Foundations of multidimensional and metric data structures . Academic Press . Hanan Samet. 2006. Foundations of multidimensional and metric data structures. Academic Press."},{"key":"e_1_2_1_49_1","volume-title":"VLDB'87, Proceedings of 13th International Conference on Very Large Data Bases","author":"Sellis Timos K.","year":"1987","unstructured":"Timos K. Sellis , Nick Roussopoulos , and Christos Faloutsos . 1987. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects . In VLDB'87, Proceedings of 13th International Conference on Very Large Data Bases , September 1-4, 1987 , Brighton, England, Peter M. Stocker, William Kent, and Peter Hammersley (Eds.). Morgan Kaufmann , 507--518. http:\/\/www.vldb.org\/conf\/1987\/P507.PDF Timos K. Sellis, Nick Roussopoulos, and Christos Faloutsos. 1987. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. In VLDB'87, Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton, England, Peter M. Stocker, William Kent, and Peter Hammersley (Eds.). Morgan Kaufmann, 507--518. http:\/\/www.vldb.org\/conf\/1987\/P507.PDF"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164192"},{"key":"e_1_2_1_51_1","volume-title":"The LSM RUM-Tree: A Log Structured Merge R-Tree for Update-intensive Spatial Workloads. 2021 IEEE 37th International Conference on Data Engineering (ICDE)","author":"Shin Jaewoo","year":"2021","unstructured":"Jaewoo Shin , Jianguo Wang , and Walid G. Aref . 2021 . The LSM RUM-Tree: A Log Structured Merge R-Tree for Update-intensive Spatial Workloads. 2021 IEEE 37th International Conference on Data Engineering (ICDE) ( 2021 ), 2285--2290. Jaewoo Shin, Jianguo Wang, and Walid G. Aref. 2021. The LSM RUM-Tree: A Log Structured Merge R-Tree for Update-intensive Spatial Workloads. 2021 IEEE 37th International Conference on Data Engineering (ICDE) (2021), 2285--2290."},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1007\/s00778-008-0120-3","article-title":"The RUM-tree: supporting frequent updates in R-trees using memos","volume":"18","author":"Silva Yasin N.","year":"2008","unstructured":"Yasin N. Silva , Xiaopeng Xiong , and Walid G. Aref . 2008 . The RUM-tree: supporting frequent updates in R-trees using memos . The VLDB Journal 18 (2008), 719 -- 738 . Yasin N. Silva, Xiaopeng Xiong, and Walid G. Aref. 2008. The RUM-tree: supporting frequent updates in R-trees using memos. The VLDB Journal 18 (2008), 719--738.","journal-title":"The VLDB Journal"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012088469-8.50066-8"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012722442-8\/50075-6"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00157"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2019.00121"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1996.492202"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.128"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.92"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3574245.3574253","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T23:20:41Z","timestamp":1677021641000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3574245.3574253"}},"subtitle":["A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing"],"short-title":[],"issued":{"date-parts":[[2022,12]]},"references-count":59,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.14778\/3574245.3574253"],"URL":"https:\/\/doi.org\/10.14778\/3574245.3574253","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,12]]},"assertion":[{"value":"2023-02-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}