Thumbnail
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

   Open content in new tab
Source: ACM Digital Library