Time, space, and statistical improvements to the pathfinder network generation algorithm
C. R. Esposito · 1988
Network models have played an important role in a wide variety of areas, such as knowledge representation, natural language processing, and scene description. This work presents time, space, and statistical improvements to a network generation algorithm known as Pathfinder. The first part of this work describes improvements to the algorithm that reduce the worst-case time complexity from $O(n\sp4)$ to $O(n\sp3$ log$\sb2$ n) in the general case and down to $O(n\sp3)$ in two useful special cases. Some suggestions on how the time complexity can be improved to $O(n\sp2)$ for one of the special cases are also presented. Space requirements are reduced by 25% in the general case and by 75% in the two special cases. The second part of this work describes a reformulation of the Pathfinder algorithm along statistical lines. In this revised version, edge and path lengths are modelled as portions of normal distributions with a user-specified width rather than as point values. We demonstrate that this revision improves both the structural properties of the networks and the statistical fit between the network and the original data. Also discussed in this part are two studies that suggest that structural (i.e., graph-theoretic) methods of interpreting the networks and validating generation parameter choices are often preferable to those based on the edge weights.