Next: Implementation
Up: Bundling: a hybrid approach
Previous: Conceptual framework
Once the input profiles have been used to create the graph, the bundling
algorithm uses the graph to put the files into bundles. The algorithm works
as follows:
- Initially, each file is put in a separate bundle.
- Edges whose weight is less than the minimum edge weight
are discarded.
- The edges are sorted according to the edge comparator.
- The edges are processed one at a time, in the order
determined in step 3. For each edge, if the files
connected by the edge are not already in the same bundle, and if the
number of files in the resulting bundle would not exceed the maximum bundle size, and if the
resulting bundle would not exceed the maximum bundle spread, then the
bundles containing the files are combined into a single bundle.
- After all the edges have been processed, the files within each resulting bundle
are sorted according to the bundle sort comparator.
Once the contents of the bundles have been determined, they are
combined and compressed cumulatively. We evaluated both zlib (at the
highest compression level) and Pack as compressed formats for the
bundles.
David Hovemeyer
Tue Feb 27 18:43:09 EST 2001