Efficient Algorithms and Performance Results for Multi-User Knowledge Bases

Abstract

The paper describes research efforts to develop efficient implementation techniques for large, shared knowledge bases, focusing on efficient concurrent access of large knowledge bases by multiple users. We present an algorithm, called the Dynamic Directed Graph policy, originally proposed in [Chaudhri et a/., 1992], which allows efficient interleaved execution of transactions against a large knowledge base with the intent of optimizing transaction throughput. The implementation of the policy and experimental evaluation results are also presented and discussed. The paper concludes with discussion on lessons learnt from this research. Large knowledge bases containing millions of facts will soon be here, thanks to research efforts such as the Knowledge Sharing initiative [Patil et a/., 1992] and the CYC project [Guha and Lenat, 1994]. However, tools for building knowledge bases do not scale up to accommodate such large knowledge bases. Our efforts are focusing on the adoption of database techniques to build knowledge base building tools that do scale up. One of the requirements of such tools is that they accommodate efficient multi-user access of a single, large knowledge base by maximizing throughput, i.e., the number of user-defined transactions that are executed against the knowledge base per time unit. A comparable requirement for databases is addressed by concurrency control mechanisms that are routinely offered by database management systems, which have been shown to improve throughput by as much as an order of magnitude or more. A comparable concurrency control algorithm, specifically designed for knowledge bases and called the Dynamic Directed Graph policy was proposed in [Chaudhri et a/., 1992]. The main purpose of this paper is to describe an implementation of that policy and to present