Content area
Abstract
The field of data compression currently attracts tremendous interest due to the ever increasing and expanding use of digital data and products. Data compression is important because it reduces the storage and transmission requirements of digital data. But compressed digital data have to be decompressed in order to be processed. Due to advances in hardware, Content Addressable Memories (CAMs) are catching on and finding a niche in applications requiring fast searching of data. Quadtrees and octrees have been extensively used as a compact means of data representation, but also allow faster processing of data. CAMs have been shown to efficiently implement algorithms processing quadtree data in locational code representation. But given that currently available CAMs are of limited size, they can be overwhelmed by the size of quadtree and octree representations.
We present a new technique, called branch sharing, for compressing locational code representations of quadtree data for CAM processing. This technique achieves compression by combining two codes that differ in one trit position into a code with a "don't care" trit in this position. We introduce a fast CAM-based heuristic algorithm for branch sharing compression which reduces the CAM-based locational code representation to about a half of its size, on average. We extend this algorithm to deal with a limited CAM size, color quadtree and octree data.
We show that the problem of obtaining a minimum compressed representation by branch sharing is NP-complete and we present a suboptimal algorithm which achieves in practice, compression quite close to optimal. We then show how CAM quadtree algorithms can be used with compressed locational code data with minor changes and no significant degradation in speed. We show how a compressed locational code can be partially decompressed for use in quadtree algorithms that edit the tree. We illustrate, with a ray tracing application, how compressed quadtree data can improve the performance of algorithms that have to deal with limited CAM size, by reducing its reloading requirements. Finally, we present an arithmetic coding algorithm for post-compression of compressed quadtree data, for storage and transmission purposes.