Show simple item record

dc.contributor.authorReinbold, Christianen_US
dc.contributor.authorWestermann, Rüdigeren_US
dc.contributor.editorBorgo, Rita and Marai, G. Elisabeta and Landesberger, Tatiana vonen_US
dc.date.accessioned2021-06-12T11:01:28Z
dc.date.available2021-06-12T11:01:28Z
dc.date.issued2021
dc.identifier.issn1467-8659
dc.identifier.urihttps://doi.org/10.1111/cgf.14294
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf14294
dc.description.abstractSummed Volume Tables (SVTs) allow one to compute integrals over the data values in any cubical area of a three-dimensional orthogonal grid in constant time, and they are especially interesting for building spatial search structures for sparse volumes. However, SVTs become extremely memory consuming due to the large values they need to store; for a dataset of n values an SVT requires O(nlogn) bits. The 3D Fenwick tree allows recovering the integral values in O(log3 n) time, at a memory consumption ofO(n) bits.We propose an algorithm that generates SVT representations that can flexibly trade speed for memory: From similar characteristics as SVTs, over equal memory consumption as 3D Fenwick trees at significantly lower computational complexity, to even further reduced memory consumption at the cost of raising computational complexity. For a 641x9601x9601 binary dataset, the algorithm can generate an SVT representation that requires 27.0 GB and 46 . 8 data fetch operations to retrieve an integral value, compared to 27.5 GB and 1521 . 8 fetches by 3D Fenwick trees, a decrease in fetches of 97%. A full SVT requires 247.6GB and 8 fetches per integral value. We present a novel hierarchical approach to compute and store intermediate prefix sums of SVTs, so that any prescribed memory consumption between O(n) bits and O(nlogn) bits is achieved. We evaluate the performance of the proposed algorithm in a number of examples considering large volume data, and we perform comparisons to existing alternatives.en_US
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectInformation systems
dc.subjectData structures
dc.subjectHuman centered computing
dc.subjectScientific visualization
dc.titleParameterized Splitting of Summed Volume Tablesen_US
dc.description.seriesinformationComputer Graphics Forum
dc.description.sectionheadersVolume and Vector Computing and Representation
dc.description.volume40
dc.description.number3
dc.identifier.doi10.1111/cgf.14294
dc.identifier.pages123-133


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

  • 40-Issue 3
    EuroVis 2021 - Conference Proceedings

Show simple item record