Optimized skyline queries on road networks using nearest neighbors

Maytham Hassan Safar, Dalal El-Amin, David Taniar

    Research output: Contribution to journalArticleResearchpeer-review

    12 Citations (Scopus)

    Abstract

    Skyline queries are used with data extensive applications, such as mobile location-based services, to support multi-criteria decision-making and to prune the data space by returning the most "interesting" data points. Most interesting data points are the points, which are not dominated by any other point. Spatial network skyline query is a subset of the skyline query problem where data points are nodes in a road network and the attributes of the data points are network distance relative to a set of query points. Spatial network skyline query's problem is the need to calculate the attributes with an expensive distance calculation operation. Previous works (Deng et al. Proceedings of the 23th international conference on data engineering, 796-805, 2007), Sharifzadeh et al. Proceedings of the 32nd international conference on very large databases, 751-762, 2009) that addressed this problem involved extensive network distance calculation between the query points and data points. A new algorithm that requires a remarkably less number of network distance calculations is proposed in this work. Our approach uses a progressive nearest neighbor algorithm to minimize the set of candidates then evaluates those candidates by only comparing them to a subset of discovered skyline points. Experiments showed the effectiveness of our algorithm compared to previous works.

    Original languageEnglish
    Pages (from-to)845-856
    Number of pages12
    JournalPersonal and Ubiquitous Computing
    Volume15
    Issue number8
    DOIs
    Publication statusPublished - 2011

    Keywords

    • Mobile computing
    • Nearest neighbor
    • Network Voronoi diagrams
    • Road networks
    • Skyline query

    Cite this