Abstract
dc:description.abstractA two-dimensional point p=(p.x,p.y) dominates another point p'=(p'.x,p'.y) if p.x ≥ p'.x and p.y>p'.y or p.x>p'.x and p.y ≥ p'.y. The skyline of a point set P is a subset P' ⊆ P such that every point in P' is not dominated by any other point in P. An orthogonal skyline counting query Q on a set of points P asks for the number of points on the skyline of P ⋂ Q. In this work we study data structures that support orthogonal skyline counting queries in the special case when the query range is bounded on three sides. First, we describe a linear space data structure that counts the points on the skyline of a top-open three-sided query range in O(log log n) time. We also consider a variation of the skyline problem where each of the points have some category, which we call color. An orthogonal color skyline query Q on a set of points P returns the distinct color of points on the skyline of P ⋂ Q. We achieve a solution for top-open three-sided color skyline counting query that requires O(log n/ log log n) time and linear space. Additionally, we show the reduction of four-sided skyline query to a bottom-open three-sided skyline query establishing that solving the skyline problems in a bottom-open three-sided query range is as hard as solving it for a four-sided query range. In contrast, we show that top-open three-sided skyline counting queries can be solved in just O(log log n) time. This demonstrates that for orthogonal skyline queries, although the top-open and bottom-open three-sided query ranges may seem similar, their computational complexities differ significantly.
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
-
- Kushwaha, Suruchi
- Committee members dc:contributor.committeemember
-
- Zhenlin Wang
- Ali Ebnenasir
- Contributors dc:contributor
-
- Yakov Nekrich
Subjects
dc:subject × 7Rights
- Licence dc:rights.license
Identifiers
dc:identifier.*- Identifier
- https://digitalcommons.mtu.edu/etdr/1979