Online Index Recommendations for High-Dimensional Databases Using Query Workloads

摘要

High-dimensional databases pose a challenge withrespect to efficient access. High-dimensional indexes do notwork because of the oft-cited "curse of dimensionality''. However, users are usually interested in querying data over a relativelysmall 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. Query response using physical database design 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 frequently used forhigh-dimensional data sets and to dynamically adjust indexesas the underlying query workload changes. We incorporate aquery pattern change detection mechanism to determine when the access patterns have changed enough to warrant change inthe 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.