Before delving into F-Skylines, let’s discuss two of the most famous algorithms for traditional skylines: Block Nested Loop (BNL) [1]} and Sort-Filter-Skyline (SFS) [2]}, both designed for centralized settings. BNL was the first algorithm introduced to compute skylines. It adopts a naive approach, simply applying a nested-loops algorithm and confronting each tuple with all the other tuples. This, of course, results in a very inefficient algorithm, particularly for large datasets. Overall, BNL has a time complexity of \(O(N^{2})\) . A solution to this problem is SFS, which implements pre-sorting to improve efficiency in big datasets. Even though SFS is much more efficient in some cases, the overall complexity is still the same as BNL.
