Bulk-loading onion-trees

• Grant number: 10/13756-8
• Support Opportunities: Scholarships in Brazil - Master
• Start date: March 01, 2011
• End date: February 28, 2013
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal Investigator: Cristina Dutra de Aguiar
• Grantee: Arthur Emanuel de Oliveira Carosia
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil

Abstract

It is being under development by the research group headed by the supervisor of this project the Onion-tree, a new and robust dynamic memory-based access method that slices the metric space into disjoint subspaces to provide quick indexing of complex data. It introduces three major characteristics: (i) a partitioning method that controls the number of disjoint subspaces generated at each node; (ii) a replacement technique that can change the leaf node pivots in insertion operations; and (iii) range and k-NN extended query algorithms to support the new partitioning method. However, the Onion-tree only performs element-by-element insertions into its structure. Another related issue is the mass loading technique, called bulk-loading, which builds the index considering all the elements of the dataset at once. The main advantage of the bulk-loading is to analyze in advance the elements to achieve a better partitioning of the metric space. The objective of this research project is to develop a bulk-loading strategy for the Onion-tree, based on the intrinsic characteristics of this metric access method. (AU)