Image databases typically manage feature data that can be viewed as points in a feature space. Some features, however, can be better expressed as a collection of points or described by a probability distribution function (PDF) rather than as a single point. In earlier work we introduced a similarity measure and a method for indexing and searching the PDF descriptions of these items that guarantees an answer equivalent to sequential search. Unfortunately, certain properties of the data can restrict the efficiency of that method. In this paper we extend that work and examine trade-offs between efficiency and answer quality or effectiveness. These trade-offs reduce the amount of work required during a search by reducing the number of undesired items fetched without excluding an excessive number of the desired ones.
J. Barros, J. French, W. Martin, and P. Kelly. Trading efficiency for effectiveness in similarity-based indexing for image databases. In SPIE Vol. 2606 Digital Image Storage and Archiving Systems, pages 276-287, 1995. (UVA) [ Abstract | PostScript (418 KB) | PDF (229 KB) ]
