M.Sc Student | Antsfeld Leonid |
---|---|

Subject | Efficient Algorithms for Fusing Hierarchically Structured Data |

Department | Department of Applied Mathematics |

Supervisors | Professor Nadav Liron |

Dr. David Hertz |

Suppose
that several sensors simultaneously, or a single sensor sequentially observe
the same *n* objects and produce(s) *m* noisy reports of estimates of
their types. Here, the only allowed observed types are associated with a given
hierarchical structure that is represented by a rooted tree. In this thesis we
present an efficient algorithm for matching and fusing the received *m* observation
reports.

For the matching problem we first describe the proposed optimal algorithm and then analyze its computational complexity. We show that its time complexity is

O(*N*log
*N*), where *N* is the number of nodes in the rooted tree that
correspond to the observed objects. We also present several other new solution
approaches that have higher computational complexity than the proposed greedy
algorithm but can be used for solving the weighted version of the above
problem. Finally, for finding only the cardinality of the optimal matching, we present
a modification of the proposed greedy algorithm whose time complexity is O(*Nk*),
where *k* is the maximal degree of *T*. This modification has been
used by us to derive an efficient suboptimal algorithm for fusion of several
observation reports.

For the fusion algorithm, we
first present an optimal algorithm for solving the above problem. that
generates an hypothesis set of all possible solutions. Then, based on the optimal
algorithm we propose a suboptimal algorithm that judiciously generates a
substantially reduced hypotheses set. The simulations reveal that by using the
proposed suboptimal algorithm, we could quite accurately estimate the true *n*
object types.