Maintenance of multidimensional histograms

S. Muthukrishnan; Martin Strauss

doi:10.1007/978-3-540-24597-1_30

Maintenance of multidimensional histograms

S. Muthukrishnan, Martin Strauss

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

Abstract

We present a space- and time- efficient algorithm for maintaining multidimensional histograms for data that is dynamic, i.e., subject to updates that may be increments or decrements. Both space used as well as per-update and computing times are polylogarithmic in the input data size; this is the first known algorithm in the data stream model for this problem with this property. One of the powerful motivation for studying data stream algorithms is in analyzing traffic log from IP networks where d-dimensional data (for small d) is common. Hence, our results are of great interest. The result itself is achieved by generalizing methods known for maintenance of unidimensional histograms under updates - finding significant tensor generalizations of one dimensional wavelets, approximating distributions by robust representations - and relationships amongst histograms such as those between tensor wavelets or hierarchical histograms and general histograms.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Paritosh K. Pandya, Jaikumar Radhakrishnan
Publisher	Springer Verlag
Pages	352-362
Number of pages	11
ISBN (Electronic)	9783540206804
DOIs	https://doi.org/10.1007/978-3-540-24597-1_30
State	Published - 2003

Publication series

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

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-24597-1_30

Fingerprint Dive into the research topics of 'Maintenance of multidimensional histograms'. Together they form a unique fingerprint.

Cite this

Muthukrishnan, S., & Strauss, M. (2003). Maintenance of multidimensional histograms. In P. K. Pandya, & J. Radhakrishnan (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 352-362). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2914). Springer Verlag. https://doi.org/10.1007/978-3-540-24597-1_30

Maintenance of multidimensional histograms. / Muthukrishnan, S.; Strauss, Martin.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Paritosh K. Pandya; Jaikumar Radhakrishnan. Springer Verlag, 2003. p. 352-362 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2914).

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

Muthukrishnan, S & Strauss, M 2003, Maintenance of multidimensional histograms. in PK Pandya & J Radhakrishnan (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2914, Springer Verlag, pp. 352-362. https://doi.org/10.1007/978-3-540-24597-1_30

Muthukrishnan S, Strauss M. Maintenance of multidimensional histograms. In Pandya PK, Radhakrishnan J, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 352-362. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-540-24597-1_30

Muthukrishnan, S. ; Strauss, Martin. / Maintenance of multidimensional histograms. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Paritosh K. Pandya ; Jaikumar Radhakrishnan. Springer Verlag, 2003. pp. 352-362 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{39ede4c13cd14a19b169ebd5eeddb617,

title = "Maintenance of multidimensional histograms",

abstract = "We present a space- and time- efficient algorithm for maintaining multidimensional histograms for data that is dynamic, i.e., subject to updates that may be increments or decrements. Both space used as well as per-update and computing times are polylogarithmic in the input data size; this is the first known algorithm in the data stream model for this problem with this property. One of the powerful motivation for studying data stream algorithms is in analyzing traffic log from IP networks where d-dimensional data (for small d) is common. Hence, our results are of great interest. The result itself is achieved by generalizing methods known for maintenance of unidimensional histograms under updates - finding significant tensor generalizations of one dimensional wavelets, approximating distributions by robust representations - and relationships amongst histograms such as those between tensor wavelets or hierarchical histograms and general histograms.",

author = "S. Muthukrishnan and Martin Strauss",

year = "2003",

doi = "10.1007/978-3-540-24597-1_30",

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 = "352--362",

editor = "Pandya, {Paritosh K.} and Jaikumar Radhakrishnan",

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

}

TY - CHAP

T1 - Maintenance of multidimensional histograms

AU - Muthukrishnan, S.

AU - Strauss, Martin

PY - 2003

Y1 - 2003

N2 - We present a space- and time- efficient algorithm for maintaining multidimensional histograms for data that is dynamic, i.e., subject to updates that may be increments or decrements. Both space used as well as per-update and computing times are polylogarithmic in the input data size; this is the first known algorithm in the data stream model for this problem with this property. One of the powerful motivation for studying data stream algorithms is in analyzing traffic log from IP networks where d-dimensional data (for small d) is common. Hence, our results are of great interest. The result itself is achieved by generalizing methods known for maintenance of unidimensional histograms under updates - finding significant tensor generalizations of one dimensional wavelets, approximating distributions by robust representations - and relationships amongst histograms such as those between tensor wavelets or hierarchical histograms and general histograms.

AB - We present a space- and time- efficient algorithm for maintaining multidimensional histograms for data that is dynamic, i.e., subject to updates that may be increments or decrements. Both space used as well as per-update and computing times are polylogarithmic in the input data size; this is the first known algorithm in the data stream model for this problem with this property. One of the powerful motivation for studying data stream algorithms is in analyzing traffic log from IP networks where d-dimensional data (for small d) is common. Hence, our results are of great interest. The result itself is achieved by generalizing methods known for maintenance of unidimensional histograms under updates - finding significant tensor generalizations of one dimensional wavelets, approximating distributions by robust representations - and relationships amongst histograms such as those between tensor wavelets or hierarchical histograms and general histograms.

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

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

U2 - 10.1007/978-3-540-24597-1_30

DO - 10.1007/978-3-540-24597-1_30

M3 - Chapter

AN - SCOPUS:35248872007

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

SP - 352

EP - 362

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

A2 - Pandya, Paritosh K.

A2 - Radhakrishnan, Jaikumar

PB - Springer Verlag

ER -