Transfer non-metric measures into metric for similarity search

ABSTRACT

Similarity search is widely used in multimedia retrieval systems to find the most similar ones for a given object. Some similarity measures, however, are not metric, leading to existing metric index structures cannot be directly used. To address this issue, we propose a simulated-annealing-based technique to derive optimized mapping functions that transfer non-metric measures into metric, and still preserve the original similarity orderings. Then existing metric index structures can be used to speed up similarity search by exploiting the triangular inequality property. The experimental study confirms the efficacy of our approach.

REFERENCES

• 1: V. Athitsos, J. Alon, S. Sclaroff, and G. Kollios. Boostmap: A method for efficient approximate similarity rankings. In Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition, pages 268--275, 2004.
• 2: H. G. Barrow, J. M. Tenenbaum, R. C. Bolles, and H. C. Wolf. Parametric correspondence and chamfer matching: Two new techniques for image matching. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 659--663, 1977.
• 3: N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An efficient and robust access method for points and rectangles. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 322--331, 1990.
• 4: P. Ciaccia, M. Patella, and P. Zezula. M-ree: An efficient access method for similarity search in metric spaces. In Proceedings of the International Conference on Very Large Data Bases, pages 426--435, 1997.
• 5: T. M. Cover and J. A. Thomas. Elements of information theory. Wiley--Interscience, 1991.
• 6: C. Faloutsos and K. Lin. Fastmap: A fast algorithm for indexing, data--mining and visualization of traditional and multimedia datasets. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 163--174, 1995.
• 7: K. Goh, B. Li, and E. Y. Chang:. Dyndex: a dynamic and non-metric space indexer. In Proceedings of the ACM International Conference on Multimedia, pages 466--475, 2002.
• 8: G. Hjaltason and H. Samet. Properties of embedding methods for similarity searching in metric spaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(5):530--549, 2003.
• 9: D. W. Jacobs, D. Weinshall, and Y. Gdalyahu. Classification with non--metric distances: Image retrieval and class representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(6):583--600, 2000.
• 10: H. V. Jagadish, B. C. Ooi, K.-L. Tan, C. Yu, and R. Zhang. iDistance: An adaptive B+-tree based indexing method for nearest neighbor search. ACM Transactions on Database Systems, 30(2):364--397, 2005.
• 11: N. Katayama and S. Satoh. The sr-tree: An index structure for high--dimensional nearest neighbor queries. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 369--380, May 1997.
• 12: E. J. Keogh. Exact indexing of dynamic time warping. In Proceedings of the International Conference on Very Large Data Bases, pages 406--417, 2002.
• 13: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671--680, 1983.
• 14: A. Marzal and E. Vidal. Computation of normalized edit distance and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(9):926--932, 1993.
• 15: Y. Sakurai, M. Yoshikawa, S. Uemura, and H. Kojima. The A-tree: An Index Structure for High-dimensional Spaces Using Relative Approximation. In Proceedings of the International Conference on Very Large Data Bases, pages 516--526, 2000.
• 16: T. Skopal. On fast non-metric similarity search by metric access methods. In Proceedings of the International Conference on Extending Database Technology, pages 718--736, 2006.
• 17: X. Wang, J. Wang, K. Lin, D. Shasha, B. Shapiro, and K. Zhang. An index structure for data mining and clustering. Knowledge and Information Systems, 2(2):161--184, 2000.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process; Retrieval models; Selection process

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
multimedia retrieval, non-metric similarity, relevance feedback