NDLI: Sketching asynchronous data streams over sliding windows

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

Sketching asynchronous data streams over sliding windows

Content Provider	Springer Nature Link
Author	Xu, Bojian Tirthapura, Srikanta Busch, Costas
Copyright Year	2007
Abstract	We study the problem of maintaining a sketch of recent elements of a data stream. Motivated by applications involving network data, we consider streams that are asynchronous, in which the observed order of data is not the same as the time order in which the data was generated. The notion of recent elements of a stream is modeled by the sliding timestamp window, which is the set of elements with timestamps that are close to the current time. We design algorithms for maintaining sketches of all elements within the sliding timestamp window that can give provably accurate estimates of two basic aggregates, the sum and the median, of a stream of numbers. The space taken by the sketches, the time needed for querying the sketch, and the time for inserting new elements into the sketch are all polylogarithmic with respect to the maximum window size. Our sketches can be easily combined in a lossless and compact way, making them useful for distributed computations over data streams. Previous works on sketching recent elements of a data stream have all considered the more restrictive scenario of synchronous streams, where the observed order of data is the same as the time order in which the data was generated. Our notion of recency of elements is more general than that studied in previous work, and thus our sketches are more robust to network delays and asynchrony.
Starting Page	359
Ending Page	374
Page Count	16
File Format	PDF
ISSN	01782770
Journal	Distributed Computing
Volume Number	20
Issue Number	5
e-ISSN	14320452
Language	English
Publisher	Springer-Verlag
Publisher Date	2007-11-06
Publisher Place	Berlin/Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Data streams Asynchronous streams Distributed streams Sliding window Sum Median Theory of Computation Software Engineering/Programming and Operating Systems Computer Systems Organization and Communication Networks Computer Hardware Computer Communication Networks
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computer Networks and Communications Computational Theory and Mathematics Hardware and Architecture

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

Sketching asynchronous streams over a sliding window

Lower bounds for asynchronous consensus

Distributed data clustering in sensor networks

Beeping a maximal independent set

Efficient distributed computation of distance sketches in networks

Concurrent Maintenance of Rings

Distributed processing of continuous sliding-window k-NN queries for data stream filtering

Gathering on rings under the Look–Compute–Move model

Distributed transactional memory for metric-space networks

Sketching asynchronous data streams over sliding windows

Similar Documents

Sketching asynchronous streams over a sliding window

Lower bounds for asynchronous consensus

Distributed data clustering in sensor networks

Beeping a maximal independent set

Efficient distributed computation of distance sketches in networks

Concurrent Maintenance of Rings

Distributed processing of continuous sliding-window k-NN queries for data stream filtering

Gathering on rings under the Look–Compute–Move model

Distributed transactional memory for metric-space networks

Sketching asynchronous data streams over sliding windows