An efficient grid-based framework for answering tolerance-based skyline queries

Skyline queries are commonly used for database systems and mostly based on the notion of pareto-dominance. In reality, however, a user may have her/his tolerance value for each individual attribute when comparing the records, rather than a strict comparison of the respective values. This work proposes the idea of tolerance-based dominance and the associated tolerance-based skyline query (TSQ), which allows the incorporation of user-specified tolerance tuple to relax the rigidness of the classic skyline. To this end, we present the definition of tolerance-based dominance relation and the TSQ accordingly. We then exploit the relationship between pareto-based dominance and tolerance-based dominance along with grid properties to present an efficient grid-based scheme for processing a TSQ with arbitrary tolerance tuple. Our proposed technique essentially converts the TSQ processing operation into simple pareto-based dominance checking over grid space. Extensive experiments have been conducted to evaluate the performance of the proposed method.