{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T10:01:35Z","timestamp":1771236095925,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:p>\n            Can we quickly explore large multidimensional data in main memory?\n            <jats:italic>Adaptive indexing<\/jats:italic>\n            responds to this need by building an index incrementally, in response to queries; in its default form, it indexes a single attribute or, in the presence of several attributes, one attribute per index level. Unfortunately, this approach falters when indexing spatial data objects, encountered in data exploration tasks involving multidimensional range queries. In this paper, we introduce the Adaptive Incremental R-tree (AIR-tree): the first method for the adaptive indexing of non-point spatial objects; the AIR-tree incrementally and progressively constructs an in-memory spatial index over a static array, in response to incoming queries, using a suite of heuristics for creating and splitting nodes. Our thorough experimental study on synthetic and real data and workloads shows that the AIR-tree consistently outperforms prior adaptive indexing methods focusing on multidimensional points and a pre-built static R-tree in cumulative time over at least the first thousand queries.\n          <\/jats:p>","DOI":"10.14778\/3598581.3598596","type":"journal-article","created":{"date-parts":[[2023,7,10]],"date-time":"2023-07-10T22:19:06Z","timestamp":1689027546000},"page":"2248-2260","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Adaptive Indexing of Objects with Spatial Extent"],"prefix":"10.14778","volume":"16","author":[{"given":"Fatemeh","family":"Zardbani","sequence":"first","affiliation":[{"name":"Aarhus University"}]},{"given":"Nikos","family":"Mamoulis","sequence":"additional","affiliation":[{"name":"University of Ioannina"}]},{"given":"Stratos","family":"Idreos","sequence":"additional","affiliation":[{"name":"Harvard University"}]},{"given":"Panagiotis","family":"Karras","sequence":"additional","affiliation":[{"name":"Aarhus University"}]}],"member":"320","published-online":{"date-parts":[[2023,7,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398577"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/2831360.2831361"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328920"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_5_1","first-page":"799","volume-title":"SIGMOD","author":"Beckmann Norbert","year":"2009","unstructured":"Norbert Beckmann and Bernhard Seeger . A revised R*-tree in comparison with related index structures . In SIGMOD , pages 799 -- 812 , 2009 . Norbert Beckmann and Bernhard Seeger. A revised R*-tree in comparison with related index structures. In SIGMOD, pages 799--812, 2009."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425880"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/647223.718775"},{"key":"e_1_2_1_9_1","first-page":"1352","volume-title":"SpatialHadoop: A MapReduce Framework for Spatial Data. In ICDE","author":"Eldawy Ahmed","year":"2015","unstructured":"Ahmed Eldawy and Mohamed F . Mokbel . SpatialHadoop: A MapReduce Framework for Spatial Data. In ICDE , pages 1352 -- 1363 , 2015 . Ahmed Eldawy and Mohamed F. Mokbel. SpatialHadoop: A MapReduce Framework for Spatial Data. In ICDE, pages 1352--1363, 2015."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38758"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168652"},{"key":"e_1_2_1_13_1","first-page":"393","volume-title":"7th Intl Conf. on Data Science, Technology and Applications DATA","author":"Holanda Pedro","year":"2018","unstructured":"Pedro Holanda , Matheus Nerone , Eduardo Cunha de Almeida , and Stefan Manegold . Cracking KD-tree : The first multidimensional adaptive indexing (position paper) . In 7th Intl Conf. on Data Science, Technology and Applications DATA , pages 393 -- 399 , 2018 . Pedro Holanda, Matheus Nerone, Eduardo Cunha de Almeida, and Stefan Manegold. Cracking KD-tree: The first multidimensional adaptive indexing (position paper). In 7th Intl Conf. on Data Science, Technology and Applications DATA, pages 393--399, 2018."},{"key":"e_1_2_1_14_1","first-page":"68","volume-title":"CIDR","author":"Idreos Stratos","year":"2007","unstructured":"Stratos Idreos , Martin L. Kersten , and Stefan Manegold . Database cracking . In CIDR , pages 68 -- 78 , 2007 . Stratos Idreos, Martin L. Kersten, and Stefan Manegold. Database cracking. In CIDR, pages 68--78, 2007."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559878"},{"issue":"9","key":"e_1_2_1_16_1","first-page":"585","article-title":"Adaptive indexing in main-memory column-stores","volume":"4","author":"Idreos Stratos","year":"2011","unstructured":"Stratos Idreos , Stefan Manegold , Harumi A. Kuno , and Goetz Graefe . Merging what's cracked, cracking what's merged : Adaptive indexing in main-memory column-stores . PVLDB , 4 ( 9 ): 585 -- 597 , 2011 . Stratos Idreos, Stefan Manegold, Harumi A. Kuno, and Goetz Graefe. Merging what's cracked, cracking what's merged: Adaptive indexing in main-memory column-stores. PVLDB, 4(9):585--597, 2011.","journal-title":"PVLDB"},{"key":"e_1_2_1_17_1","first-page":"469","volume-title":"EDBT","author":"Jensen Anders Hammersh\u00f8j","year":"2021","unstructured":"Anders Hammersh\u00f8j Jensen , Frederik Lauridsen , Fatemeh Zardbani , Stratos Idreos , and Panagiotis Karras . Revisiting multidimensional adaptive indexing . In EDBT , pages 469 -- 474 , 2021 . Anders Hammersh\u00f8j Jensen, Frederik Lauridsen, Fatemeh Zardbani, Stratos Idreos, and Panagiotis Karras. Revisiting multidimensional adaptive indexing. In EDBT, pages 469--474, 2021."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217055"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0146-664X(76)80006-8"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/645482.653437"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00014"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401090"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(82)90104-6"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_1_25_1","first-page":"624","volume-title":"ICDE","author":"Nerone Matheus Agio","year":"2021","unstructured":"Matheus Agio Nerone , Pedro Holanda , Eduardo Cunha de Almeida, and Stefan Manegold. Multidimensional adaptive & progressive indexes . In ICDE , pages 624 -- 635 , 2021 . Matheus Agio Nerone, Pedro Holanda, Eduardo Cunha de Almeida, and Stefan Manegold. Multidimensional adaptive & progressive indexes. In ICDE, pages 624--635, 2021."},{"key":"e_1_2_1_26_1","first-page":"701","volume-title":"SIGMOD","author":"Nobari Sadegh","year":"2013","unstructured":"Sadegh Nobari , Farhan Tauheed , Thomas Heinis , Panagiotis Karras , St\u00e9phane Bressan , and Anastasia Ailamaki . TOUCH : in-memory spatial join by hierarchical data-oriented partitioning . In SIGMOD , pages 701 -- 712 , 2013 . Sadegh Nobari, Farhan Tauheed, Thomas Heinis, Panagiotis Karras, St\u00e9phane Bressan, and Anastasia Ailamaki. TOUCH: in-memory spatial join by hierarchical data-oriented partitioning. In SIGMOD, pages 701--712, 2013."},{"key":"e_1_2_1_27_1","first-page":"325","volume-title":"EDBT","author":"Pavlovic Mirjana","year":"2018","unstructured":"Mirjana Pavlovic , Darius Sidlauskas , Thomas Heinis , and Anastasia Ailamaki . QUASII : query-aware spatial incremental index . In EDBT , pages 325 -- 336 , 2018 . Mirjana Pavlovic, Darius Sidlauskas, Thomas Heinis, and Anastasia Ailamaki. QUASII: query-aware spatial incremental index. In EDBT, pages 325--336, 2018."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078195"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610522"},{"key":"e_1_2_1_30_1","first-page":"507","volume-title":"VLDB","author":"Sellis Timos K.","year":"1987","unstructured":"Timos K. Sellis , Nick Roussopoulos , and Christos Faloutsos . The R+-tree : A dynamic index for multi-dimensional objects . In VLDB , pages 507 -- 518 , 1987 . Timos K. Sellis, Nick Roussopoulos, and Christos Faloutsos. The R+-tree: A dynamic index for multi-dimensional objects. In VLDB, pages 507--518, 1987."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1080\/136588197242185"},{"key":"e_1_2_1_32_1","volume-title":"ICLR","author":"Tsitsulin Anton","year":"2020","unstructured":"Anton Tsitsulin , Marina Munkhoeva , Davide Mottin , Panagiotis Karras , Alexander M. Bronstein , Ivan V. Oseledets , and Emmanuel M\u00fcller . The shape of data: Intrinsic distance for data distributions . In ICLR , 2020 . Anton Tsitsulin, Marina Munkhoeva, Davide Mottin, Panagiotis Karras, Alexander M. Bronstein, Ivan V. Oseledets, and Emmanuel M\u00fcller. The shape of data: Intrinsic distance for data distributions. In ICLR, 2020."},{"key":"e_1_2_1_33_1","first-page":"444","volume-title":"Game Programming Gems","author":"Ulrich Thatcher","year":"2000","unstructured":"Thatcher Ulrich . Loose octrees. In Mark DeLoura, editor , Game Programming Gems , pages 444 -- 453 . Charles River Media , 2000 . Thatcher Ulrich. Loose octrees. In Mark DeLoura, editor, Game Programming Gems, pages 444--453. Charles River Media, 2000."},{"key":"e_1_2_1_34_1","first-page":"193","volume-title":"SIGMOD","author":"Yang Zongheng","year":"2020","unstructured":"Zongheng Yang , Badrish Chandramouli , Chi Wang , Johannes Gehrke , Yinan Li , Umar Farooq Minhas , Per-\u00c5ke Larson , Donald Kossmann , and Rajeev Acharya . Qd-tree : Learning data layouts for big data analytics . In SIGMOD , pages 193 -- 208 , 2020 . Zongheng Yang, Badrish Chandramouli, Chi Wang, Johannes Gehrke, Yinan Li, Umar Farooq Minhas, Per-\u00c5ke Larson, Donald Kossmann, and Rajeev Acharya. Qd-tree: Learning data layouts for big data analytics. In SIGMOD, pages 193--208, 2020."},{"key":"e_1_2_1_35_1","first-page":"415","volume-title":"EDBT","author":"Zardbani Fatemeh","year":"2020","unstructured":"Fatemeh Zardbani , Peyman Afshani , and Panagiotis Karras . Revisiting the theory and practice of database cracking . In EDBT , pages 415 -- 418 , 2020 . Fatemeh Zardbani, Peyman Afshani, and Panagiotis Karras. Revisiting the theory and practice of database cracking. In EDBT, pages 415--418, 2020."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3598581.3598596","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,19]],"date-time":"2023-07-19T22:58:32Z","timestamp":1689807512000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3598581.3598596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5]]},"references-count":35,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["10.14778\/3598581.3598596"],"URL":"https:\/\/doi.org\/10.14778\/3598581.3598596","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,5]]},"assertion":[{"value":"2023-07-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}