The time-worn aphorism close only counts in horseshoes and hand grenades is clearly inadequate. Close also counts in golf, shuffleboard, archery, darts, curling, and other games of accuracy in which hitting the precise center of the target isn't to be expected every time, or in which we can expect to be driven from the target by skilled opponents. This book is t devoted to sports discussions, but to efficient algorithms for determining pairs of closely related web pages-and a few other situations in which we have found that inexact matching is good eugh - where proximity suffices. We will t, however, attempt to be comprehensive in the investigation of probabilistic algorithms, approximation algorithms, or even techniques for organizing the discovery of nearest neighbors. We are more concerned with finding nearby neighbors; if they are t particularly close by, we are t particularly interested. In thinking of when approximation is sufficient, remember the oft-told joke about two campers sitting around after dinner. They hear ises coming towards them. One of them reaches for a pair of running shoes, and starts to don them. The second then tes that even with running shoes, they cant hope to outrun a bear, to which the first tes that most likely the bear will be satiated after catching the slower of them. We seek problems in which we don't need to be faster than the bear, just faster than the others fleeing the bear.
Mark S. Manasse
Morgan & Claypool Publishers
Date of Publication
Computing: Textbooks & Study Guides
Synthesis Lectures on Information Concepts, Retrieval, and Services