Voronoi-based Range-kNN search with Map Grid in a mobile environment

Zhou Shao, David Taniar, Kiki Maulana Adhinugraha

    Research output: Contribution to journalArticleResearchpeer-review

    10 Citations (Scopus)


    Mobile Computing, which attracts a large amount of users, allows users to access mobile information services through spatial queries. For this large group of mobile users, they are expecting more efficient information services, which requires the query results to be retrieved in a short time period. In this paper, we propose an efficient Voronoi-based Range-kNN search algorithm with constructing a Map Grid (MG). With MG, the query range can be derived in a short time period even when the mobile user is moving, as well as finding the first nearest neighbours for the Range-kNN query. Then for searching the objects outside the query range, a Voronoi-based algorithm is used. We have proved that our algorithm is more efficient than Range-kNN algorithms which use irregular polygons or even irregular shapes as the query range. Meanwhile, in the evaluation part, the overall performance of our search algorithm is proved to be quite efficient.

    Original languageEnglish
    Pages (from-to)305-314
    Number of pages10
    JournalFuture Generation Computer Systems
    Publication statusPublished - 1 Feb 2017


    • Map Grid
    • Mobile computing
    • Range-kNN
    • Voronoi Diagram

    Cite this