Anytime skyline query processing for interactive systems
Matteo Magnani, Ira Assent, Michael Lind Mortensen · 2012
In this paper we introduce the concept of anytime skyline query . The skyline database operator returns the top-1record for every possible monotone record scoring function.However, computing a skyline can be very time-consumingdepending on the size, distribution and dimensionality of the data, making this operator not applicable to interactivesystems. Therefore, we propose a new computational modelfor skyline queries where users may request a result at any time , e.g., immediately after issuing a query. With respect to previous works, this is achieved by relaxing the requirement that all the records in the result should necessarily belong to the skyline at any time. On the contrary, we allow the presence of non-skyline records as far as they are accurate (i.e., close to the actual skyline) and representative (i.e., covering dfferent portions of it). We present a firstalgorithm for anytime skyline queries aimed at increasing accuracy (in case non-skyline points are selected) and representativeness over time, and we experimentally show that the time needed to identify actual skyline points is extremely short in practice