View selection using randomized search

Panos Kalnis, Nikos Mamoulis, Dimitris Papadias*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

78 Scopus citations

Abstract

An important issue in data warehouse development is the selection of a set of views to materialize in order to accelerate On-line analytical processing queries, given certain space and maintenance time constraints. Existing methods provide good results but their high execution cost limits their applicability for large problems. In this paper, we explore the application of randomized, local search algorithms to the view selection problem. The efficiency of the proposed techniques is evaluated using synthetic datasets, which cover a wide range of data and query distributions. The results show that randomized search methods provide near-optimal solutions in limited time, being robust to data and query skew. Furthermore, they can be easily adapted for various versions of the problem, including the simultaneous existence of size and time constraints, and view selection in dynamic environments. The proposed heuristics scale well with the problem size, and are therefore particularly useful for real life warehouses, which need to be analyzed by numerous business perspectives.

Original languageEnglish (US)
Pages (from-to)89-111
Number of pages23
JournalData and Knowledge Engineering
Volume42
Issue number1
DOIs
StatePublished - Jul 2002
Externally publishedYes

Keywords

  • Data warehouse
  • On-line analytical processing
  • View selection

ASJC Scopus subject areas

  • Information Systems and Management

Fingerprint

Dive into the research topics of 'View selection using randomized search'. Together they form a unique fingerprint.

Cite this