Computing ranked selection indexes for linear preference queries

Loading...
Thumbnail Image
Authors
Francis, Preeti
Advisors
Ramanan, Prakash
Issue Date
2015-12
Type
Thesis
Keywords
Research Projects
Organizational Units
Journal Issue
Citation
Abstract

The significant increase in data storage and its consumption in today's world brings the focus on efficient query processing. It is general practice to query several data sources for k data entities based on a ranking of certain attributes associated with these entities. In our work, we consider the top-k selection query of relational databases: SELECT * FROM S ORDER BY f(t) LIMIT k We consider the special case of linear monotone preference functions f that are based only on two rank attributes in S. This is an important special case of the top-k join query, and has received much attention. We study the problem of constructing efficient indexes on S, so as to find the top-k tuples, for any given linear monotone preference function f. There are efficient algorithms in the literature to construct such an index for k=2. We present another efficient algorithm for k=2, and also an efficient algorithm for k=3. As in some previous works, our approach is based on convex layers, which are more appropriate for linear monotone preference functions.

Table of Contents
Description
Thesis (M.S.)--Wichita State University, College of Engineering, Dept. of Electrical Engineering and Computer Science
Publisher
Wichita State University
Journal
Book Title
Series
PubMed ID
DOI
ISSN
EISSN