Engineering succinct DOM

ABSTRACT

We describe the engineering of Succinct DOM (SDOM), a DOM implementation, written in C++, which is suitable for in-memory representation of large static XML documents. SDOM avoids the use of pointers, and is based upon succinct data structures, which use an information-theoretically minimum amount of space to represent an object.

SDOM gives a space-efficient in-memory representation, with stable and predictable memory usage. The space used by SDOM is an order of magnitude less than that used by a standard C++ DOM representation such as Xerces, but SDOM is extremely fast: navigation is in some cases faster than for a pointer-based representation such as Xerces (even for moderate-sized documents which can comfortably be loaded into main memory by Xerces).

A variant, SDOM-CT, applies bzip-based compression to textual and attribute data, and its space usage is comparable with "queryable" XML compressors. Some of these compressors support navigation and/or querying (e.g. subpath queries) of the compressed file. SDOM-CT does not support querying directly, but remains extremely fast: it is several orders of magnitude faster for navigation than queryable XML compressors that support navigation (and only a few times slower than say Xerces).

REFERENCES

• 1: Andrei Arion , Angela Bonifati , Ioana Manolescu , Andrea Pugliese, XQueC: A query-conscious compressed XML database, ACM Transactions on Internet Technology (TOIT), v.7 n.2, p.10-es, May 2007 [doi>10.1145/1239971.1239974]
• 2: Peter Boncz , Torsten Grust , Maurice van Keulen , Stefan Manegold , Jan Rittinger , Jens Teubner, MonetDB/XQuery: a fast XQuery processor powered by a relational engine, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142527]
• 3: BZip2. http://www.bzip.org.
• 4: Busatto, G., Lohrey, M., and Maneth, S. 2005. Efficient memory representation of XML documents. In Proc. Database Programming Languages, 10th International Symposium, DBPL 2005. Springer LNCS 3774, pp. 199--216. doi:10.1007/11601524_13
• 5: Cheng, J., Ng, W., 2004. XQzip: Querying compressed XML using structural indexing. In Proc. 9th International Conference on Extending Database Technology, EDBT '04. Springer LNCS 2992, pp. 219--236. doi:10.1007/b95855.
• 6: David R. Clark , J. Ian Munro, Efficient suffix trees on secondary storage, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.383-391, January 28-30, 1996, Atlanta, Georgia, United States
• 7: Delpratt, D., Rahman, N., and Raman, R. 2007. Compressed prefix sums. In Proc. Theory and Practice of Computer Science, SOFSEM '07. Springer LNCS 4362, pp. 235--247. doi:10.1007/978-3-540-69507-3_19.
• 8: Delpratt, D., Rahman, N., and Raman, R. 2006. Engineering the LOUDS succinct tree representation. In Proc.5^th Workshop on Experimental Algorithms, WEA '06. Springer LNCS 4007, pp. 134--145. doi:10.1007/11764298_12.
• 9: Paolo Ferragina , Giovanni Manzini, An experimental study of an opportunistic index, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.269-278, January 07-09, 2001, Washington, D.C., United States
• 10: P. Ferragina , F. Luccio , G. Manzini , S. Muthukrishnan, Compressing and searching XML data via two zips, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135891]
• 11: Richard F. Geary , Naila Rahman , Rajeev Raman , Venkatesh Raman, A simple optimal representation for balanced parentheses, Theoretical Computer Science, v.368 n.3, p.231-246, December, 2006 [doi>10.1016/j.tcs.2006.09.014]
• 12: Jacobson, G. 1989. Space-efficient static trees and graphs. In Proc. 30th Symp. Foundations of Computer Science, FOCS '89, pp. 549--554. doi:10.1109/SFCS.1989.63533
• 13: Kim, D. K., Na, J. C., Kim, J. E., and Park, K. 2005. Efficient implementation of rank and select functions for succinct representation. In Proc. 4^th Workshop on Experimental Algorithms, WEA 2005. Springer LNCS 3503, pp. 315--327. doi:10.1007/11427186_28.
• 14: Hartmut Liefke , Dan Suciu, XMill: an efficient compressor for XML data, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.153-164, May 15-18, 2000, Dallas, Texas, United States
• 15: Jun-Ki Min , Myung-Jae Park , Chin-Wan Chung, XPRESS: a queriable compression for XML data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872775]
• 16: J. Ian Munro , Venkatesh Raman, Succinct Representation of Balanced Parentheses and Static Trees, SIAM Journal on Computing, v.31 n.3, p.762-776, 2001 [doi>10.1137/S0097539799364092]
• 17: Mathias Neumüller , John N. Wilson, Improving XML Processing Using Adapted Data Structures, Revised Papers from the NODe 2002 Web and Database-Related Workshops on Web, Web-Services, and Database Systems, p.206-220, October 07-10, 2002
• 18: Wilfred Ng , Wai-Yeung Lam , Peter T. Wood , Mark Levene, XCQ: A queriable XML compression system, Knowledge and Information Systems, v.10 n.4, p.421-452, October 2006 [doi>10.1007/s10115-006-0012-z]
• 19: Raman, R. and Rao, S. S. 2003. Succinct dynamic dictionaries and trees. In Proc. ICALP 2003, Springer LNCS 2719, pp. 357--368.
• 20: Saxon. http://saxon.source.forge.net/
• 21: XGRIND: A Query-Friendly XML Compressor, Proceedings of the 18th International Conference on Data Engineering, p.225, February 26-March 01, 2002
• 22: Xerces C++ Parser. http://xerces.apache.org/xerces-c/
• 23: Xerces Java 2 Parser. http://xerces.apache.org/xerces2-j/
• 24: UW XML Repository. http://www.cs.washingon.edu/research/xmldatasets/www/repository.html
• 25: VOTable Documentation. http://www.us-vo.org/VOTable/
• 26: W3C DOM API documentation. 2004. http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/
• 27: W3C DOM Traversal, 2000. http://www.w3.org/TR/DOM-Level-2-Traversal-Range/traversal.html
• 28: Ning Zhang , Varun Kacholia , M. Tamer Özsu, A Succinct Physical Storage Scheme for Efficient Evaluation of Path Queries in XML, Proceedings of the 20th International Conference on Data Engineering, p.54, March 30-April 02, 2004