Estimating rarity and similarity over data stream windows

Mayur Datar; S. Muthukrishnan

doi:10.1007/3-540-45749-6_31

Estimating rarity and similarity over data stream windows

Mayur Datar, S. Muthukrishnan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In the windowed data stream model, we observe items coming in over time. At any time t, we consider the window of the last N observations a_t-(N-1), a_t-(N-2),…, a_t, each a_i Є{1,…, u}; we are required to support queries about the data in the window. A crucial restriction is that we are only allowed o(N) (often polylogarithmic in N) storage space, so not all items within the window can be archived. We study two basic problems in the windowed data stream model. The first is the estimation of the rarity of items in the window. Our second problem is one of estimating similarity between two data stream windows using the Jacard’s coefficient. The problems of estimating rarity and similarity have many applications in mining massive data sets. We present novel, simple algorithms for estimating rarity and similarity on windowed data streams, accurate up to factor 1 ± e using space only logarithmic in the window size.

Original language	English (US)
Title of host publication	Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
Editors	Rolf Möhring, Rajeev Raman
Publisher	Springer Verlag
Pages	323-335
Number of pages	13
ISBN (Electronic)	3540441808, 9783540441809
DOIs	https://doi.org/10.1007/3-540-45749-6_31
State	Published - 2002
Event	10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy Duration: Sep 17 2002 → Sep 21 2002

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2461
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	10th Annual European Symposium on Algorithms, ESA 2002
Country/Territory	Italy
City	Rome
Period	9/17/02 → 9/21/02

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-45749-6_31

Cite this

Datar, M., & Muthukrishnan, S. (2002). Estimating rarity and similarity over data stream windows. In R. Möhring, & R. Raman (Eds.), Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings (pp. 323-335). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2461). Springer Verlag. https://doi.org/10.1007/3-540-45749-6_31

Estimating rarity and similarity over data stream windows. / Datar, Mayur; Muthukrishnan, S.
Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. ed. / Rolf Möhring; Rajeev Raman. Springer Verlag, 2002. p. 323-335 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2461).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Datar, M & Muthukrishnan, S 2002, Estimating rarity and similarity over data stream windows. in R Möhring & R Raman (eds), Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2461, Springer Verlag, pp. 323-335, 10th Annual European Symposium on Algorithms, ESA 2002, Rome, Italy, 9/17/02. https://doi.org/10.1007/3-540-45749-6_31

Datar M, Muthukrishnan S. Estimating rarity and similarity over data stream windows. In Möhring R, Raman R, editors, Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. Springer Verlag. 2002. p. 323-335. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45749-6_31

Datar, Mayur ; Muthukrishnan, S. / Estimating rarity and similarity over data stream windows. Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. editor / Rolf Möhring ; Rajeev Raman. Springer Verlag, 2002. pp. 323-335 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0c8ebdd56b6f42b6963b3325625248f1,

title = "Estimating rarity and similarity over data stream windows",

abstract = "In the windowed data stream model, we observe items coming in over time. At any time t, we consider the window of the last N observations at-(N-1), at-(N-2),…, at, each ai Є{1,…, u}; we are required to support queries about the data in the window. A crucial restriction is that we are only allowed o(N) (often polylogarithmic in N) storage space, so not all items within the window can be archived. We study two basic problems in the windowed data stream model. The first is the estimation of the rarity of items in the window. Our second problem is one of estimating similarity between two data stream windows using the Jacard{\textquoteright}s coefficient. The problems of estimating rarity and similarity have many applications in mining massive data sets. We present novel, simple algorithms for estimating rarity and similarity on windowed data streams, accurate up to factor 1 ± e using space only logarithmic in the window size.",

author = "Mayur Datar and S. Muthukrishnan",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 10th Annual European Symposium on Algorithms, ESA 2002 ; Conference date: 17-09-2002 Through 21-09-2002",

year = "2002",

doi = "10.1007/3-540-45749-6_31",

language = "English (US)",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "323--335",

editor = "Rolf M{\"o}hring and Rajeev Raman",

booktitle = "Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings",

}

TY - GEN

T1 - Estimating rarity and similarity over data stream windows

AU - Datar, Mayur

AU - Muthukrishnan, S.

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

N2 - In the windowed data stream model, we observe items coming in over time. At any time t, we consider the window of the last N observations at-(N-1), at-(N-2),…, at, each ai Є{1,…, u}; we are required to support queries about the data in the window. A crucial restriction is that we are only allowed o(N) (often polylogarithmic in N) storage space, so not all items within the window can be archived. We study two basic problems in the windowed data stream model. The first is the estimation of the rarity of items in the window. Our second problem is one of estimating similarity between two data stream windows using the Jacard’s coefficient. The problems of estimating rarity and similarity have many applications in mining massive data sets. We present novel, simple algorithms for estimating rarity and similarity on windowed data streams, accurate up to factor 1 ± e using space only logarithmic in the window size.

AB - In the windowed data stream model, we observe items coming in over time. At any time t, we consider the window of the last N observations at-(N-1), at-(N-2),…, at, each ai Є{1,…, u}; we are required to support queries about the data in the window. A crucial restriction is that we are only allowed o(N) (often polylogarithmic in N) storage space, so not all items within the window can be archived. We study two basic problems in the windowed data stream model. The first is the estimation of the rarity of items in the window. Our second problem is one of estimating similarity between two data stream windows using the Jacard’s coefficient. The problems of estimating rarity and similarity have many applications in mining massive data sets. We present novel, simple algorithms for estimating rarity and similarity on windowed data streams, accurate up to factor 1 ± e using space only logarithmic in the window size.

UR - http://www.scopus.com/inward/record.url?scp=84938057127&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84938057127&partnerID=8YFLogxK

U2 - 10.1007/3-540-45749-6_31

DO - 10.1007/3-540-45749-6_31

M3 - Conference contribution

AN - SCOPUS:84938057127

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 323

EP - 335

BT - Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings

A2 - Möhring, Rolf

A2 - Raman, Rajeev

PB - Springer Verlag

T2 - 10th Annual European Symposium on Algorithms, ESA 2002

Y2 - 17 September 2002 through 21 September 2002

ER -

Estimating rarity and similarity over data stream windows

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this