Grafting Trees A Nearest Neighbor Search Algorithm without Distance Computation

Bibliographic Information

Other Title
  • 距離計算を行わない最近傍探索アルゴリズム : Grafting Trees(テーマセッション,大規模データベースとパターン認識)

Search this article

Description

This report presents a nearest neighbor search algorithm without distance computation K-D tree based nearest neighbor search algorithm consists of two processes : 1) determine tentative nearest neighbor data by tree search, and 2) A* algorithm based "priority search" to find true nearest neighbor data to the query. The latter process consumes most computational time especially for high dimensional data distributions. We focus on the fact that the nearest neighbor data is essentially determined by the query position in the feature space and the priority search can be replaced by classifiers. In practice, we employ decision trees as classifiers and attach them to the K-D tree leaf nodes. This data structure is named Grafting trees. On this tree, we can find the nearest neighbor data without distance computation, In this data structure, some decision tree leaves can be very deep. For solving this problem, we modified this data structure forgiving distance computation for such leaf nodes. The modified tree is named Hybrid Grafting trees. In the experiments, we compared ANN library with our methods and confirmed the search time is shorter than ANN.

Journal

  • Technical report of IEICE. PRMU

    Technical report of IEICE. PRMU 112 (441), 137-142, 2013-02-14

    The Institute of Electronics, Information and Communication Engineers

Keywords

Details 詳細情報について

  • CRID
    1573105977757186304
  • NII Article ID
    110009728815
  • NII Book ID
    AN10541106
  • Text Lang
    ja
  • Data Source
    • CiNii Articles

Report a problem

Back to top