LISA: A Learned Index Structure for Spatial Data

Pengfei Li, Hua Lu, Qian Zheng, Long Yang, Gang Pan

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review


In spatial query processing, the popular index R-tree may incur large storage consumption and high IO cost. Inspired by the recent learned index [17] that replaces B-tree with machine learning models, we study an analogy problem for spatial data. We propose a novel Learned Index structure for Spatial dAta (LISA for short). Its core idea is to use machine learning models, through several steps, to generate searchable data layout in disk pages for an arbitrary spatial dataset. In particular, LISA consists of a mapping function that maps spatial keys (points) into 1-dimensional mapped values, a learned shard prediction function that partitions the mapped space into shards, and a series of local models that organize shards into pages. Based on LISA, a range query algorithm is designed, followed by a lattice regression model that enables us to convert a KNN query to range queries. Algorithms are also designed for LISA to handle data updates. Extensive experiments demonstrate that LISA clearly outperforms R-tree and other alternatives in terms of storage consumption and IO cost for queries. Moreover, LISA can handle data insertions and deletions efficiently.
TitelSIGMOD' 20: Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020
RedaktørerDavid Maier, Rachel Pottinger, AnHai Doan, Wang-Chiew Tan, Abdussalam Alawini, Hung Q. Ngo
Antal sider15
UdgivelsesstedNew York
ForlagAssociation for Computing Machinery
ISBN (Elektronisk)978-1-4503-6735-6
StatusUdgivet - 2020
BegivenhedThe 2020 International Conference on Management of Data (Online): SIGMOD Conference 2020 - Portland (Online), Portland, USA
Varighed: 14 jun. 202019 jun. 2020


KonferenceThe 2020 International Conference on Management of Data (Online)
LokationPortland (Online)

Citer dette