Title :
Summarizing Order Statistics over Data Streams with Duplicates
Author :
Zhang, Ying ; Lin, Xuemin ; Yuan, Yidong ; Kitsuregawa, Masaru ; Zhou, Xiaofang ; Yu, Jeffrey Xu
Author_Institution :
New South Wale Univ.
Abstract :
In this paper, we investigated the problem of approximately processing rank queries against distinct data elements in a data stream with the presence of duplicated data elements. Novel space and time efficient techniques are developed for continuously maintaining order statistics so that rank queries can be answered with a relative error guarantee. This is the first work providing the space and time efficient data stream techniques to process approximate rank queries with relative error guarantees against distinct data elements.
Keywords :
approximation theory; query processing; statistics; data streams; duplicated data elements; order statistics summarization; rank queries approximation; rank queries processing; Data analysis; Data mining; Data structures; High-speed networks; Histograms; IP networks; Monitoring; Statistics; Stock markets; Tail;
Conference_Titel :
Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on
Conference_Location :
Istanbul
Print_ISBN :
1-4244-0802-4
Electronic_ISBN :
1-4244-0803-2
DOI :
10.1109/ICDE.2007.369004
