Nearest neighbor decision ruleThe 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).
Over 5,000 citations of the nearest neighbor rule were found by Citeseer, 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
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
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 second edition has been cited 50,000 times.