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

    3 Citations (Scopus)

    Abstract

    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
    Volume67
    DOIs
    Publication statusPublished - 1 Feb 2017

    Keywords

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

    Cite this

    @article{c3b8c7d659ed420bb052d372e01322ba,
    title = "Voronoi-based Range-kNN search with Map Grid in a mobile environment",
    abstract = "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.",
    keywords = "Map Grid, Mobile computing, Range-kNN, Voronoi Diagram",
    author = "Zhou Shao and David Taniar and Adhinugraha, {Kiki Maulana}",
    year = "2017",
    month = "2",
    day = "1",
    doi = "10.1016/j.future.2016.03.005",
    language = "English",
    volume = "67",
    pages = "305--314",
    journal = "Future Generation Computer Systems",
    issn = "0167-739X",
    publisher = "Elsevier",

    }

    Voronoi-based Range-kNN search with Map Grid in a mobile environment. / Shao, Zhou; Taniar, David; Adhinugraha, Kiki Maulana.

    In: Future Generation Computer Systems, Vol. 67, 01.02.2017, p. 305-314.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

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

    AU - Shao, Zhou

    AU - Taniar, David

    AU - Adhinugraha, Kiki Maulana

    PY - 2017/2/1

    Y1 - 2017/2/1

    N2 - 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.

    AB - 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.

    KW - Map Grid

    KW - Mobile computing

    KW - Range-kNN

    KW - Voronoi Diagram

    UR - http://www.scopus.com/inward/record.url?scp=84962128816&partnerID=8YFLogxK

    U2 - 10.1016/j.future.2016.03.005

    DO - 10.1016/j.future.2016.03.005

    M3 - Article

    VL - 67

    SP - 305

    EP - 314

    JO - Future Generation Computer Systems

    JF - Future Generation Computer Systems

    SN - 0167-739X

    ER -