A quadtree dictionary approach to multi-resolution compression

ABSTRACT

As we attempt to harness the power of tomorrow's mobile devices, intelligent information delivery becomes a primary concern. Getting the appropriate data to the resources that need it is referred to as the needs mismatch problem. In this paper we present a lossless multi-resolution compression technique based on a quadtree dictionary (QTD) that achieves 8:1 compression in the worst case. Test results show our method improves upon probabilistic, wavelet, and tree reduction techniques while providing 54:1 compression in the average case.

REFERENCES

• 1: Dooley, A. Chatterjee, "Mobile ISAW." in Proceedings of the 1st Annual International Conference on Web Service, ICWS '03, June 23--26, Las Vegas, NV, CSREA Press 2003, pages 359--364.
• 2: Minos and Gibbons. Approximate Query Processing: Taming the Terabytes. VLDB 2001. Roma, Italy, September 2001. Available at <u>http://www.belllabs.com/user/minos/Talks/vldb01-tutorial.ppt.</u>
• 3: Anil K. Jain , Robert P. W. Duin , Jianchang Mao, Statistical Pattern Recognition: A Review, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.1, p.4-37, January 2000 [doi>10.1109/34.824819]
• 4: Olken, Frank. "Random Sampling from Databases." PhD Dissertation. University of California at Berkeley. 1993. Available at: <u>http://citeseer.nj.nec.com/cache/papers/cs/7292/http:zSzzSzwww.unfortu.netzSzpubzSzdbzSzpostgreszSzpaperszSzUCBPhD-olken.pdf/olken93random.pdf.</u>
• 5: Telephone Interview, Art Schultz of IPNS, Argonne National Lab. March 10, 2003.
• 6: Kopp, M., Lossless Wavelet Based Image Compression with Adaptive 2D Decomposition, Proceedings of the Fourth International Conference in Central Europe on Computer Graphics and Visualization 96 (WSCG96), pp. 141--149, Plzen, 1996. Available at: <u>http://www.cg.tuwien.ac.at/research/TR/95/TR-186-2-95-11Abstract.html.</u>
• 7: Polikar, Robi. "The Wavelet Tutorial." Iowa State University, 2000. Available at <u>http://engineering.rowan.edu/~polikar/WAVELETS/Wttutorial.html.</u>
• 8: Eric J. Stollnitz , Tony D. DeRose , David H. Salesin, Wavelets for Computer Graphics: A Primer, Part 1, IEEE Computer Graphics and Applications, v.15 n.3, p.76-84, May 1995 [doi>10.1109/38.376616]
• 9: Linda Yang , Manavendra Misra, Coarse-Grained Parallel Algorithms for Multi-DimensionalWavelet Transforms, The Journal of Supercomputing, v.12 n.1-2, p.99-118, Jan./Feb., 1998 [doi>10.1023/A:1007985629329]
• 10: Ole Moller Nielsen. Parallel Performance of Fast Wavelet Transforms. International Journal of High Speed Computing, June 2000. Available at <u>http://www.imm.dtu.dk/~omni/parwave.pdf.</u>
• 11: Ashfaq A. Khokhar , Gerd Heber , Parimala Thulasiraman , Guang R. Gao, Load Adaptive Algorithms and Implementations for the 2D Discrete Wavelet Transform on Fine-Grain Multithreaded Architectures, Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, p.458-462, April 12-16, 1999
• 12: R. Lang, A. Spray. "The 2D Wavelet Transform on a Massively Parallel Machine". Proceedings of the Second Australasian Conference on Parallel and Real-Time Systems (PART'95), Perth, September 1995, pages 325--332. Available at: <u>http://murray.newcastle.edu.au/users/visitors/RobertL/www/files/maspar.ps.gz.</u>
• 13: Dmitriy V. Pinskiy , Joerg Meyer , Bernd Hamann , Kenneth I. Joy , Eric Brugger , Mark Duchaineau, A hierarchical error controlled octree data structure for large-scale visualization, Crossroads, v.6 n.3, p.26-31, Spring 2000 [doi>10.1145/331624.331633]
• 14: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 15: J. Ziv and A. Lempel, "A Universal Algorithm for Sequential Data Compression," IEEE Transactions on Information Theory, Vol. 23, pp. 337--342, 1977.
• 16: Rion Dooley, A Distributed Quadtree Dictionary Approach to Multi-Resolution Compression, Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'04) Volume 2, p.155, April 05-07, 2004

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

General Terms:
Algorithms

Keywords:
compression, dictionary, needs mismatch, quadtree