Report Number: CS-TR-91-1381
Institution: Stanford University, Department of Computer Science
Title: Implementing hypertext database relationships through
aggregations and exceptions
Author: Hara, Yoshinori
Author: Keller, Arthur M.
Author: Rathmann, Peter K.
Author: Wiederhold, Gio
Date: September 1991
Abstract: In order to combine hypertext with database facilities, we
show how to extract an effective storage structure from given
instance relationships. The schema of the structure
recognizes clusters and exceptions. Extracting high-level
structures is useful for providing a high performance
browsing environment as well as efficient physical database
design, especially when handling large amounts of data.
This paper focuses on a clustering method, ACE, which
generates aggregations and exceptions from the original graph
structure in order to capture high level relationships. The
problem of minimizing the cost function is NP-complete. We
use a heuristic approach based on an extended Kernighan-Lin
We demonstrate our method on a hypertext application and on a
standard random graph, compared with its analytical model.
The storage reductions of input database size in main memory
were 77.2% and 12.3%, respectively. It was also useful for
secondary storage organization for efflcient retrieval.