類似度計算テンプレートを用いた検索質問生成による最近隣検索法の最適化  [in Japanese] Optimizing Nearest Neighbor Retrieval by Similarity Calculation Template and Retrieval Query Generation  [in Japanese]

Access this Article

Search this Article

Author(s)

Abstract

The nearest neighbor algorithm has been one of the most basic class of techniques in the field of Pattern classification. It is also the most basic and important technique in the fields such as case-based reasoning (CBR), memory-based reasoning (MBR), and example-based natural language Processing (EBNLP). In the nearest neighbor algorithm, the computational cost of example retrieval is one of the most important issues, especially when the number of examples in the database becomes large. In the field of pattern classification, there exist several techniques for reducing the computational cost of the nearest neighbor algorithm, while in other fields such as CBR, MBR, and EBNLP, there has been no technique except for the one using massively parallel computers. This paper proposes a novel technique for optimizing the nearest neighbor algorithm, especially for the use in CBR, MBR, and EBNLP. The basic idea is to use similarity calculation template, a data structure that enumerates all the possible patterns of calculating similarity between two examples. In the method, the nearest neighbor retrieval process is optimized by generating retrieval queries from an input and similarity calculation templates in a certain order. Its major advantages are as follows : 1) it can be implemented without any expensive hardwave such as massively parallel computers, 2)it is easy to add new examples to the example database. Experimental results show that nearly constant time nearest neighbor retrieval is achieved, independently of the number of examples in the database.

Journal

  • Journal of Japanese Society for Artificial Intelligence

    Journal of Japanese Society for Artificial Intelligence 11(6), 950-959, 1996-11-01

    人工知能学会

References:  16

Cited by:  1

Codes

  • NII Article ID (NAID)
    110002807996
  • NII NACSIS-CAT ID (NCID)
    AN10067140
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    0912-8085
  • NDL Article ID
    4066058
  • NDL Source Classification
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL Call No.
    Z14-1242
  • Data Source
    CJP  CJPref  NDL  NII-ELS  JSAI 
Page Top