Spatial Indexing for Location-Aware Systems

As location systems provide increasingly fine-grained locations for mobile entities, location-aware systems that react appropriately and autonomously to location events will be in demand. Although much research has been devoted to indexing schemes for very large scale GIS applications (where the systems are predominantly query-based), comparably little attention has been given to the use of spatial indexing within location-aware systems leveraging local positioning systems (predominantly event-based). This paper reviews the notion of spatial indexing (the representation of a tracked user's space to facilitate spatial event generation based on incoming locations) for event-based systems. It establishes the principles and requirements of a wide-area spatial indexer, reviews the R-tree, Quadtree and RQ-tree methods proposed before for indoor location-awareness, and significantly adapts the latter to meet the requirements. The proposed indexing method uses a combination of R-trees (for high level spatial information, down to structural level) and Quadtrees (for lower level representation of objects). It proposes the use of linear Quadtrees to exploit the ease of direct node movement rather than the re-rasterisation of polygons used in systems to date. This approach is compared in simulation with other approaches