Summary form only given. Conventional compression techniques exploit general redundancy features in data to compress them. For example, Huffman or Lempel-Ziv techniques compresses data by statistical modeling or string matching while the Burrows-Wheeler Transform simply sorts data by context to improve compressibility. On the other hand, data can often be compressed better by exploiting their specific features. For example, columns or fields in a database table tend to be sparse, but not rows. Techniques have been developed to either group related table columns or compute dependency among them to transform data and enhance compressibility. The Vcodex data transformation platform provides a framework to develop and use such data transforms. That is, it treats compression techniques as invertible data transforms that can be composed together for specific tasks. In this way, data transformation remains general and can include techniques for encryption and others.

Large amounts of business data are kept in tables of fixed-length records. Columns in such a table may be functionally dependent on one another, resulting in low overall information content. This paper shows how to exploit this source of information redundancy to compress table data. Experiments with a wide variety of massive tables including telecom data and stock quotes show that this technique compresses table data well, up to 48:1 or even 100:1 reduction in some cases.

Over the past few years, my colleagues and I have written a number of software libraries for fundamental computing tasks, including I/O, memory allocation, container data types and sorting. These libraries have proved to be good software building blocks, and are used widely by programmers around the world. This success is due in part to a library architecture that employs two main interface mechanisms: disciplines to define resource requirements; and methods to parameterize resource management. Libraries built this way are called discipline and method libraries. Copyright © 2000 John Wiley & Sons, Ltd.

My colleagues and I have written and distributed a number of general purpose libraries covering a wide range of computing areas such as I/O, memory allocation, container data types, and sorting. Published studies showed that these libraries are more general, flexible and efficient than comparable packages as application construction tools. Our libraries are based on an architecture in which two main interfaces are made explicit: disciplines to define resource requirements, and methods to define resource management. This paper discusses the discipline and method library architecture and a resource-oriented analysis approach for analyzing and designing libraries based on this architecture.

Delta algorithms compress data by encoding one file in terms of another. This type of compression is useful in a number of situations: strong multiple versions of data, displaying differences, merging changes, distributing updates, storing backups, transmitting video sequences, and others. This article studies the performance parameters of several delta algorithms, using a benchmark of over 1,300 pairs of files taken from two successive releases of GNU software. Results indicate that modern delta compression algorithms based on Ziv-Lempel techniques significantly outperform diff , a popular but older delta compressor, in terms of compression ratio. The modern compressors also correlate better with the actual difference between files without sacrificing performance.

Modern software systems are often built from existing library components. A common problem is how to fix bugs when source code is not available. Xept is an instrumentation language and tool that can be used to add to object code the ability to detect, mask, recover and propagate exceptions from library functions. This helps to alleviate or avoid a large class of errors resulting from function misuses. Examples are given to show applications of Xept in actual software systems.

Cdt is a container data type library that provides a uniform set of operations to manage dictionaries based on the common storage methods: list, stack, queue, ordered set/multiset, and unordered set/multiset. Both object description and storage method in a dictionary can be dynamically changed so that abstract operations can be exactly matched with run-time requirements for operational flexibility and performance. A study comparing Cdt and other popular container packages shows that Cdt performs best in both computing time and space usage. © 1997 John Wiley & Sons, Ltd

Despite its popularity, malloc's shortcomings frequently cause programmers to code around it. The new library Vmalloc generalizes malloc to give programmers more control over memory allocation. Vmalloc introduces the idea of organizing memory into separate regions, each with a discipline to get raw memory and a method to manage allocation. Applications can write their own disciplines to manipulate arbitrary type of memory or just to better organize memory in a region by creating new regions out of its memory. The provided set of allocation methods include general purpose allocation, fast special cases and aids for memory debugging or profiling. A compatible malloc interface enables current applications to select allocation methods using environment variables so they can tune for performance or perform other tasks such as profiling memory usage, generating traces of allocation calls or debugging memory errors. A performance study comparing Vmalloc and currently popular malloc implementations shows that Vmalloc is competitive to the best of these allocators. Applications can gain further performance improvement by using the right mixture of regions with different Vmalloc methods.

A four-pass algorithm for drawing directed graphs is presented. The fist pass finds an optimal rank assignment using a network simplex algorithm. The seconds pass sets the vertex order within ranks by an iterative heuristic, incorporating a novel weight function and local transpositions to reduce crossings. The third pass finds optimal coordinates for nodes by constructing and ranking an auxiliary graph. The fourth pass makes splines to draw edges. The algorithm creates good drawings and is fast.>

Abstract DAG is a program that draws directed graphs by reading a list of noeds and edges, computing a layout and then writing a PIC or PostScript description of a picture. Optional drawing instructions specify the way nodes are drawn, attach labels and control spacing. DAG works best on directed acyclic graphs, which are often used to represent hierarchical relationships. For example, here is a drawing of a graph from J. W. Forrester's book, World Dynamics (Wright‐Allen, Cambridge, MA, 1971), which took 1.63 CPU seconds to draw using a VAX‐8650.