NDLI: Space-efficient Relative Error Order Sketch over Data Streams

Content Provider	IEEE Xplore Digital Library
Author	Ying Zhang Xuemin Lin Jian Xu Korn, F. Wei Wang
Copyright Year	2006
Description	Author affiliation: University of New South Wales (Ying Zhang)
Abstract	We consider the problem of continuously maintaining order sketches over data streams with a relative rank error guarantee ∊. Novel space-efficient and one-scan randomised techniques are developed. Our first randomised algorithm can guarantee such a relative error precision ∊ with confidence 1 - \delta using O( 1\_ \in \frac{1} {2}2 log 1d log ∊^2N) space, where N is the number of data elements seen so far in a data stream. Then, a new one-scan space compression technique is developed. Combined with the first randomised algorithm, the one-scan space compression technique yields another one-scan randomised algorithm that guarantees the space requirement is O( 1\frac{1} { \in } log(1\frac{1}{ \in } log 1\begin{gathered} \frac{1}{\delta } \hfill \\ \hfill \\ \end{gathered} )\frac{{\log ^{2 + \alpha } \in N}} {{1 - 1/2^\alpha }} (for\alpha \gt 0) on average while the worst case space remains O( \frac{1}{{ \in ^2 }}\log \frac{1} {\delta }\log \in ^2 N). These results are immediately applicable to approximately computing quantiles over data streams with a relative error guarantee \in and significantly improve the previous best space bound O( \frac{1} {{ \in ^3 }}\log \frac{1}{\delta }\log N). Our extensive experiment results demonstrate that both techniques can support an on-line computation against high speed data streams.
Starting Page	51
Ending Page	51
File Size	483625
Page Count	1
File Format	PDF
ISBN	0769525709
DOI	10.1109/ICDE.2006.145
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2006-04-03
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computer networks Statistical distributions Data mining Statistical analysis Distributed computing Stock markets Error analysis High-speed networks Computer network management Data analysis
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

Duplicate-Insensitive Order Statistics Computation over Data Streams

Space-efficient relative error order sketch over data streams (2006)

Space-efficient relative error order sketch over data streams (2006)

Summarizing Order Statistics over Data Streams with Duplicates

Space-efficient relative error order sketch over data streams (2006)

A frame for mining time-space rules from distributed transaction database

Mining for Core Patterns in Stock Market Data

An Efficient Algorithm for Mining Frequent Patterns over High Speed Data Streams

When local isn't enough: extracting distributed rules from networks

Space-efficient Relative Error Order Sketch over Data Streams

Similar Documents

Duplicate-Insensitive Order Statistics Computation over Data Streams

Space-efficient relative error order sketch over data streams (2006)

Space-efficient relative error order sketch over data streams (2006)

Summarizing Order Statistics over Data Streams with Duplicates

Space-efficient relative error order sketch over data streams (2006)

A frame for mining time-space rules from distributed transaction database

Mining for Core Patterns in Stock Market Data

An Efficient Algorithm for Mining Frequent Patterns over High Speed Data Streams

When local isn't enough: extracting distributed rules from networks

Space-efficient Relative Error Order Sketch over Data Streams