Spatial Queries Processing in Autonomous Mobile System Environment

In this paper, authors discuss a scheme for distributed processing of spatial index tree[1], and its application to spatial queries, Shortest Path Search(SPS), Distance Range Query(DRQ) and k-Nearest Neighbor search(kNN) for spatial networks. Spatial index tree is generated from a given road network using Network Voronoi Diagrams, and possesses layered structure. We herein assume autonomous mobile system environment where spatial index tree servers and GPS-equipped mobile devices, such as ANDROID embedded smart phones, communicate with each other to process these spatial queries in a distributed manner. Queries are processed in two separate steps, rough search in servers and fine search in mobile devices, respectively. Structured data of spatial index tree are extracted for each generator region, and stored in servers. Some numerical results are presented for real map data issued by Geographical Survey Institute.