Optimal histograms for hierarchical range queries

Nick Koudas, S. Muthukrishnan, Divesh Srivastava

    Research output: Contribution to conferencePaperpeer-review

    Abstract

    Optimal histograms are computed for hierarchical range queries. It is shown that optimal histograms for equality queries are sub-optimal for hierarchical range queries. Polynomial time, dynamic programming algorithms are presented for computing optimal histograms that would provably minimize expected error for a given amount of space. The algorithm for the case of one-sided ranges is proved to be as efficient in running time as the V-optimal algorithm, which computes optimal histograms for equality series.

    Original languageEnglish (US)
    Pages196-204
    Number of pages9
    StatePublished - 2000
    EventPODS 2000 - 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems - Dallas, TX, USA
    Duration: May 15 2000May 17 2000

    Conference

    ConferencePODS 2000 - 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems
    CityDallas, TX, USA
    Period5/15/005/17/00

    ASJC Scopus subject areas

    • Software
    • Information Systems
    • Hardware and Architecture

    Fingerprint Dive into the research topics of 'Optimal histograms for hierarchical range queries'. Together they form a unique fingerprint.

    Cite this