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

Abstract

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.
OriginalsprogEngelsk
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
Publikationsdato2020
Sider2119-2133
ISBN (Elektronisk)978-1-4503-6735-6
DOI
StatusUdgivet - 2020
BegivenhedThe 2020 International Conference on Management of Data (Online): SIGMOD Conference 2020 - Portland (Online), Portland, USA
Varighed: 14 jun. 202019 jun. 2020
https://sigmod2020.org/

Konference

KonferenceThe 2020 International Conference on Management of Data (Online)
LokationPortland (Online)
Land/OmrådeUSA
ByPortland
Periode14/06/202019/06/2020
Internetadresse

Citer dette