Publications/Algorithms

Systems and Methods for Multiresolution Parsing

A multiresolution parser (MRP) can selectively extract one or more information units from a dataset based on the available processing capacity and/or the arrival rate of the dataset. Should any of these parameters change, the MRP can adaptively change the information units to be extracted such that the benefit or

Read More »

On the Bottleneck Structure of Positive Linear Programming

Positive linear programming (PLP), also known as packing and covering linear programs, is an important class of problems frequently found in fields such as network science, operations research, or economics. In this work we demonstrate that all PLP problems can be represented using a network structure, revealing new key insights

Read More »

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

Read More »

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

Read More »

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,

Read More »

A Pragmatic Approach of Determining Heavy-Hitter Traffic Thresholds

Heavy-hitter flows or Cheetah Flows (CF), which are high-rate flows can result in increased packet losses and delay in general Internet traffic. A Cheetah Flow Traffic Engineering System (CFTES) is presented, which can dynamically compute a heavy-hitter or CF threshold using information from the general background traffic. The system works

Read More »

Algorithms and Data Structures to Accelerate Network Analysis

As the sheer amount of computer generated data continues to grow exponentially, new bottlenecks are unveiled that require rethinking our traditional software and hardware architectures. In this paper, we present five algorithms and data structures (long queue emulation, lockless bimodal queues, tail early dropping, LFN tables, and multiresolution priority queues)

Read More »