• Login
    View Item 
    •   Eurographics DL Home
    • Computer Graphics Forum
    • Volume 32 (2013)
    • 32-Issue 3
    • View Item
    •   Eurographics DL Home
    • Computer Graphics Forum
    • Volume 32 (2013)
    • 32-Issue 3
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Maximum Entropy Summary Trees

    Thumbnail
    View/Open
    v32i3pp071-080.pdf (383.2Kb)
    0326-file1.pdf (2.437Mb)
    0326-file2.pdf (1.422Mb)
    0326-file3.pdf (162.9Kb)
    Date
    2013
    Author
    Karloff, Howard
    Shirley, Kenneth E.
    Pay-Per-View via TIB Hannover:

    Try if this item/paper is available.

    Metadata
    Show full item record
    Abstract
    Given a very large, node-weighted, rooted tree on, say, n nodes, if one has only enough space to display a knode summary of the tree, what is the most informative way to draw the tree? We define a type of weighted tree that we call a summary tree of the original tree that results from aggregating nodes of the original tree subject to certain constraints. We suggest that the best choice of which summary tree to use (among those with a fixed number of nodes) is the one that maximizes the information-theoretic entropy of a natural probability distribution associated with the summary tree, and we provide a (pseudopolynomial-time) dynamic-programming algorithm to compute this maximum entropy summary tree, when the weights are integral. The result is an automated way to summarize large trees and retain as much information about them as possible, while using (and displaying) only a fraction of the original node set. We illustrate the computation and use of maximum entropy summary trees on five real data sets whose weighted tree representations vary widely in structure. We also provide an additive approximation algorithm and a greedy heuristic that are faster than the optimal algorithm, and generalize to trees with real-valued weights.
    BibTeX
    @article {10.1111:cgf.12094,
    journal = {Computer Graphics Forum},
    title = {{Maximum Entropy Summary Trees}},
    author = {Karloff, Howard and Shirley, Kenneth E.},
    year = {2013},
    publisher = {The Eurographics Association and Blackwell Publishing Ltd.},
    ISSN = {1467-8659},
    DOI = {10.1111/cgf.12094}
    }
    URI
    http://dx.doi.org/10.1111/cgf.12094
    Collections
    • 32-Issue 3
    • EuroVis13: Eurographics Conference on Visualization

    Eurographics Association copyright © 2013 - 2020 
    Send Feedback | Contact - Imprint | Data Privacy Policy | Disable Google Analytics
    Theme by @mire NV
    System hosted at  Graz University of Technology.
    TUGFhA
     

     

    Browse

    All of Eurographics DLCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    BibTeX | TOC

    Create BibTeX Create Table of Contents

    Eurographics Association copyright © 2013 - 2020 
    Send Feedback | Contact - Imprint | Data Privacy Policy | Disable Google Analytics
    Theme by @mire NV
    System hosted at  Graz University of Technology.
    TUGFhA