149 citations · 233 across the 9 of their papers we have counts for
7 papers · 1 filter
Heavy Hitters over Interval Queries
Ran Ben Basat, Roy Friedman, Rana Shahout
Heavy hitters and frequency measurements are fundamental in many networking applications such as load balancing, QoS, and network security. This paper considers a generalized slidi…
Fast Flow Volume Estimation
Ran Ben Basat, Gil Einziger, Roy Friedman
The increasing popularity of jumbo frames means growing variance in the size of packets transmitted in modern networks. Consequently, network monitoring tools must maintain explici…
Constant Time Updates in Hierarchical Heavy Hitters
Ran Ben Basat, Gil Einziger, Roy Friedman +2
Monitoring tasks, such as anomaly and DDoS detection, require identifying frequent flow aggregates based on common IP prefixes. These are known as \emph{hierarchical heavy hitters}…
Succinct Approximate Rank Queries
Ran Ben Basat
We consider the problem of summarizing a multi set of elements in under the constraint that no element appears more than times. The goal is then to an…
Give Me Some Slack: Efficient Network Measurements
Ran Ben Basat, Gil Einziger, Roy Friedman
Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challengin…
Efficient Summing over Sliding Windows
Ran Ben Basat, Gil Einziger, Roy Friedman +1
This paper considers the problem of maintaining statistic aggregates over the last W elements of a data stream. First, the problem of counting the number of 1's in the last W bits…
Relations between automata and the simple k-path problem
Ran Ben-Basat, Ariel Gabizon
Let be a directed graph on vertices. Given an integer , the SIMPLE -PATH problem asks whether there exists a simple -path in . In case is weighted, the M…