NDLI: Efficiently Summarizing Data Streams over Sliding Windows

Content Provider	IEEE Xplore Digital Library
Author	Rivetti, N. Busnel, Y. Mostefaoui, A.
Copyright Year	2015
Description	Author affiliation: Crest, Inria, Rennes, France (Busnel, Y.) \|\| LINA, Univ. de Nantes, Nantes, France (Rivetti, N.; Mostefaoui, A.)
Abstract	Estimating the frequency of any piece of information in large-scale distributed data streams became of utmost importance in the last decade (e.g., in the context of network monitoring, big data, etc.). If some elegant solutions have been proposed recently, their approximation is computed from the inception of the stream. In a runtime distributed context, one would prefer to gather information only about the recent past. This may be led by the need to save resources or by the fact that recent information is more relevant. In this paper, we consider the sliding window model and propose two different (on-line) algorithms that approximate the items frequency in the active window. More precisely, we determine a (ε, δ)-additive-approximation meaning that the error is greater than ε only with probability δ. These solutions use a very small amount of memory with respect to the size N of the window and the number n of distinct items of the stream, namely, O(1/ε log 1/δ (log N+log n)) and O(1/τε log 1/δ (log N+log n)) bits of space, where τ is a parameter limiting memory usage. We also provide their distributed variant, i.e., considering the sliding window functional monitoring model. We compared the proposed algorithms to each other and also to the state of the art through extensive experiments on synthetic traces and real data sets that validate the robustness and accuracy of our algorithms.
Starting Page	151
Ending Page	158
File Size	333868
Page Count	8
File Format	PDF
e-ISBN	9781509018499
DOI	10.1109/NCA.2015.46
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-09-28
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computational modeling Frequency estimation Complexity theory Estimation Approximation methods Data models Monitoring randomized approximation algorithm data stream windowing model frequency estimation
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

Efficiently Summarizing Distributed Data Streams over Sliding Windows

Efficiently Summarizing Distributed Data Streams over Sliding Windows

Estimating the Frequency of Data Items in Massive Distributed Streams

Efficiently Summarizing Distributed Data Streams over Sliding Windows

An Information Divergence Estimation over Data Streams

Maintaining Stream Statistics over Sliding Windows

Variance estimation over sliding windows

Density-Based Data Streams Subspace Clustering over Weighted Sliding Windows

A Distributed Information Divergence Estimation over Data Streams

Efficiently Summarizing Data Streams over Sliding Windows

Similar Documents

Efficiently Summarizing Distributed Data Streams over Sliding Windows

Efficiently Summarizing Distributed Data Streams over Sliding Windows

Estimating the Frequency of Data Items in Massive Distributed Streams

Efficiently Summarizing Distributed Data Streams over Sliding Windows

An Information Divergence Estimation over Data Streams

Maintaining Stream Statistics over Sliding Windows

Variance estimation over sliding windows

Density-Based Data Streams Subspace Clustering over Weighted Sliding Windows

A Distributed Information Divergence Estimation over Data Streams

Efficiently Summarizing Data Streams over Sliding Windows