Similarity Search: the metric space approach

In the Information Society, information holds the master key to economic inuence and success. But the usefulness of information depends critically upon its quality and the speed at which it can be transferred. In domains as diverse as multimedia, molecular biology, computer-aided design and marketing and purchasing assistance, the number of data resources is growing rapidly, both with regard to database size and the variety of forms in which data comes packaged. To cope with the resulting information overkill, it is vital to nd tools to search these resources efciently and effectively. Hence the intense interest in Computer Science in searching digital data repositories. But traditional retrieval techniques, typically based upon sorting routines and hash tables, are not appropriate for a growing number of newly-emerging data domains. More exible methods must be found instead which take into account the needs of particular users and particular application domains. This book is about nding efcient ways to locate user-relevant information in collections of objects which have been quantied using a pairwise distance measure between object instances. It is written in direct response to recent advances in computing, communication and storage which have led to the current ood of digital libraries, data warehouses and the limitless heterogeneity of Internet resources. The scale of the problem can be gauged by noting that almost everything we see, hear, read, write or measure will soon be available to computerized information systems. In such an environment, varied data modalities such as multimedia objects, scientic observations and measurements, statistical analyses and many others, are massively extending more traditional attribute-like data types.