Browse Prior Art Database

Radix Partitioned Trees for Prolog Axiom Storage

IP.com Disclosure Number: IPCOM000041099D
Original Publication Date: 1987-Aug-01
Included in the Prior Art Database: 2005-Feb-02
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Cohen, ME: AUTHOR

Abstract

This article describes a technique for storing and retrieving axioms in a prolog interpreter.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 1

Radix Partitioned Trees for Prolog Axiom Storage

This article describes a technique for storing and retrieving axioms in a prolog interpreter.

In a prolog interpreter a method for storing and retrieving axioms is used. The axioms are stored by axiom name and number of arguments into a radix partitioned tree. A radix partitioned tree is a kind of binary tree which stores information by keys as described below. These trees have a number of traits that make them superior to the more common hash table axiom storage algorithm. Hash tables are very fast as long as there are fewer things to store than there are buckets in the table. After this point is reached, the access time to hash table grows linearly with the number of items stored in the table. Radix partitioned tree search (RPTS) routines are at least as fast for small numbers of data items and because they maintain nearly balanced binary trees, the access time grows logarithmically with the number of items stored. This is a very important point because prolog programs tend to have many axioms and axiom storage and retrieval is one of the performance bottlenecks in a prolog interpreter.

These axiom storage routines may be further improved by adding the capability to index an axiom by one or more arguments as well as by name and number of arguments. This is most easily accomplished by storing a group of axioms with the same name and number of arguments in another tree. This tree would store each axiom using the fi...