Browse Prior Art Database

Predictive Search Mechanism

IP.com Disclosure Number: IPCOM000038894D
Original Publication Date: 1987-Mar-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 4 page(s) / 25K

Publishing Venue

IBM

Related People

Natarajan, KS: AUTHOR

Abstract

The described invention is a Prediction Mechanism for optimizing the execution speed of applications that repeatedly perform sequential search and make correlated decisions. In a certain class of applications, successive decisions are not independent of one another but instead are correlated with the previous decisions made in sequence. This invention exploits the inherent correlation between successive decisions in a sequence of decisions to achieve faster execution. Statistical knowledge based on observations made during their execution is used to detect such dependencies and predict the optimal execution sequence for making individual decisions. Eventually, the average performance over a period of time converges to a near-optimal performance.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 41% of the total text.

Page 1 of 4

Predictive Search Mechanism

The described invention is a Prediction Mechanism for optimizing the execution speed of applications that repeatedly perform sequential search and make correlated decisions. In a certain class of applications, successive decisions are not independent of one another but instead are correlated with the previous decisions made in sequence. This invention exploits the inherent correlation between successive decisions in a sequence of decisions to achieve faster execution. Statistical knowledge based on observations made during their execution is used to detect such dependencies and predict the optimal execution sequence for making individual decisions. Eventually, the average performance over a period of time converges to a near-optimal performance. The mechanism enhances the performance of an adaptive algorithm that typically does not take into account the correlation of sequential decisions. A sequential search algorithm for decision-making searches a set of potential outcomes to choose one that satisfies given search criteria. Smith
[1], Garey [2], and Simon and Kadane [3] have addressed the problem of minimizing the average cost of sequential decision-making. Their works show that the minimum average cost of making a decision depends on the probability of success and the cost of evaluating individual outcomes. Rivest [4] described two algorithms for adaptively organizing a sequential search where the costs of individual outcomes are equal. The idea of adaptively ordering a chain of decisions has applications in maintenance of data structures, such as linear lists
[4], and in scanning rule-lists in expert system applications. It has been shown that costs and probabilities can be estimated by monitoring program execution and are used to adaptively order a search procedure that converges to an optimal ordering. It has also been shown [5] how an adaptive search can be improved by taking into account the context of the search procedure. The main assumption to note about all of the work cited above is that the successive decisions are made independent of one another, i.e., the probability of making a specific decision at some step does not depend on what decision was taken prior to it in any of the previous steps. The Prediction Mechanism disclosed here is applicable for many applications that make correlated sequential decisions. It is presented here in the context of optimization of expert-system applications. Assume that a program contains a sequential decision chain with several outcomes, and that each decision in the chain has associated with it some fixed cost. For purposes of explanation, a discrete time scale is assumed. The t-th decision taken by a search procedure is considered to occur at Time t. If the probability of success associated with each outcome is given, then it is known [1,2,3] that the optimal ordering of the decisions orders them by descending values of ratios of their probabilities of...