Searching for places by their spatial configuration is useful in domains that are grounded in the physical world, like urban planning, civil engineering, and travel. However, many spatial search use cases in these domains are not well-served by modern search engines and mapping applications, with many spatial search questions naturally specified using a visual query pattern, which requires computationally expensive spatial pattern matching to resolve. The types of spatial relationships that can be defined are also heterogeneous in nature, making it difficult to reason over them consistently, and capturing such a query typically requires using an image, pictorial, sketch-map, or graph-based query format, which is incompatible with text-centric search engines and mapping platforms.

In this thesis, we address these challenges, taking an approach that is approximate in nature to address the computational cost and flexible enough to handle heterogeneous relations and multi-modal query formats to facilitate integration with mainstream search platforms. We leverage techniques in artificial intelligence and natural language processing to develop an ensemble of complementary methods and introduce a system that showcases the viability of our approach to enable fast, robust approximate search over directional spatial queries.