Skip to content

AndreaNeti/DB2-Skyline-Challenge

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 
 
 
 
 

Repository files navigation

DB2-Skyline-Challenge

Data Bases 2 Skyline Challenge - a.a. 2022-2023
Professor: Davide Martinenghi

The challenge

The skyline algorithms we saw in class are inherently quadratic in the size of the dataset, but can we achieve sub-quadratic complexity (i.e., an overall complexity that is less than O(N²), where N is the dataset size)? Just focus on the 2-dimensional case and either

  1. Prove that no sub-quadratic algorithm can correctly compute the skyline in 2D, or
  2. Code (in a language of your choice) a correct algorithm that computes the skyline in 2D with sub-quadratic complexity.

Here is my solution in O(NlogN) that granted me 2 out of 2 extra points

About

Data Bases 2 Skyline Challenge - a.a. 2022-2023

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages