View selection using randomized search

Panos Kalnis, Nikos Mamoulis, Dimitris Papadias*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

77 Scopus citations


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
Issue number1
StatePublished - Jul 2002
Externally publishedYes

Bibliographical note

Funding Information:
This work was supported by grants HKUST 6081/01E and HKUST 6070/00E from Hong Kong RGC.


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

ASJC Scopus subject areas

  • Information Systems and Management


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

Cite this