Search

In this article, we are interested in accelerating similarity search in high dimensional spaces. The performance of exact nearest neighbors search rapidly decays with the increase of the space dimension (curse of dimensionality effect). This justified a significant effort toward alternate solutions for accelerating similarity search in the past ten years. After a short survey of these new solutions organized into three categories, we describe and evaluate three new strategies: first we propose a progressive exact approach, called HiPeR which is independent of the data as well as of the multidimensional index. We illustrate this approach with the VA-file. Then we study the adaptation of HiPeR to approximate search, using a probabilistic model for precision control. Last we present strategies for efficient processing of multiple queries with application to tree indices as well as HiPeR.

Nowadays, materialized views are increasingly being supported by a variety of commercial DBMS to speed up query response time. This technique is also very useful in dataware-housing for optimizing OLAP queries. However, most existing view selection methods are of static nature. Moreover, none of these methods have considered the problem of dematerializing the previously materialized views. This paper deals with the problem of dynamic view selection and the pending issue of removing materialized views in order to replace the less beneficial views with more beneficial views. More precisely, we have designed and implemented a view selection method, including a polynomial algorithm, to decide which views to materialize according to statistic metadata.