Multi-Target Tracking (MTT) is a challenging problem in the field of data association and sensor data fusion. Many solutions to MTT assume a Markovian nature to the motion of the target to solve the problem and avoid the potential computational complexity. Recently, we have shown that considering a sequence of three time steps and their resulting triplet costs in data association provides a superior solution that better incorporates the kinematic behavior of maneuvering targets. Nevertheless, the triplet costs pose significant computational overhead and scaling challenges. In this paper, we present significant computational advances in a triplet cost-based data association engine for MTT using Graphics Processing Units (GPUs). We achieve this by improving the computational performance of the dual ascent algorithm for dense Multi-Dimensional Assignment Problem (MAP), presented in Vadrevu and Nagi, 2022. Our contributions include: (1) A very fast GPU-accelerated Linear Assignment Problem (LAP) solver that solves an array of tiled LAPs without synchronizing with the CPU, (2) Reduction in computational overheads of triplet costs by using gating and compressed matrix representations, and (3) Computational performance studies that demonstrate the effectiveness of our computational enhancements. Our resulting solution is 5.8 times faster than the current solution without compromising the accuracy.

Recently we proposed a new Mixed-Integer Linear Programming formulation for the Multi-Target Tracking (MTT) problem and used a standard optimization solver to demonstrate its viability [1]. Subsequently, we provided Graphics Processing Unit (GPU) accelerated algorithms for the underlying Multidimensional Assignment Problem (MAP) with decomposable costs or triplet costs using a Lagrangian Relaxation (LR) framework. Here, we present a Dual-Ascent algorithm that provides monotonically increasing lower bounds and converges in a fraction of iterations required for a subgradient scheme. This approach can handle a large number of targets for many time steps with massive parallelism and computational efficiency. The dual-ascent framework decomposes the MAP into a set of Linear Assignment Problems (LAPs) for adjacent time-steps, which can be solved in parallel using the GPU-accelerated method of [2], [3]. The overall dual-ascent algorithm is able to efficiently solve problems with 100 targets and 100 time-frames with high accuracy. We demonstrate the applicability of our new algorithm to MTT by including realistic issues of missed detections and false alarms. Computational results demonstrate the robustness of the algorithm with good MMEP and ITCP scores and solution times for the larger problems in less than 6 seconds.

This paper attempts to provide viral marketeers guidance in terms of an investment level that could help capture some desired γ percentage of the market-share by some target time t with a desired level of confidence. To do this, we first introduce a diffusion model for social networks. A distance-dependent random graph is then considered as a model for the underlying social network, which we use to analyze the proposed diffusion model. Using the fact that vertices degrees have an almost Poisson distribution in distance-dependent random networks, we then provide a lower bound on the probability of the event that the time it takes for an idea (or a product, disease, etc.) to dominate a pre-specified γ percentage of a social network (denoted by Rγ) is smaller than some pre-selected target time t > 0, i.e., we find a lower bound on the probability of the event {Rγ ≤ t}. Simulation results performed over a wide variety of networks, including random as well as real-world, are then provided to verify that our bound indeed holds in practice. The Kullback-Leibler divergence measure is used to evaluate performance of our lower bound over these groups of networks, and as expected, we note that for networks that deviate more from the Poisson degree distribution, our lower bound does worse.

In this paper, we propose an integer programming based model for tracking multiple maneuverable targets in a planar region. The objective function of this model uses both pairs and triplets of observations, which offer more accurate representation for constant velocity targets. Triplet scores in this model are calculated using a novel approach based on cubic spline interpolation, while the data association problem is solved using a specialized multi-dimensional assignment formulation. We show that the spline interpolation based scoring model provides more accurate reconstruction of trajectories, when compared to a naïve model based on linear interpolation, on various randomly generated trajectories, at the expense of modest increase in computation time. The proposed multi-dimensional assignment formulation has nice structural properties and tight linear programming relaxation bound, which results in small computation times.

Today's social networks are getting larger, and the need to analyze datasets with millions of nodes and billions of edges is not uncommon any more. As a network of social relationships evolves by the addition of new nodes and edges, fast algorithms are desirable for the recomputation of key network measures such as actor centrality. The distributed computing paradigm offers a scalable approach to addressing the recomputation challenge. This paper develops a Map-Reduce implementation of an incremental All-Pairs Shortest Path (APSP) algorithm. The incremental nature of the approach allows for performing minimal work in updating centrality measures, while the Map-Reduce implementation makes it scalable to large data. The key idea of the incremental APSP algorithm [1] is based on the efficient use of past information about the shortest paths between any node and the neighbors of the newly added node. A presented parallelized version of the algorithm relies on a three-step iterative execution of the "map" and "reduce" jobs. Experiences with its implementation are reported in application to a real-world dataset containing 7115 nodes. The experimental runs were performed using the Amazon's EMR service.

In this work, we consider a relatively new representation used in cognitive theory to describe how people understand concepts. This representation is called Conceptual Spaces, and is a geometrical way to represent human thought. Our work relates Conceptual Spaces to Data Fusion, first at Level 1, and later to be extended to Level 2 (as defined by JDL [1]). In this paper, we focus on modeling these Conceptual Spaces as a mathematical program. We then discuss uses and methodologies for Conceptual Spaces in the light of Data Fusion.

Asymmetric/urban warfare, improvised explosive devices (IEDs), and dirty bombs are dominating over conventional warfare, and there is an urgent need to deal with them systematically. Effective strategies of thwarting terrorism continue to be the top priority for international communities. This paper presents a research approach for situation awareness and threat/impact assessment strategies for a genre of UW problems. The approach is based on a formal domain ontology and a scenario authoring and simulation environment. A class of hybrid deductive (model-based) and inductive reasoning approaches are applied to the scenario simulation and performance evaluation studies are conducted. Such an approach can be used for training purposes as well as fusion technology development. An example will be presented

The intent of this paper is to show enhancements in level 2 and 3 fusion capabilities through a new class of graph models and solution strategies. The problem today is not often lack of information, but instead, information overload. Graphs have demonstrated to be a useful framework to represent and analyze large amounts of information. Classical strategies such as Bayesian networks, semantic networks and graph matching are some examples of the power of graphs. We will introduce two different but related graph-based structures that will allow us to span the temporal performance of decision-making processes. Given that most of the high level information fusion problems of interest are NP-Hard, there is a need to separate methodologies between "near real-time" tools and forensic heuristics. With this in mind we will introduce a real-time decision-making tool (INFERD) and a forensic graph matching algorithm (TruST)