Computing Skyline Using Taxicab Geometry

Skyline computation is relevant in multi-criteria decision making where the criteria are inversely proportional to each other. Skyline is generally computed using dominance analysis and applicable in a situation where shortest distance is computed with respect to a point of importance. In real life scenarios different cost parameters are obviously high for the points which are designated as "important" where as users search for the points which are generally of low cost. These types of inverse conditions are managed in skyline computation. Existing research works majorly apply shortest distance calculation for searching the points of importance and it is assumed that the points are connected without any obstructions. However in practical cases this assumption is often wrong as different obstacles or barriers exist between the points or places. In this research work we use Taxicab distance calculation to consider the presence of obstacles and apply it to compute skyline of geographically dispersed data.

I. Introduction

Data centric applications based on relational model fetch data using SQL queries. The criteria for fetching data may be simple or complex in nature. Some of the complex queries may involve multi-criteria decision makings, where the criteria are inversely proportional to each other. Optimization on these types of multi-criteria decision makings cannot be optimized directly using SQL. One of the solutions of this type of problem is to identify the best point of one dimension (corresponds to attribute) and rank all the other points according to that.