DocumentCode :
3530856
Title :
Dynamic Spatial Approximation Trees for Massive Data
Author :
Navarro, Gonzalo ; Reyes, Nora
Author_Institution :
Dept. of Comput. Sci., Univ. of Chile, Santiago, Chile
fYear :
2009
fDate :
29-30 Aug. 2009
Firstpage :
81
Lastpage :
88
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 not dynamic, that is, few of them tolerate insertion of elements at reasonable cost over an existing index and only a few work efficiently in secondary memory. In this paper we introduce a secondary-memory variant of the dynamic spatial approximation tree, which has shown to be competitive in main memory. The resulting index handles well the secondary memory scenario and is competitive with the state of the art, becoming a useful alternative in a wide range of database applications. Moreover, our ideas are applicable to other secondary-memory trees where there is little control over the tree shape.
Keywords :
approximation theory; database indexing; multimedia databases; spatial data structures; storage management; tree data structures; dynamic spatial approximation tree; indexing scheme; main memory; massive data; metric space searching; multimedia database; secondary-memory variant; similarity search; Application software; Computer science; Costs; Degradation; Extraterrestrial measurements; Indexes; Indexing; Multimedia databases; Shape control; Spatial databases; metric spaces; multimedia databases; secondary memory;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Similarity Search and Applications, 2009. SISAP '09. Second International Workshop on
Conference_Location :
Prague
Print_ISBN :
978-0-7695-3765-8
Type :
conf
DOI :
10.1109/SISAP.2009.28
Filename :
5271949
Link To Document :
بازگشت