Computationally Efficient Multiple Hypothesis Association of Intelligence Reports

In this paper we develop a computationally efficient multiple hypothesis association algorithm for generation of alternative association hypotheses regarding cluster memberships of intelligence reports represented as belief functions. We have previously an O(N² K²) clustering algorithm using a measure of pairwise conflicts, and a fast algorithm for classification of clusters using a more advanced measure. As these measures are similar but not identical and may have different minima we generate additional multiple association hypotheses around the solution found by the clustering algorithm. These hypotheses may then be evaluated by the classification algorithm in order to find the best overall classification of all clusters. In order to maintain the computational complexity we will investigate algorithms that run in no worse than O(N²K² ) time