Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userElastic_HH: Tailored Elastic for Finding Heavy Hitters
50
0
0.0
(
0
)
Added by
Xilai Liu
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Finding heavy hitters has been of vital importance in network measurement. Among all the recent works in finding heavy hitters, the Elastic sketch achieves the highest accuracy and fastest speed. However, we find that there is still room for improvement of the Elastic sketch in finding heavy hitters. In this paper, we propose a tailored Elastic to enhance the sketch only for finding heavy hitters at the cost of losing the generality of Elastic. To tailor Elastic, we abandon the light part, and improve the eviction strategy. Our experimental results show that compared with the standard Elastic, our tailored Elastic reduces the error rate to 5.7~8.1 times and increases the speed to 2.5 times. All the related source codes and datasets are available at Github.
rate research
Read More
We study the heavy hitters and related sparse recovery problems in the low-failure probability regime. This regime is not well-understood, and has only been studied for non-adaptive schemes. The main previous work is one on sparse recovery by Gilbert et al.(ICALP13). We recognize an error in their analysis, improve their results, and contribute new non-adaptive and adaptive sparse recovery algorithms, as well as provide upper and lower bounds for the heavy hitters problem with low failure probability.
We study the distinct elements and $ell_p$-heavy hitters problems in the sliding window model, where only the most recent $n$ elements in the data stream form the underlying set. We first introduce the composable histogram, a simple twist on the exponential (Datar et al., SODA 2002) and smooth histograms (Braverman and Ostrovsky, FOCS 2007) that may be of independent interest. We then show that the composable histogram along with a careful combination of existing techniques to track either the identity or frequency of a few specific items suffices to obtain algorithms for both distinct elements and $ell_p$-heavy hitters that are nearly optimal in both $n$ and $epsilon$. Applying our new composable histogram framework, we provide an algorithm that outputs a $(1+epsilon)$-approximation to the number of distinct elements in the sliding window model and uses $mathcal{O}left(frac{1}{epsilon^2}log nlogfrac{1}{epsilon}loglog n+frac{1}{epsilon}log^2 nright)$ bits of space. For $ell_p$-heavy hitters, we provide an algorithm using space $mathcal{O}left(frac{1}{epsilon^p}log^2 nleft(log^2log n+logfrac{1}{epsilon}right)right)$ for $0<ple 2$, improving upon the best-known algorithm for $ell_2$-heavy hitters (Braverman et al., COCOON 2014), which has space complexity $mathcal{O}left(frac{1}{epsilon^4}log^3 nright)$. We also show complementing nearly optimal lower bounds of $Omegaleft(frac{1}{epsilon}log^2 n+frac{1}{epsilon^2}log nright)$ for distinct elements and $Omegaleft(frac{1}{epsilon^p}log^2 nright)$ for $ell_p$-heavy hitters, both tight up to $mathcal{O}left(loglog nright)$ and $mathcal{O}left(logfrac{1}{epsilon}right)$ factors.
Network device syslogs are ubiquitous and abundant in modern data centers with most large data centers producing millions of messages per day. Yet, the operational information reflected in syslogs and their implications on diagnosis or management tasks are poorly understood. Prevalent approaches to understanding syslogs focus on simple correlation and abnormality detection and are often limited to detection providing little insight towards diagnosis and resolution. Towards improving data center operations, we propose and implement Log-Prophet, a system that applies a toolbox of statistical techniques and domain-specific models to mine detailed diagnoses. Log-Prophet infers causal relationships between syslog lines and constructs succinct but valuable problem graphs, summarizing root causes and their locality, including cascading problems. We validate Log-Prophet using problem tickets and through operator interviews. To demonstrate the strength of Log-Prophet, we perform an initial longitudinal study of a large online service providers data center. Our study demonstrates that Log-Prophet significantly reduces the number of alerts while highlighting interesting operational issues.
Wireless Sensor Networks research and demand are now in full expansion, since people came to understand these are the key to a large number of issues in industry, commerce, home automation, healthcare, agriculture and environment, monitoring, public safety etc. One of the most challenging research problems in sensor networks research is power awareness and power-saving techniques. In this masters thesis, we have studied one particular power-saving technique, i.e. frequency scaling. In particular, we analysed the close relationship between clock frequencies in a microcontroller and several types of constraints imposed on these frequencies, e.g. by other components of the microcontroller, by protocol specifications, by external factors etc. Among these constraints, we were especially interested in the ones imposed by the timer service and by the serial ports transmission rates. Our efforts resulted in a microcontroller configuration management tool which aims at assisting application programmers in choosing microcontroller configurations, in function of the particular needs and constraints of their application.
Elastic optical network (EON) efficiently utilize spectral resources for optical fiber communication by allocating the minimum necessary bandwidth to client demands. On the other hand, network traffic has been continuously increasing due to the wide penetration of video streaming services, so the efficient and cost-effective use of available bandwidth plays an important role in improving service provisioning. In this work, we formulate and solve an optimization problem to perform routing and spectrum assignment (RSA) in EON with focus on video streaming. In this formulation, EON and video constraints such as spectrum fragmentation and received video quality are considered jointly. In this way, we utilize a machine learning (ML) technique to estimate the video quality versus channel state. The proposed algorithm is evaluated over two benchmarks fiber-optic network, namely NSFNET and US-backbone using numerical simulations based on random traffic models. The results reveal that the mean optical signal-to-noise ratio (OSNR) for video content data in the receiver is remarkably higher than in non-video data. This is while the blocking ratio is the same for both data types.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
