582410 Processing of large document collections, Exercise 6

The solutions should be ready for inspection by Thursday 8.11.2001 (midnight).

The exercises are based on the article: Liefke, Suciu: XMill: an efficient compressor for XML data [ACM Digital Library] [Local copy (PDF)]. Published in Proceedings of the 2000 ACM SIGMOD on Management of data.

1. Summarize the compression method described in the paper. Consider, at least, the following points:

   • What is the motivation of the method? Why XML data needs special compression methods?

   • What are the benefits and limitations of the method? Is the method particularly suitable for some special type of XML data?

   • What are the main ideas to achieve compression?

2. Explain the method more detailly using the sample XML document below.

   • Describe the architecture.

   • Describe the main points of sections 4.1-4.3 giving examples using the sample below.

<departments>
<department>
<name>Department of Aesthetics</name>  
<address><box>PL 3</box><street><name>Fabianinkatu</name><number>33</number></street>
<city><zip>00014</zip><name>University of Helsinki</name></city>
</address> 
<fax>19123079</fax> 
<chair><name>Arto Haapala</name></chair>
</department>
<department>
<name>Department of Agricultural Engineering</name>
<address><box>PL 27</box><street><name>Latokartanonkaari</name><number>13</number></street>
<city><zip>00014</zip><name>University of Helsinki</name></city>
<fax>19158491</fax> 
<chair><name>Aarne Pehkonen</name></chair>
</department>
<department>
<name>Department of Anatomy</name> 
<address><box>PL 9 Siltavuorenpenger 20A 00014 University of Helsinki 1918499 Ismo Virtanen
</department>
<department>
<name>Department of Animal Science</name> 
<address><box>PL 28</box><street><name>Koetilantie</name><number>5</number></street>
<city><zip>00014</zip><name>University of Helsinki</name></city>
<fax>19158379</fax> 
<chair><name>Matti Ojala</name></chair>
</department>
<department>
<name>Department of Applied Chemistry</name> 
<address><box>PL 27</box><street><name>Latokartanonkaari</name><number>11</number></street>
<city><zip>00014</zip></city><name>University of Helsinki</name></city> 
<fax>19158475</fax> 
<chair><name>Vieno Piironen</name></chair>
</department>
<department>
<name>Department of Applied Zoology</name> 
<address><box>PL 27</box><street><name>Latokartanonkaari</name><number>5</number></street>
<city><zip>00014</zip><name>University of Helsinki</name></city> 
<fax>19158463</fax> 
<chair><name>Kari Heliövaara</name></chair>
</department>
<department>
<name>Department of Archaeology</name> 
<address><box>PL 59</box><street><name>Unioninkatu</name><number>38F</number><street>
<city><zip>00014</zip><name>University of Helsinki</name></city> 
<fax>19123520</fax> 
<chair><name>Ari Siiriäinen</name></chair>
</department>
<department>
<name>Department of Art History</name> 
<address><box>PL 3</box><street><name>Unioninkatu</name><number>34</number></street>
<city><zip>00014</zip><name>University of Helsinki</name></city> 
<fax>19122961</fax> 
<chair><name>Riitta Nikula</name></chair>
</department>
<department>
<name>Department of Astronomy</name> 
<address><box>PL 14</box><street><name>Tähtitorninmäki</name><number></number></street>
<city><zip>00014</zip><name>University of Helsinki</name></city> 
<fax>19122952</fax> 
<chair><name>Karri Muinonen</name></chair>
</department>
</departments>