Maintenance of multidimensional histograms

S. Muthukrishnan, Martin Strauss

    Research output: Chapter in Book/Report/Conference proceedingChapter

    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 languageEnglish (US)
    Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    EditorsParitosh K. Pandya, Jaikumar Radhakrishnan
    PublisherSpringer Verlag
    Pages352-362
    Number of pages11
    ISBN (Electronic)9783540206804
    DOIs
    StatePublished - 2003

    Publication series

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

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

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

    Cite this