  Graphs are widely used to model data in many application domains. Thanks to
the wide spread use of GPS-enabled devices, many applications assign a spatial
attribute to graph vertices (e.g., geo-tagged social media). Users may issue a
Reachability Query with Spatial Range Predicate (abbr. RangeReach). RangeReach
finds whether an input vertex can reach any spatial vertex that lies within an
input spatial range. An example of a RangeReach query is: Given a social graph,
find whether Alice can reach any of the venues located within the geographical
area of Arizona State University. The paper proposes GeoReach an approach that
adds spatial data awareness to a graph database management system (GDBMS).
GeoReach allows efficient execution of RangeReach queries, yet without
compromising a lot on the overall system scalability (measured in terms of
storage size and initialization/maintenance time). To achieve that, GeoReach is
equipped with a light-weight data structure, namely SPA-Graph, that augments
the underlying graph data with spatial indexing directories. When a RangeReach
query is issued, the system employs a pruned-graph traversal approach.
Experiments based on real system implementation inside Neo4j proves that
GEOREACH exhibits up to two orders of magnitude better query response time and
up to four times less storage than the state-of-the-art spatial and
reachability indexing approaches.
