Back to search

Michigan Technological University

ORTHOGONAL RANGE SKYLINE QUERIES

Abstract

dc:description.abstract

Given a set of points P, we often need to report the ones that lie within a certain query range Q. This is referred to as orthogonal range reporting. We can also go further, reporting only the dominant points within that query. In 2 dimensions, a point p1 = (x1, y1) dominates a point p2 = (x2, y2) iff x1 ≥ x2 and y1 > y2 or x1 > x2 and y1 ≥ y2. The set of all dominant points within a query range is called the skyline of that query. There are several different variants of skyline queries. For example, we can consider each point in P to be colored. Given a query range Q, can we efficiently count the number of points of each color in the skyline? In this thesis, we will present a new O( log n log log n + D log log n) method for doing so. The method is possible thanks to a new reduction from skyline queries to orthogonal range queries. We will also explore novel algorithms for answering skyline query variants in the I/O model of computation, making use of techniques such as Ganguly et al.’s [2] double-chaining method and Alstrup et al.’s [14] grid approach. By applying these existing techniques in new ways, we can not only derive our own efficient algorithms for skyline queries, but also explore potential avenues for future research

Degree

thesis:*
Name thesis:degree_name
Master of Science in Computer Science (MS)
Level thesis:degree_level
Open Access Master's Thesis
Discipline thesis:degree_discipline
Department of Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Murembya, Saano
Committee members dc:contributor.committeemember
  • Zhenlin Wang
  • Ali Ebnenasir
Contributors dc:contributor
  • Yakov Nekrich

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Michigan Technological University
Base URL
digitalcommons.mtu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Murembya, Saano. ORTHOGONAL RANGE SKYLINE QUERIES. Open Access Master's Thesis thesis, https://doi.org/10.37099/mtu.dc.etdr/1536