Scalable Distributed Processing of Spatial Point Data
Martin Raack, Odej Kao · 2011
The increasing availability of cheap location tracking devices is causing a steadily increasing demand for location based services. Such services usually utilize spatial data structures that need to scale with increasing request load. While static data allows for scaling by simple service replication, dynamic data such as moving users requires administration in a single coherent system to provide consistent and up-to-date processing results. In this paper, we propose a distributed system based on a P2P architecture to store and process spatial data, in particular with window- and k-nearest-neighbors queries. Our system is very simple in that it solely manages a range-partitioned linear data space defined by a Hilbert Curve mapping and neither requires explicit hashing, clustering or the maintenance of a dedicated distributed spatial structure at all. Our main focus is on the inherent quad-tree structure of the 2d Hilbert Curve and how it suffices to efficiently evaluate nearest-neighbor queries in a distributed manner. We verify our approach using real-world data from Open Street Map and demonstrate that the throughput of our system scales asymptotically linear with the network size.