Browse Prior Art Database

Adaptive Optimization of Recursive Search Trees

IP.com Disclosure Number: IPCOM000057721D
Original Publication Date: 1988-Jun-01
Included in the Prior Art Database: 2005-Feb-15

Publishing Venue

IBM

Related People

Authors:
Natarajan, KS Sakuragawa, T Stone, HS [+details]

Abstract

A technique is described whereby adaptive searching is applied to recursively defined search trees, as used in artificial intelligence search algorithms, so as to minimize the average cost of a search. Discussed are ways of reordering recursive rules without changing the semantics, such that ordering takes place in the same ratio that determines the ordering of nonrecursive search trees. Adaptive optimization of recursive search trees establishes that when techniques are applied to recursively defined search trees, the nodes of the recursive tree should be ordered according to descending values of the ratio p/c, where p is the probability of the successful termination of the rule and c is the cost of application of the rule.