Efficient Join-Index-Based Join Processing: A Clustering Approach

Abstract

A join-index is a data structure used for processing join queries in databases. Join-indices use pre-computation techniques to speed up online query processing and are useful for data sets which are updated infrequently. The I/O cost of join computation using a join-index with limited buffer space depends primarily on the page-access sequence used to fetch the pages of the base relations. Given a join-index, we introduce a suite of methods based on clustering to compute the joins. We derive upper bounds on the length of the page-access sequences. Experimental results with Sequoia 2000 data sets show that the clustering method outperforms existing methods based on sorting and online-clustering heuristics.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 06, 1999
Accession Number
AD1020028

Entities

People

  • Chang-tien Lu
  • Sanjay Chawla
  • Shashi Shekhar
  • Sivakumar Ravada

Organizations

  • University of Minnesota

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Clustering
  • Computations
  • Computer Science
  • Data Sets
  • Databases
  • Generators
  • Graphs
  • Iterations
  • Literature
  • Relational Databases
  • Sequences
  • Side Effects
  • Three Dimensional
  • Two Dimensional
  • United States

Fields of Study

  • Computer science

Readers

  • Linear Algebra
  • Materials Science.
  • Parallel and Distributed Computing.

Technology Areas

  • Space