16-03-2010, 10:06 PM
Online Index Recommendations For High-Dimensional Databases Using Query Workloads
Scope of this Project:
Best application for this approach is to apply the more time consuming no-constraint analysis in order to determine an initial index set and then apply a lightweight and low control sensitivity analysis for the online query pattern change detection in order to avoid or make the user aware of situations where the index set is not at all effective for the new incoming queries.
Introduction
An increasing number of database applications such as business data warehouses and scientific data repositories deal with high-dimensional data sets. As the number of dimensions/attributes and the overall size of data sets increase, it becomes essential to efficiently retrieve specific queried data from the database in order to effectively utilize
the database. Indexing support is needed to effectively prune out significant portions of the data set that are not relevant for the queries. Multidimensional indexing, dimensionality reduction, and Relational Database Management System (RDBMS) index selection tools all could be applied to the problem. However, for high-dimensional data sets, each of these potential solutions has inherent problems.
To illustrate these problems, consider a uniformly distributed data set of 1,000,000 data objects with several hundred attributes. Range queries are consistently executed over five of the attributes. The query selectivity over each attribute is 0.1, so the overall query selectivity is 1=105 (that is, the answer set contains about 10 results). An ideal solution would allow us to read from the disk only those pages that contain matching answers to the query. We could build a multidimensional index over the data set so that we can directly answer any query by only using the index. However, the performance of multidimensional index structures is subject to Bellmanâ„¢s curse of dimensionality and rapidly degrades as the number of dimensions increases. For the given example, such an index would perform much worse than a sequential scan. Another
Possibility would be to build an index over each single dimension. The effectiveness of this approach is limited to the amount of search space that can be pruned by a single dimension (in the example, the search space would only be pruned to 100,000 objects).
Abstract:
High-dimensional databases pose a challenge with respect to efficient access. High-dimensional indexes do not work because of the often-cited "curse of dimensionality. However, users are usually interested in querying data over a relatively small subset of the entire attribute set at a time.
A potential solution is to use lower dimensional indexes that accurately represent the user access patterns. A query response using the physical database design that is developed based on a static snapshot of the query workload may significantly degrade if the query patterns change.
To address these issues, we introduce a parameterizable technique to recommend indexes based on index types that are frequently used for high-dimensional data sets and to dynamically adjust indexes as the underlying query workload changes.
We incorporate a query pattern change detection mechanism to determine when the access patterns have changed enough to warrant change in the physical database design. By adjusting analysis parameters,
We trade off analysis speed against analysis resolution. We perform experiments with a number of data sets, query sets, and parameters to show the effect that varying these characteristics has on analysis results.
Existing System
Query response does not perform well if query patterns change.
Because it uses static query workload.
Its performance may degrade if the database size gets increased.
Tradition feature selection technique may offer less or no data pruning capability given query attributes.
Proposed System
We develop a flexible index selection frame work to achieve index selection for high dimensional data.
A control feedback technique is introduced for measuring the performance.
Through this a database could benefit from an index change.
The index selection minimizes the cost of the queries in the work load.
Online index selection is designed in the motivation if the query pattern changes over time.
By monitoring the query workload and detecting when there is a change on the query pattern, able to evolve good performance as query patterns evolve.
Advantages
By creating index we can minimize the searching time.
Index will automatically adjust itself based on the query workloads over time
Disadvantages
If the query patterns change it does not provide better result.
Efficiency is less.
Less reliability
System Requirements
Hardware requirements
Monitor :15 inches
RAM :256 MB
Processor :Intel Pentium 4
Key board :102 keys
Mouse :3 Buttons
software requirements
Front End :J2EE
Back End :MS SQL
