Publications

Computationally Efficient CP Tensor Decomposition Update Framework for Emerging Component Discovery in Streaming Data

We present streaming CP update, an algorithmic framework for updating CP tensor decompositions that possesses the capability of identifying emerging components and can produce decompositions of large, sparse tensors streaming along multiple modes at a low computational cost. We discuss a large-scale implementation of the proposed scheme integrated within the ENSIGN tensor analysis package, and we evaluate and demonstrate the performance of the framework, in terms of computational efficiency and capability to discover emerging components, on a real cyber dataset.

Accelerating Dijkstra's Algorithm Using Multiresolution Priority Queues

Multiresolution priority queues are data structures recently discovered by Reservoir Labs that reduce the entropy of some critical graph algorithms—such as Dijkstra’s or Prim’s algorithms—and deliver new lower computational complexity bounds. These new data structures are capable of exploiting the multiresolution properties of discrete algorithms, a characteristic that has been otherwise overlooked in the field of graph algorithms. Similar to the concept of resolution found in signal processing—by which a signal can be undersampled while information loss is zero or very small—graphs’ entropy tends to be concentrated in regions that can be efficiently exploited by multiresolution data structures. In this approach, a small controllable bounded discrete error is introduced in a way that entropy is substantially reduced, resulting in new lower computational complexity algorithms.

While the fastest currently known graph algorithms provide exact solutions at the expense of incurring high computational costs, a multiresolution graph algorithm is capable of softening graph problems and breaking their current information theoretic barriers, introducing a small amount of controlled error in a way that the problem’s entropy is reduced. As a result, a new class of higher performance graph algorithms is enabled, enabling the solution of previously deemed intractable problems by identifying solutions that are close to optimal and within a known bounded error.

All-at-once Decomposition of Coupled Billion-scale Tensors in Apache Spark

As the scale of unlabeled data rises, it becomes increasingly valuable to perform scalable, unsupervised data analysis. Tensor decompositions, which have been empirically successful at finding meaningful cross-dimensional patterns in multidimensional data, are a natural candidate to test for scalability and meaningful pattern discovery in these massive real-world datasets. Furthermore, the production of big data of different types necessitates the ability to mine patterns across disparate sources. The coupled tensor decomposition framework captures this idea by decomposing several tensors from different data sources together. We present a scalable implementation of coupled tensor decomposition on Apache Spark. We introduce nonnegativity and sparsity constraints, and perform all-at-once quasi-Newton optimization of all factor matrix parameters. We present results showing the billion-scale scalability of this novel implementation and also demonstrate the high level of interpretability in the components produced, suggesting that coupled, all-at-once tensor decompositions on Apache Spark represent a promising framework for large-scale, unsupervised pattern discovery.

High Speed Elephant Flow Detection Under Partial Information

In this paper we introduce a new framework to detect elephant flows at very high speed rates and under uncertainty. The framework provides exact mathematical formulas to compute the detection likelihood and introduces a new flow reconstruction lemma under partial information. These  theoretical results lead to the design of BubbleCache, a new elephant flow detection algorithm  designed to operate near the optimal tradeoff between computational scalability and accuracy by dynamically tracking the traffic’s natural cutoff sampling rate. We demonstrate on a real world 100 Gbps network that the BubbleCache algorithm helps reduce the computational cost by a factor of 1000 and the memory requirements by a factor of 100 while detecting the top flows on the network with very high probability.

Topic Modeling for Analysis of Big Data Tensor Decompositions