Enhancements to high level data fusion using graph matching and state space search

Kedar Sambhoos, Rakesh Nagi, Moises Sudit, Adam Stotz

Research output: Contribution to journalArticlepeer-review


The intent of this paper is to show enhancements in Levels 2 and 3 fusion capabilities through a new class of models and algorithms in graph matching. The problem today is not often lack of data, but instead, lack of information and data overload. Graph matching algorithms help us solve this problem by identifying meaningful patterns in voluminous amounts of data to provide information. In this paper we investigate a classical graph matching technique for subgraph isomorphism. A complete implementation of a heuristic approach (since the problem under consideration is NP-Hard) using an inexact isomorphism technique has been used. The heuristic approach is called Truncated Search Tree algorithm (TruST), where the state space of the problem is constrained using breadth and depth control parameters. The breadth and depth control parameters are then studied using design of experiment based inferential statistics. Finally, a software implementation of the procedure has been completed.

Original languageEnglish (US)
Pages (from-to)351-364
Number of pages14
JournalInformation Fusion
Issue number4
StatePublished - Oct 2010
Externally publishedYes


  • Data fusion
  • Design of experiments
  • Graph/subgraph matching
  • State space search

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Enhancements to high level data fusion using graph matching and state space search'. Together they form a unique fingerprint.

Cite this