File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1111/j.1467-8659.2009.01554.x
- Scopus: eid_2-s2.0-71949116983
- WOS: WOS:000270778100005
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Linkless octree using multi-level perfect hashing
Title | Linkless octree using multi-level perfect hashing |
---|---|
Authors | |
Keywords | Computer Graphics [I.3.6]: Graphics data structures and data types— |
Issue Date | 2009 |
Publisher | Wiley-Blackwell Publishing Ltd.. The Journal's web site is located at http://www.wiley.com/bw/journal.asp?ref=0167-7055 |
Citation | Computer Graphics Forum: the international journal of the Eurographics Association, 2009, v. 28 n. 7, p. 1773-1780 How to Cite? |
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. |
Persistent Identifier | http://hdl.handle.net/10722/134617 |
ISSN | 2023 Impact Factor: 2.7 2023 SCImago Journal Rankings: 1.968 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Choi, MG | - |
dc.contributor.author | Ju, EJ | - |
dc.contributor.author | Chang, JW | - |
dc.contributor.author | Lee, JH | - |
dc.contributor.author | Kim, YJ | - |
dc.date.accessioned | 2011-06-28T04:52:23Z | - |
dc.date.available | 2011-06-28T04:52:23Z | - |
dc.date.issued | 2009 | - |
dc.identifier.citation | Computer Graphics Forum: the international journal of the Eurographics Association, 2009, v. 28 n. 7, p. 1773-1780 | - |
dc.identifier.issn | 0167-7055 | - |
dc.identifier.uri | http://hdl.handle.net/10722/134617 | - |
dc.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. | - |
dc.language | eng | - |
dc.publisher | Wiley-Blackwell Publishing Ltd.. The Journal's web site is located at http://www.wiley.com/bw/journal.asp?ref=0167-7055 | - |
dc.relation.ispartof | Computer Graphics Forum: the international journal of the Eurographics Association | - |
dc.rights | The definitive version is available at www3.interscience.wiley.com | - |
dc.subject | Computer Graphics [I.3.6]: Graphics data structures and data types— | - |
dc.title | Linkless octree using multi-level perfect hashing | en_US |
dc.type | Article | en_US |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0167-7055&volume=28&issue=7&spage=1773&epage=1780&date=2009&atitle=Linkless+octree+using+multi-level+perfect+hashing | - |
dc.identifier.email | Chang, JW: jungwoochang@gmail.com | - |
dc.description.nature | postprint | - |
dc.identifier.doi | 10.1111/j.1467-8659.2009.01554.x | - |
dc.identifier.scopus | eid_2-s2.0-71949116983 | - |
dc.identifier.hkuros | 182651 | - |
dc.identifier.volume | 28 | - |
dc.identifier.issue | 7 | - |
dc.identifier.spage | 1773 | - |
dc.identifier.epage | 1780 | - |
dc.identifier.isi | WOS:000270778100005 | - |
dc.identifier.citeulike | 6331010 | - |
dc.identifier.issnl | 0167-7055 | - |