# Technical Highlights

## Nearest neighbor decision rule

The nearest neighbor rule is a widely-used method in pattern classification. The first derivation of its fundamental theoretical properties were described in:

Cover, T. M. and P. E. Hart, "Nearest Neighbor Pattern Classification," *IEEE Trans. on Information Theory*, Vol. IT-13, No. 1, pp 21-27 (January 1967).

Over12,000 citations of the nearest neighbor rule are documented by Google Scholar, and our apparently-seminal paper eventually received a Golden Jubilee Paper Award from the IEEE Information Theory Society.

## The A* algorithm for finding the shortest path through a graph

The A* algorithm is guaranteed to find the shortest path through a graph, and does so with minimum computation. It was first described, and its admissibility and optimality properties proved, in:

Hart, P. E., N. J. Nilsson, and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs," *IEEE Trans. on Systems Science and Cybernetics*, Vol. SSC-4, No. 2, pp 100-107, (July 1968).

In addition to spawning a large literature, A* is used in many applications. Among these, it is the foundation of automobile- and web-based systems for computing driving directions; it is the most widely-used path-finding algorithm in video games; and it is used for string-matching and parsing, two of the most fundamental functions in computing.

## The Hough transform

The Hough transform for finding lines and shapes in digital images is a widely used algorithm in image analysis. Hough's original transform used a linear form that made it computationally awkward. The transform universally used today was first described in:

Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," *Comm. ACM*, Vol. 15, pp 1-15 (January, 1972).

I thought the story of how I came to invent this transform was interesting enough to publish it here.

The sinusoidal form of the Hough transform

## PROSPECTOR

The PROSPECTOR expert system for mineral exploration was the first expert system to prove through field test that it could solve an economically important problem. The widely-repeated headline "PROSPECTOR DISCOVERS A MINE", correct in spirit though not literally accurate, ignited interest in artificial intelligence as a serious commercial technology.

PROSPECTOR was first described in:

Hart, P. E., "Progress on a Computer-Based Consultant," *Proc. International Joint Conference on Artificial Intelligence,* Vol. 2, pp 831-841, (Tbilisi, USSR, September 1975).

The big headlines came from our report in Science magazine:

Campbell, A. N., V. F. Hollister, R. O. Duda and P. E. Hart, "Recognition of a Hidden Mineral Deposit by an Artificial Intelligence Program", SCIENCE , Vol. 217, No. 4563, pp 927-929 (3 September 1982).

## Autonomous information retrieval

Modern computer systems increasingly try to guess usersâ€™ intentions and autonomously provide information that might help them achieve their purpose. One of the first examples of this was reported in:

Hart, P. E., and J. Graham, "Query-Free Information Retrieval," *Proc. Second Int. Conf. on Cooperative Info. Systems, pp* 36-46 (Toronto, Canada, May 17-20, 1994).

Ricoh Corporation used this system for over 10 years to support the operators in its national help desk center.

## Pattern Classification and Scene Analysis

First edition

Second edition

Duda, R. O. and P. E. Hart, *Pattern Classification and Scene Analysis,* (John Wiley & Sons, New York, NY, 1973).

The first edition of this graduate text went through 19 printings over more than 25 years before being supplanted by the second edition, *Pattern Classification** (*2nd ed, 2000) by R. O. Duda, P. E. Hart & D. G. Stork (Wiley). The two editions have been cited 70,000 times.