Optimal Parallel I/O for Range Queries through Replication

Get BibTex-formatted data

Download

PDF

Author

Keith Frikken, Mikhail Atallah, Sunil Prabhakar, Rei Safavi-Naini

Tech report number

CERIAS TR 2003-10

Entry type

inproceedings

Abstract

In this paper we study the problem of declustering two-dimensional datasets with replication over parallel devices to improve range query performance. The related problem of declustering without replication has been well studied. It has been established that strictly optimal declustering schemes do no exist if data is not replicated. In addition to the usual problem of identifying a good allocation, the replicated version of the problem needs to address the issue of identifying a good retrieval schedule for a given query. We address both problems in this paper. An efficient algorithm for finding a lowest cost retrieval schedule is developed. This algorithm works for any query, not just range queries. Two replicated placement schemes are presented - one that results in a strictly optimal allocation, and another that guarantees a retrieval cost that is either optimal or 1 more than the optimal for any range query.

Download

PDF

Date

2002 – 09

Booktitle

13th International Conference and Workshop on Database and Expert Systems Applications (DEXA)

Key alpha

Frikken

Pages

669-678

Affiliation

Purdue University

Publication Date

2002-09-01

Keywords

parallel I/O, range queries

Language

English

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Inproceedings{ Frikken,
	title = "Optimal Parallel I/O for Range Queries through Replication",
	author = "Keith Frikken, Mikhail Atallah, Sunil Prabhakar, Rei Safavi-Naini",
	year = "2002",
	month = "09",
	booktitle = "13th International Conference and Workshop on Database and Expert Systems Applications (DEXA)",
	pages = "669-678",
	abstract = "In this paper we study the problem of declustering two-dimensional datasets with replication over parallel devices to improve range query performance.  The related problem of declustering without replication has been well studied.  It has been established that strictly optimal declustering schemes do no exist if data is not replicated.  In addition to the usual problem of identifying a good allocation, the replicated version of the problem needs to address the issue of identifying a good retrieval schedule for a given query.  We address both problems in this paper.  An efficient algorithm for finding a lowest cost retrieval schedule is developed.  This algorithm works for any query, not just range queries.  Two replicated placement schemes are presented - one that results in a strictly optimal allocation, and another that guarantees a retrieval cost that is either optimal or 1 more than the optimal for any range query.",
	affiliation = "Purdue University",
	keywords = "parallel I/O, range queries",
	language = "English",
}