K-NEAREST NEIGHBORS ASSOCIATIVE MEMORY
| Patent code | P170013649 |
|---|---|
| File No. | 14073 |
| Posted date | Jan 25, 2017 |
| Application number | P2015-016977 |
| Publication number | P2016-143430A |
| Patent number | P6389438 |
| Date of filing | Jan 30, 2015 |
| Date of publication of application | Aug 8, 2016 |
| Date of registration | Aug 24, 2018 |
| Inventor |
|
| Applicant |
|
| Title |
K-NEAREST NEIGHBORS ASSOCIATIVE MEMORY
|
| Abstract |
PROBLEM TO BE SOLVED: To provide a k-nearest neighbors associative memory that effectively realizes a k-nearest neighbors algorithm. SOLUTION: A k-nearest neighbors associative memory 100 includes: a clock counting type associative memory 10 that holds R pieces of reference data and outputs, for each of the R pieces of reference data, a match signal that becomes active when a clock count corresponding to a distance between the reference data and given search data has been reached; and a k-nearest neighbors clustering circuit 30 that, each time at least one of the R match signals output from the clock counting type associative memory becomes active, selects a piece of class data, out of R pieces of class data representing classes of the R pieces of reference data, corresponding to each of the at least one active match signal, until k match signals out of the R match signals become active, and determines a class having a largest number of pieces of data when the selected total k pieces of class data are classified by classes. |
| Outline of related art and contending technology |
(In Japanese) 近年、文字認識・画像認識などに代表されるパターンマッチングを必要とするアプリケーションが大変注目されている。特に、パターンマッチングをLSI（Large Scale Integrated circuit）上で実現することにより、将来、人工知能およびモバイル機器などの高機能アプリケーションに適用可能になり、この技術の実現は、非常に注目を浴びている。 パターンマッチングでは、データベースに保存された複数の参照データの中から、完全に検索データと一致するパターンを検索する「完全一致検索処理」と、検索データと最も類似するパターンを検索する「最類似検索処理」とがある。 前者は、CAM（Content Addressable Memory）と呼ばれ、ネットワークルータのIPアドレステーブルのルーティングおよびプロセッサのキャッシュなどの実現に用いられる。人間の脳のような柔軟な検索・比較をコンピュータに処理させるには、後者の最類似検索処理を実現することが必要不可欠である。このような柔軟な比較を実現する機能を持つメモリのことを特に連想メモリ（Associative Memory）と呼ぶ。 連想メモリの例として、検索データと参照データとのマンハッタン距離またはユークリッド距離を用いて最類似検索処理を行うものが知られている（非特許文献1参照）。また、連想メモリにk近傍探索を取り入れたものが知られている（非特許文献2参照）。 |
| Field of industrial application |
(In Japanese) 本発明は、連想メモリに関し、特に、k近傍法を効果的に実現する連想メモリに関する。 |
| Scope of claims |
(In Japanese) 【請求項1】 R個の参照データを保持しており、前記R個の参照データのそれぞれについて、与えられた検索データとの距離に応じたクロック数の経過後にアクティブとなるマッチ信号を出力するクロックカウント式連想メモリと、 前記クロックカウント式連想メモリから出力されるR個のマッチ信号のうちいずれかk個のマッチ信号がアクティブになるまでの間、前記R個のマッチ信号の少なくとも一つがアクティブになるごとに、前記R個の参照データのそれぞれのクラスを表すR個のクラスデータから当該アクティブになった少なくとも一つのマッチ信号のそれぞれに対応するクラスデータを選択し、当該選択した全部でk個のクラスデータをクラス別に分類した場合においてデータ数が最大となるクラスを判定するk近傍クラスタリング回路とを備えている ことを特徴とするk近傍法連想メモリ。 【請求項2】 前記k近傍クラスタリング回路が、 前記R個のクラスデータを保持するクラスデータメモリと、 X個のクラスのそれぞれに対応するX個のクラスカウンタと、 前記アクティブになった少なくとも一つのマッチ信号を順次選択し、当該選択したマッチ信号に対応するクラスデータを前記クラスデータメモリから読み出し、当該読み出したクラスデータによって表されるクラスに対応するクラスカウンタをカウントアップし、前記アクティブになった少なくとも一つのマッチ信号をすべて選択し終わると終了信号を出力するクラス識別回路と、 前記X個のクラスカウンタの中からカウント値が最大のクラスカウンタを見つける最大カウンタ検出回路と、 前記クラス識別回路がアクティブになったマッチ信号を一つ選択するごとにカウントアップし、カウント値がkに一致したことを検出するk－マッチ信号数一致検出回路とを有するものであり、 前記k近傍法連想メモリが、前記R個のマッチ信号の少なくとも一つがアクティブになると前記クロックカウント式連想メモリの動作を停止させて前記クラス識別回路を動作させ、前記クラス識別回路から前記終了信号が出力されると前記クラス識別回路の動作を停止させて前記クロックカウント式連想メモリを動作させる制御回路を備え、 前記クロックカウント式連想メモリが、前記k－マッチ信号数一致検出回路によって前記カウント値がkに一致したことが検出されたとき、動作を停止するように構成されている、請求項1に記載のk近傍法連想メモリ。 【請求項3】 前記制御回路が、 前記R個のマッチ信号のそれぞれに対応して設けられ、対応するマッチ信号がアクティブになってから前記クラス識別回路から前記終了信号が出力されるまでの間だけアクティブになる検出信号を出力するR個のマッチ信号アクティブ検出回路と、 前記R個のマッチ信号アクティブ検知回路から出力されるR個の検出信号の論理和を演算するORゲートとを有し、 前記ORゲートの出力信号で前記クラス識別回路および前記クロックカウント式連想メモリの動作を制御する、請求項2に記載のk近傍法連想メモリ。 【請求項4】 前記クラス識別回路が、前記R個のマッチ信号のそれぞれに対応して設けられ、対応するマッチ信号がアクティブであることを検出して前記クラスデータメモリに当該マッチ信号に対応するクラスデータを選択する選択信号を出力するR個のマッチ信号検出回路を有し、 前記R個のマッチ信号検出回路が、動作開始信号を伝搬するように直列に接続されており、 前記R個のマッチ信号検出回路のそれぞれが、前記対応するマッチ信号が非アクティブのとき、入力された前記動作開始信号をすぐさま次段に伝達し、前記対応するマッチ信号がアクティブのとき、前記動作開始信号を受けて前記選択信号を出力してから前記動作開始信号を次段に伝達するように構成されている、請求項2および3のいずれか一つに記載のk近傍法連想メモリ。 【請求項5】 前記最大カウンタ検出回路が、 初期値からカウント値をカウントダウンするダウンカウンタと、 前記X個のクラスカウンタのそれぞれに対応して設けられ、対応するクラスカウンタのカウント値と前記ダウンカウンタのカウント値との一致を検出するX個の一致検出回路とを有し、 前記ダウンカウンタのカウント値がカウントダウンされている間に、前記X個の一致検出回路のうちのいずれか一つによって前記ダウンカウンタのカウント値と対応するクラスカウンタのカウント値との一致が検出されたとき、前記ダウンカウンタのカウント動作を停止させる、請求項2ないし4のいずれか一つに記載のk近傍法連想メモリ。 【請求項6】 前記最大カウンタ検出回路が、2入力1出力の複数の最大値選出回路がツリー状に接続されてなり、リーフノードの複数の最大値選出回路に前記X個のクラスカウンタの各カウント値および各クラスカウンタの識別番号を結合した各信号が入力され、ルートノードの最大値選出回路から前記X個のクラスカウンタの最大カウント値およびそのクラスカウンタの識別番号を結合した信号を出力するトーナメント回路であり、 前記最大値選出回路が、第1のクラスカウンタのカウント値および前記第1のクラスカウンタの識別番号を結合した第1の信号、および第2のクラスカウンタのカウント値および前記第2のクラスカウンタの識別番号を結合した第2の信号を受け、前記第1および第2のクラスカウンタのうちカウント値が大きい方のクラスカウンタのカウント値およびそのクラスカウンタの識別番号を結合した第3の信号を出力する、請求項2ないし4のいずれか一つに記載のk近傍法連想メモリ。 |
| IPC(International Patent Classification) |
|
| F-term | |
|
Drawing
※Click image to enlarge. |
|
| State of application right | Registered |
Contact Information for " K-NEAREST NEIGHBORS ASSOCIATIVE MEMORY"
- HIROSHIMA UNIVERSITY Collaborative Research Center Intellectual Property Division
- URL: https://www.hiroshima-u.ac.jp/iagcc
-
E-mail:
- Address: 1-3-2 Kagamiyama Higashi-Hiroshima, Hiroshima, Japan , 739-8511
- Fax: 81-82-424-6133
※ It is possible to retrieve in J-STORE by the same key word. → Retrieval result of J-STORE
