k-nearest neighbors on road networks

A journey in experimentation and in-memory implementation

Tenindra Abeywickrama, Muhammad Aamir Cheema, David Taniar

    Research output: Contribution to journalArticleResearchpeer-review

    27 Citations (Scopus)

    Abstract

    A k nearest neighbor (kNN) query on road networks retrieves the k closest points of interest (POIs) by their network distances from a given location. Today, in the era of ubiquitous mobile computing, this is a highly pertinent query. While Euclidean distance has been used as a heuristic to search for the closest POIs by their road network distance, its efficacy has not been thoroughly investigated. The most recent methods have shown significant improvement in query performance. Earlier studies, which proposed disk-based indexes, were compared to the current state-of-the-art in main memory. However, recent studies have shown that main memory comparisons can be challenging and require careful adaptation. This paper presents an extensive experimental investigation in main memory to settle these and several other issues. We use efficient and fair memory-resident implementations of each method to reproduce past experiments and conduct additional comparisons for several overlooked evaluations. Notably we revisit a previously discarded technique (IER) showing that, through a simple improvement, it is often the best performing technique.

    Original languageEnglish
    Pages (from-to)492-503
    Number of pages12
    JournalProceedings of the VLDB Endowment
    Volume9
    Issue number6
    DOIs
    Publication statusPublished - Jan 2016

    Cite this

    @article{2346b55659f7466b86590c61e716710e,
    title = "k-nearest neighbors on road networks: A journey in experimentation and in-memory implementation",
    abstract = "A k nearest neighbor (kNN) query on road networks retrieves the k closest points of interest (POIs) by their network distances from a given location. Today, in the era of ubiquitous mobile computing, this is a highly pertinent query. While Euclidean distance has been used as a heuristic to search for the closest POIs by their road network distance, its efficacy has not been thoroughly investigated. The most recent methods have shown significant improvement in query performance. Earlier studies, which proposed disk-based indexes, were compared to the current state-of-the-art in main memory. However, recent studies have shown that main memory comparisons can be challenging and require careful adaptation. This paper presents an extensive experimental investigation in main memory to settle these and several other issues. We use efficient and fair memory-resident implementations of each method to reproduce past experiments and conduct additional comparisons for several overlooked evaluations. Notably we revisit a previously discarded technique (IER) showing that, through a simple improvement, it is often the best performing technique.",
    author = "Tenindra Abeywickrama and Cheema, {Muhammad Aamir} and David Taniar",
    year = "2016",
    month = "1",
    doi = "10.14778/2904121.2904125",
    language = "English",
    volume = "9",
    pages = "492--503",
    journal = "Proceedings of the VLDB Endowment",
    issn = "2150-8097",
    publisher = "VLDB Endowment",
    number = "6",

    }

    k-nearest neighbors on road networks : A journey in experimentation and in-memory implementation. / Abeywickrama, Tenindra; Cheema, Muhammad Aamir; Taniar, David.

    In: Proceedings of the VLDB Endowment, Vol. 9, No. 6, 01.2016, p. 492-503.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

    T1 - k-nearest neighbors on road networks

    T2 - A journey in experimentation and in-memory implementation

    AU - Abeywickrama, Tenindra

    AU - Cheema, Muhammad Aamir

    AU - Taniar, David

    PY - 2016/1

    Y1 - 2016/1

    N2 - A k nearest neighbor (kNN) query on road networks retrieves the k closest points of interest (POIs) by their network distances from a given location. Today, in the era of ubiquitous mobile computing, this is a highly pertinent query. While Euclidean distance has been used as a heuristic to search for the closest POIs by their road network distance, its efficacy has not been thoroughly investigated. The most recent methods have shown significant improvement in query performance. Earlier studies, which proposed disk-based indexes, were compared to the current state-of-the-art in main memory. However, recent studies have shown that main memory comparisons can be challenging and require careful adaptation. This paper presents an extensive experimental investigation in main memory to settle these and several other issues. We use efficient and fair memory-resident implementations of each method to reproduce past experiments and conduct additional comparisons for several overlooked evaluations. Notably we revisit a previously discarded technique (IER) showing that, through a simple improvement, it is often the best performing technique.

    AB - A k nearest neighbor (kNN) query on road networks retrieves the k closest points of interest (POIs) by their network distances from a given location. Today, in the era of ubiquitous mobile computing, this is a highly pertinent query. While Euclidean distance has been used as a heuristic to search for the closest POIs by their road network distance, its efficacy has not been thoroughly investigated. The most recent methods have shown significant improvement in query performance. Earlier studies, which proposed disk-based indexes, were compared to the current state-of-the-art in main memory. However, recent studies have shown that main memory comparisons can be challenging and require careful adaptation. This paper presents an extensive experimental investigation in main memory to settle these and several other issues. We use efficient and fair memory-resident implementations of each method to reproduce past experiments and conduct additional comparisons for several overlooked evaluations. Notably we revisit a previously discarded technique (IER) showing that, through a simple improvement, it is often the best performing technique.

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

    U2 - 10.14778/2904121.2904125

    DO - 10.14778/2904121.2904125

    M3 - Article

    VL - 9

    SP - 492

    EP - 503

    JO - Proceedings of the VLDB Endowment

    JF - Proceedings of the VLDB Endowment

    SN - 2150-8097

    IS - 6

    ER -