NDLI: Improving sketch reconstruction accuracy using linear least squares method

Please wait, while we are loading the content...

Measurement-based characterization of a collection of on-line games

A first look at modern enterprise traffic

Client behavior and feed characteristics of RSS, a publish-subscribe system for web micronews

Measurements, analysis, and modeling of BitTorrent-like systems

Characterizing unstructured overlay topologies in modern P2P file-sharing systems

Should internet service providers fear peer-assisted content distribution?

Joint data streaming and sampling techniques for detection of super sources and destinations

Optimal combination of sampled network measurements

The power of slicing in internet flow measurement

Poisson versus periodic path probing (or, does PASTA matter?)

On the accuracy of embeddings for internet coordinate systems

An empirical approach to modeling inter-AS traffic matrices

Geographic locality of IP prefixes

An information-theoretic approach to network monitoring and measurement

Multi-hop probing asymptotics in available bandwidth estimation: stochastic analysis

Exploiting internet route sharing for large scale available bandwidth estimation

Inferring and debugging path MTU discovery failures

Characterization and measurement of TCP traversal through NATs and firewalls

Predicting short-transfer latency from TCP arcana: a trace-based validation

Novel approaches to end-to-end packet reordering measurement

Data reduction for the scalable automated analysis of distributed darknet traffic

Sparse approximations for high fidelity compression of network traffic data

Building a time machine for efficient recording and retrieval of high-volume network traffic

Improving sketch reconstruction accuracy using linear least squares method

Understanding congestion in IEEE 802.11b wireless networks

Facilitating access point selection in IEEE 802.11 wireless networks

Eliminating handoff latencies in 802.11 WLANs using multiple radios: applications, experience, and evaluation

Estimation of link interference in static multi-hop wireless networks

Exploiting partially overlapping channels in wireless networks: turning a peril into an advantage

Network anomography

Combining filtering and statistical methods for anomaly detection

Detecting anomalies in network traffic using maximum entropy estimation

Exploiting underlying structure for detailed reconstruction of an internet-scale event

Collaborating against common enemies

Perils of transitive trust in the domain name system

Flooding attacks by exploiting persistent forwarding loops

Improving sketch reconstruction accuracy using linear least squares method

Content Provider	ACM Digital Library
Author	Yoon, Young Lee, Gene Moo Liu, Huiya Zhang, Yin
Abstract	Sketch is a sublinear space data structure that allows one to approximately reconstruct the value associated with any given key in an input data stream. It is the basis for answering a number of fundamental queries on data streams, such as range queries, finding quantiles, frequent items, etc. In the networking context, sketch has been applied to identifying heavy hitters and changes, which is critical for traffic monitoring, accounting, and network anomaly detection. In this paper, we propose a novel approach called lsquare to significantly improve the reconstruction accuracy of the sketch data structure. Given a sketch and a set of keys, we estimate the values associated with these keys by constructing a linear system and finding the optimal solution for the system using linear least squares method. We use a large amount of real Internet traffic data to evaluate lsquare against countmin, the state-of-the-art sketch scheme. Our results suggest that given the same memory requirement, lsquare achieves much better reconstruction accuracy than countmin. Alternatively, given the same reconstruction accuracy, lsquare requires significantly less memory. This clearly demonstrates the effectiveness of our approach.
Starting Page	24
Ending Page	24
Page Count	1
File Format	PDF
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-10-19
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Improving sketch reconstruction accuracy using linear least squares method (2005)

Improving Sketch Reconstruction Accuracy Using Linear Least Squares Method (2005)

Improving generalization in the XCSF classifier system using linear least-squares

Fast High-Resolution Image Reconstruction Using Tikhonov Regularization Based Total Least Squares

Study on the technology of quadric surface extracting base on least square method

Proximity of Weighted and Layered Least Squares Solutions

Orthogonal Least Squares in Partition of Unity Surface Reconstruction with Radial Basis Function

An Efficient Method to Mesh Point Cloud

Evaluation of a direct 4D reconstruction method using generalised linear least squares for estimating nonlinear micro-parametric maps

Improving sketch reconstruction accuracy using linear least squares method

Similar Documents

Improving sketch reconstruction accuracy using linear least squares method (2005)

Improving Sketch Reconstruction Accuracy Using Linear Least Squares Method (2005)

Improving generalization in the XCSF classifier system using linear least-squares

Fast High-Resolution Image Reconstruction Using Tikhonov Regularization Based Total Least Squares

Study on the technology of quadric surface extracting base on least square method

Proximity of Weighted and Layered Least Squares Solutions

Orthogonal Least Squares in Partition of Unity Surface Reconstruction with Radial Basis Function

An Efficient Method to Mesh Point Cloud

Evaluation of a direct 4D reconstruction method using generalised linear least squares for estimating nonlinear micro-parametric maps

Improving sketch reconstruction accuracy using linear least squares method