AN IMPROVED METHOD TO SELECT CANDIDATES ON METRIC INDEX VP-TREE

Masami Shishibori, Samuel Sangkon Lee, Kenji Kita

2011

Abstract

On multimedia databases, it is one of important techniques to use the efficient indexing method for the fast access. Metric indexing methods can apply for various distance measures other than the Euclidean distance. Then, metric indexing methods have higher flexibility than multi-dimensional indexing methods. We focus on the Vantage Point tree (VP-tree) which is one of the metric indexing methods. VP-tree is an efficient metric space indexing method, however the number of distance calculations at leaf nodes tends to increase. In this paper, we propose an efficient algorithm to reduce the number of distance calculations at leaf nodes of the VPtree. The conventional VP-tree uses the triangle inequality at the leaf node in order to reduce the number of distance calculations. At this point, the vantage point of the VP-tree is used as a reference point of the triangle inequality. The proposed algorithm uses the nearest neighbor (NN) point for the query instead of the vantage point as the reference point. By using this method, the selection range by the triangle inequality becomes small, and the number of distance calculations at leaf nodes can be cut down. Moreover, it is impossible to specify the NN point in advance. Then, this method regards the nearest point to the query in the result buffer as the temporary NN point. If the nearer point is found on the retrieval process, the temporary NN point is replaced with new one. From evaluation experiments using 10,000 image data, it was found that our proposed method could cut 5%12% of search time of the conventional VP-tree.

Paper Citation

in Harvard Style

Shishibori M., Sangkon Lee S. and Kita K. (2011). AN IMPROVED METHOD TO SELECT CANDIDATES ON METRIC INDEX VP-TREE . In Proceedings of the International Conference on Knowledge Discovery and Information Retrieval - Volume 1: KDIR, (IC3K 2011) ISBN 978-989-8425-79-9, pages 306-311. DOI: 10.5220/0003668803140319

in Bibtex Style

@conference{kdir11,
author={Masami Shishibori and Samuel Sangkon Lee and Kenji Kita},
title={AN IMPROVED METHOD TO SELECT CANDIDATES ON METRIC INDEX VP-TREE},
booktitle={Proceedings of the International Conference on Knowledge Discovery and Information Retrieval - Volume 1: KDIR, (IC3K 2011)},
year={2011},
pages={306-311},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003668803140319},
isbn={978-989-8425-79-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Knowledge Discovery and Information Retrieval - Volume 1: KDIR, (IC3K 2011)
TI - AN IMPROVED METHOD TO SELECT CANDIDATES ON METRIC INDEX VP-TREE
SN - 978-989-8425-79-9
AU - Shishibori M.
AU - Sangkon Lee S.
AU - Kita K.
PY - 2011
SP - 306
EP - 311
DO - 10.5220/0003668803140319