کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
534715 | 870283 | 2012 | 6 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A log square average case algorithm to make insertions in fast similarity search A log square average case algorithm to make insertions in fast similarity search](/preview/png/534715.png)
To speed up similarity based searches many indexing techniques have been proposed in order to address the problem of efficiency. However, most of the proposed techniques do not admit fast insertion of new elements once the index is built. The main effect is that changes in the environment are very costly to be taken into account.In this work, we propose a new technique to allow fast insertions of elements in a family of static tree-based indexes. Unlike other techniques, the resulting index is exactly equal to the index that would be obtained by building it from scratch. Therefore there is no performance degradation in search time.We show that the expected number of distance computations (and the average time complexity) is bounded by a function that grows with log2(n) where n is the size of the database.In order to check the correctness of our approach some experiments with artificial and real data are carried out.
► Fast similarity search techniques use indexes to speed up the search.
► A new technique to allow insertions of elements in tree-based indexes is proposed.
► A theoretical analysis shows the insertions can be made in log square average time.
► Experiments confirm the theoretical results.
Journal: Pattern Recognition Letters - Volume 33, Issue 9, 1 July 2012, Pages 1060–1065