Density Based Learned Spatial Index for Clustered Data

Retrieving spatial points, such as GPS records, that meet specific location criteria from a spatial database is a crucial operation in location-based services. Recent research suggests that learned indexes can surpass traditional ones in both query performance and space efficiency by leveraging data distribution information to construct a compact model, whereas traditional indexes make minimal assumptions about data distribution. In real-world spatial databases, spatial data often clusters, indicating a non-uniform distribution but concentration in specific regions or along road networks. Adaptivity of the index to this data pattern is crucial in such scenarios. In this paper, we discuss building efficient learned indexes by capitalizing on the clustering property of the dataset. Specifically, we propose a Density-based Grid Learning Spatial Index (DGLSI) that partitions spatial data based on data point density and employs learned models, including spatial interpolation functions and a recursive model index, to predict the grid cell IDs of query points. We evaluate DGLSI’s performance on real-world GPS datasets and demonstrate that the proposed methods outperform analogous grid-based indexes across various query workloads, including nearest point queries and range queries while maintaining high space efficiency.