LISA: A Learned Index Structure for Spatial Data

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

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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.
Original languageEnglish
Title of host publicationSIGMOD' 20: Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020
EditorsDavid Maier, Rachel Pottinger, AnHai Doan, Wang-Chiew Tan, Abdussalam Alawini, Hung Q. Ngo
Number of pages15
Place of PublicationNew York
PublisherAssociation for Computing Machinery
Publication date2020
Pages2119-2133
ISBN (Electronic)978-1-4503-6735-6
DOIs
Publication statusPublished - 2020
EventThe 2020 International Conference on Management of Data (Online): SIGMOD Conference 2020 - Portland (Online), Portland, United States
Duration: 14 Jun 202019 Jun 2020
https://sigmod2020.org/

Conference

ConferenceThe 2020 International Conference on Management of Data (Online)
LocationPortland (Online)
Country/TerritoryUnited States
CityPortland
Period14/06/202019/06/2020
Internet address

Cite this