摘要：Metric space searching is an emerging technique to address the problem of similarity searching in many applications. In order to efficiently answer similarity queries, the database must be indexed. In some inter- esting real applications dynamism is an indispensable property of the index. There are very few actually dynamic indexes that support not only searches, but also insertions and deletions of elements. The dynamic spatial approx- imation tree (DSAT) is a data structure specially de- signed for searching in metric spaces, which com- pares favorably against other data structures in high dimensional spaces or queries with low selectivity. Insertions are efficient and easily supported in DSAT, but deletions degrade the structure over time. Several methods are proposed to handle deletions over the DSAT. One of them has shown to be supe- rior to the others, in the sense that it permits control- ling the expected deletion cost as a proportion of the insertion cost and searches does not overly degrade after several deletions. In this paper we propose and study a new alter- native deletion method, based on the better existing strategy. The outcome is a fully dynamic data struc- ture that can be managed through insertions and dele- tions over arbitrarily long periods of time without any significant reorganization
