טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentAntsfeld Leonid
SubjectEfficient Algorithms for Fusing Hierarchically Structured
Data
DepartmentDepartment of Applied Mathematics
Supervisors Professor Nadav Liron
Dr. David Hertz


Abstract

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(Nlog 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.