距離索引VP - treeにおける解絞り込みの一改良法

• Item type: SIG Technical Reports(1)
• 公開日: 2003-09-29
• タイトル: 距離索引VP - treeにおける解絞り込みの一改良法
• タイトル / 言語: en
• タイトル: An improved method to select candidates on metric index VP - tree
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 徳島大学工学部
• 著者所属: 徳島大学工学部
• 著者所属: 徳島大学高度情報化基盤センター
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Tokushima University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Tokushima University
• 著者所属(英): en
• 著者所属(英): Center for Advanced Information Technology, Tokushima Univereity
• 著者名: 中川, 嘉之; 獅々堀正幹; 北, 研二
• 著者名(英): Yoshiyuki, Nakagawa; Masami, Shishibori; Kenji, Kita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: マルチメディア・データベースでは検索効率を高めるために，多次元空間に基づく索引化法が使用される．しかし，この手法は距離尺度としてユークリッド距離を用いることが前提であるため，汎用性に欠ける．一方，距離公理の成立のみを前提とする距離空間に基づく索引化法は，ユークリッド距離以外の距離尺度も利用できるため，汎用性が高い．本稿では，距離空間索引化法の一つであるVP-tree の改良法を提案する．VP-tree は検索時に，ルートノードから検索範囲に適合するノードを辿り，最終的に辿り着いたリーフノードにリンクされているオブジェクトとの距離を算出し，検索範囲に適合するかを調べる．しかし，リーフノードにおける距離計算が増大すると，検索速度が遅くなってしまう．そこで，リーフノードにおける三角不等式を用いた絞り込み法に着目し，その改良法として，三角不等式に用いる基準点を複数個用いる手法，また，基準点に問い合わせオブジェクトに対する最近傍点を用いる手法を提案する．これらの改良法により，検索範囲をより小さくし，距離計算回数を削減することが可能になる．実際に10 000件の画像データを用いて評価実験を行った結果，既存の手法に比べ検索時間を58%?72% 削減することができた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: On multimedia databases, in order to realize the fast access method, indexing methods for the multi-dimension data space are used. However, since it is a premise to use the Euclid distance as the distance measure, this method lacks in flexibility. On the other hand, there are metric indexing methods which require only to satisfy distance axiom. Since metric indexing methods can also apply for distance measures other than the Euclid distance, these methods have high flexibility. This paper proposes an improved method of VP-tree which is one of the metric indexing methods. VP-tree follows the node which suits the search range from a route node at searching. And distances between a query and all objects linked from the leaf node which finally arrived are computed, and it investigates whether each object is contained in the search range. However, search speed will become slow if the number of distance calculations in a leaf node increases. Therefore, we paid attention to the narrowing-down method using the triangular inequality in a leaf node. As the improved methods, we propose the method to utilize not only one vantage point but also two or more vantage points as the datum point of the triangular inequality, and the method to use the nearest neighbor object point for the query as the datum point. It becomes possible to make the search range smaller and to cut down the number of times of distance calculation by these improved methods. From evaluation experiments using 10,000 image data, it was found that our proposed method could cut 58\%縲鰀72\% of search time of the traditional method.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10115061
• 書誌情報: 情報処理学会研究報告自然言語処理（NL）; 巻 2003, 号 98(2003-NL-157), p. 1-8, 発行日 2003-09-29
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会