Effectively Learning Spatial Indices

Jianzhong Qi, Guanli Liu, Christian S. Jensen, Lars Kulik

Research output: Contribution to journalJournal articleResearchpeer-review

1 Citation (Scopus)
41 Downloads (Pure)

Abstract

Machine learning, especially deep learning, is used increasingly to enable better solutions for data management tasks previously solved by other means, including database indexing. A recent study shows that a neural network can not only learn to predict the disk address of the data value associated with a one-dimensional search key but also outperform B-tree-based indexing, thus promises to speed up a broad range of database queries that rely on B-trees for efficient data access. We consider the problem of learning an index for two-dimensional spatial data. A direct application of a neural network is unattractive because there is no obvious ordering of spatial point data. Instead, we introduce a rank space based ordering technique to establish an ordering of point data and group the points into blocks for index learning. To enable scalability, we propose a recursive strategy that partitions a large point set and learns indices for each partition. Experiments on real and synthetic data sets with more than 100 million points show that our learned indices are highly effective and efficient. Query processing using our indices is more than an order of magnitude faster than the use of R-trees or a recently proposed learned index.

Original languageEnglish
JournalProceedings of the VLDB Endowment
Volume13
Issue number12
Pages (from-to)2341-2354
Number of pages14
ISSN2150-8097
DOIs
Publication statusPublished - 2020

Fingerprint Dive into the research topics of 'Effectively Learning Spatial Indices'. Together they form a unique fingerprint.

Cite this