Title :
Dynamic Spatial Approximation Trees for Massive Data
Author :
Navarro, Gonzalo ; Reyes, Nora
Author_Institution :
Dept. of Comput. Sci., Univ. of Chile, Santiago, Chile
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;
Conference_Titel :
Similarity Search and Applications, 2009. SISAP '09. Second International Workshop on
Conference_Location :
Prague
Print_ISBN :
978-0-7695-3765-8
DOI :
10.1109/SISAP.2009.28