Home // DBKDA 2013, The Fifth International Conference on Advances in Databases, Knowledge, and Data Applications // View article

Shrinking Data Balls in Metric Indexes

Authors:
Bilegsaikhan Naidan
Magnus Lie Hetland

Keywords: approximation algorithms, experiments, similarity search, metric space.

Abstract:
Some of the existing techniques for approximate similarity retrieval in metric spaces are focused on shrinking the query region by user-defined parameter. We modify this approach slightly and present a new approximation technique that shrinks data regions instead. The proposed technique can be applied to any metric indexing structure based on the ball-partitioning principle. Experiments show that our technique performs better than the relative error approximation and region proximity techniques, and that it achieves significant speedup over exact search with a low degree of error. Beyond introducing this new method, we also point out and remedy a problem in the relative error approximation technique, substantially improving its performance.

Pages: 211 to 216

Copyright: Copyright (c) IARIA, 2013

Publication date: January 27, 2013

Published in: conference

ISSN: 2308-4332

ISBN: 978-1-61208-247-9

Location: Seville, Spain

Dates: from January 27, 2013 to February 1, 2013