### Dynamic spatial approximation treesDynamic spatial approximation trees

Access Restriction
Subscribed

 Author Navarro, Gonzalo ♦ Reyes, Nora Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2008 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Multimedia databases ♦ Similarity or proximity search ♦ Spatial and multidimensional search ♦ Spatial approximation tree Abstract Metric space searching is an emerging technique to address the problem of efficient similarity searching in many applications, including multimedia databases and other repositories handling complex objects. Although promising, the metric space approach is still immature in several aspects that are well established in traditional databases. In particular, most indexing schemes are static, that is, few of them tolerate insertion or deletion of elements at reasonable cost over an existing index. The spatial approximation tree $(\textit{sa--tree})$ has been experimentally shown to provide a good tradeoff between construction cost, search cost, and space requirement. However, the $\textit{sa--tree}$ is static, which renders it unsuitable for many database applications. In this paper, we study different methods to handle insertions and deletions on the $\textit{sa--tree}$ at low cost. In many cases, the dynamic construction (by successive insertions) is even faster than the previous static construction, and both are similar elsewhere. In addition, the dynamic version significantly improves the search performance of $\textit{sa--trees}$ in virtually all cases. The result is a much more practical data structure that can be useful in a wide range of database applications. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2008-06-12 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 12 Page Count 68 Starting Page 1 Ending Page 68

#### Open content in new tab

Source: ACM Digital Library