3D Spatial Pattern Matching
For applications like urban planning and landmark search, this work addresses the limitation of 2D spatial pattern matching by incorporating height, but the contribution is incremental as it primarily extends existing methods.
Extended spatial pattern matching from 2D to 3D by defining the problem in three dimensions and providing a subgraph matching algorithm for distance relations. Tested on synthetic and real building data from Hamburg, establishing baseline results.
Spatial pattern matching is the process of matching query entities and constraints with database entities and relations. It has many applications, including similar region search, housing market search, landmark search, and road network matching. To our knowledge, all existing spatial pattern matching approaches frame the problem in a 2 dimensional space, where entities lie in a cartesian plane and relationships defined between them are contained in 2 dimensions. However, this problem framing has significant limitations when searching for real world entities that have height in addition to position. To address this limitation, we extend spatial pattern matching to 3 dimensions and provide a generalized definition of the problem. We describe a subgraph matching algorithm capable of resolving 3D spatial patterns over distance relations and release two 3D spatial pattern matching datasets, one synthetic and one containing real 3D building data from the city of Hamburg, Germany. We test our subgraph matching algorithm on both datasets and present results as a baseline for future methods to build upon.