Matching Random Tree Models of Spatio-Temporal Patterns to Tables or Graphs

The problem of matching random tree models of multi-component patterns to tables or graphs containing components extracted from diverse data sources is considered. We focus on bi-level trees whose branches emanate from one root node and terminate on different leaf nodes. Node and branch attributes are treated as random variables. Tree nodes represent pattern components of specified types that occur in tables or graphs to be searched. For each item in the table or graph with a type match to the tree root, there is a set of components from the table or graph that are candidate leaves for optimal matches to the tree model. We adopt a view of optimal matches to random tree models as minimum cost assignments of candidate leaves to tree branches. Model-based formulas are derived for computing costs associated with assignments of specific candidate leaf components from tables or graphs to specific tree branches. We specify an ontology suitable for dynamic geo-spatial query problems in which (1) tree nodes represent physical objects or events on the ground (buildings, roads, communication transmissions...), and (2) branch attributes characterize, with uncertainty, distance or time separations between components, and angles between links connecting components. Our approach is used to search very large images for specific types of buildings in probabilistically constrained spatial arrangements, with the goal of ranking model matches for efficient inspection by human analysts.