File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: Linkless octree using multi-level perfect hashing
  • Basic View
  • Metadata View
  • XML View
TitleLinkless octree using multi-level perfect hashing
 
AuthorsChoi, MG3
Ju, EJ
Chang, JW2
Lee, JH
Kim, YJ1
 
KeywordsComputer Graphics [I.3.6]: Graphics data structures and data types—
 
Issue Date2009
 
PublisherWiley-Blackwell Publishing Ltd.. The Journal's web site is located at http://www.wiley.com/bw/journal.asp?ref=0167-7055
 
CitationComputer Graphics Forum: the international journal of the Eurographics Association, 2009, v. 28 n. 7, p. 1773-1780 [How to Cite?]
DOI: http://dx.doi.org/10.1111/j.1467-8659.2009.01554.x
 
AbstractThe standard C/C++ implementation of a spatial partitioning data structure, such as octree and quadtree, is often inefficient in terms of storage requirements particularly when the memory overhead for maintaining parent-to-child pointers is significant with respect to the amount of actual data in each tree node. In this work, we present a novel data structure that implements uniform spatial partitioning without storing explicit parent-to-child pointer links. Our linkless tree encodes the storage locations of subdivided nodes using perfect hashing while retaining important properties of uniform spatial partitioning trees, such as coarse-to-fine hierarchical representation, efficient storage usage, and efficient random accessibility. We demonstrate the performance of our linkless trees using image compression and path planning examples.
 
ISSN0167-7055
2013 Impact Factor: 1.595
 
DOIhttp://dx.doi.org/10.1111/j.1467-8659.2009.01554.x
 
DC FieldValue
dc.contributor.authorChoi, MG
 
dc.contributor.authorJu, EJ
 
dc.contributor.authorChang, JW
 
dc.contributor.authorLee, JH
 
dc.contributor.authorKim, YJ
 
dc.date.accessioned2011-06-28T04:52:23Z
 
dc.date.available2011-06-28T04:52:23Z
 
dc.date.issued2009
 
dc.description.abstractThe standard C/C++ implementation of a spatial partitioning data structure, such as octree and quadtree, is often inefficient in terms of storage requirements particularly when the memory overhead for maintaining parent-to-child pointers is significant with respect to the amount of actual data in each tree node. In this work, we present a novel data structure that implements uniform spatial partitioning without storing explicit parent-to-child pointer links. Our linkless tree encodes the storage locations of subdivided nodes using perfect hashing while retaining important properties of uniform spatial partitioning trees, such as coarse-to-fine hierarchical representation, efficient storage usage, and efficient random accessibility. We demonstrate the performance of our linkless trees using image compression and path planning examples.
 
dc.description.naturepostprint
 
dc.identifier.citationComputer Graphics Forum: the international journal of the Eurographics Association, 2009, v. 28 n. 7, p. 1773-1780 [How to Cite?]
DOI: http://dx.doi.org/10.1111/j.1467-8659.2009.01554.x
 
dc.identifier.citeulike6331010
 
dc.identifier.doihttp://dx.doi.org/10.1111/j.1467-8659.2009.01554.x
 
dc.identifier.epage1780
 
dc.identifier.hkuros182651
 
dc.identifier.issn0167-7055
2013 Impact Factor: 1.595
 
dc.identifier.issue7
 
dc.identifier.openurl
 
dc.identifier.scopuseid_2-s2.0-71949116983
 
dc.identifier.spage1773
 
dc.identifier.urihttp://hdl.handle.net/10722/134617
 
dc.identifier.volume28
 
dc.languageeng
 
dc.publisherWiley-Blackwell Publishing Ltd.. The Journal's web site is located at http://www.wiley.com/bw/journal.asp?ref=0167-7055
 
dc.relation.ispartofComputer Graphics Forum: the international journal of the Eurographics Association
 
dc.rightsThe definitive version is available at www3.interscience.wiley.com
 
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License
 
dc.subjectComputer Graphics [I.3.6]: Graphics data structures and data types—
 
dc.titleLinkless octree using multi-level perfect hashing
 
dc.typeArticle
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Choi, MG</contributor.author>
<contributor.author>Ju, EJ</contributor.author>
<contributor.author>Chang, JW</contributor.author>
<contributor.author>Lee, JH</contributor.author>
<contributor.author>Kim, YJ</contributor.author>
<date.accessioned>2011-06-28T04:52:23Z</date.accessioned>
<date.available>2011-06-28T04:52:23Z</date.available>
<date.issued>2009</date.issued>
<identifier.citation>Computer Graphics Forum: the international journal of the Eurographics Association, 2009, v. 28 n. 7, p. 1773-1780</identifier.citation>
<identifier.issn>0167-7055</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/134617</identifier.uri>
<description.abstract>The standard C/C++ implementation of a spatial partitioning data structure, such as octree and quadtree, is often inefficient in terms of storage requirements particularly when the memory overhead for maintaining parent-to-child pointers is significant with respect to the amount of actual data in each tree node. In this work, we present a novel data structure that implements uniform spatial partitioning without storing explicit parent-to-child pointer links. Our linkless tree encodes the storage locations of subdivided nodes using perfect hashing while retaining important properties of uniform spatial partitioning trees, such as coarse-to-fine hierarchical representation, efficient storage usage, and efficient random accessibility. We demonstrate the performance of our linkless trees using image compression and path planning examples.</description.abstract>
<language>eng</language>
<publisher>Wiley-Blackwell Publishing Ltd.. The Journal&apos;s web site is located at http://www.wiley.com/bw/journal.asp?ref=0167-7055</publisher>
<relation.ispartof>Computer Graphics Forum: the international journal of the Eurographics Association</relation.ispartof>
<rights>The definitive version is available at www3.interscience.wiley.com</rights>
<rights>Creative Commons: Attribution 3.0 Hong Kong License</rights>
<subject>Computer Graphics [I.3.6]: Graphics data structures and data types&#8212;</subject>
<title>Linkless octree using multi-level perfect hashing</title>
<type>Article</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=0167-7055&amp;volume=28&amp;issue=7&amp;spage=1773&amp;epage=1780&amp;date=2009&amp;atitle=Linkless+octree+using+multi-level+perfect+hashing</identifier.openurl>
<description.nature>postprint</description.nature>
<identifier.doi>10.1111/j.1467-8659.2009.01554.x</identifier.doi>
<identifier.scopus>eid_2-s2.0-71949116983</identifier.scopus>
<identifier.hkuros>182651</identifier.hkuros>
<identifier.volume>28</identifier.volume>
<identifier.issue>7</identifier.issue>
<identifier.spage>1773</identifier.spage>
<identifier.epage>1780</identifier.epage>
<identifier.citeulike>6331010</identifier.citeulike>
<bitstream.url>http://hub.hku.hk/bitstream/10722/134617/2/content.pdf</bitstream.url>
</item>
Author Affiliations
  1. Ewha Womans University
  2. The University of Hong Kong
  3. Seoul National University