Efficient landmark-based candidate generation for kNN queries on road networks

Tenindra Nadeeshan Abeywickrama, Muhammad Aamir Cheema

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    8 Citations (Scopus)


    The k nearest neighbor (kNN) query on road networks finds the k closest points of interest (POIs) by network distance from a query point. A past study showed that a kNN technique using a simple Euclidean distance heuristic to generate candidate POIs significantly outperforms more complex techniques. While Euclidean distance is an effective lower bound when network distances represent physical distance, its accuracy degrades greatly for metrics such as travel time. Landmarks have been used to compute tighter lower bounds in such cases, however past attempts to use them in kNN querying failed to retrieve candidates efficiently. We present two techniques to address this problem, one using ordered Object Lists for each landmark and another using a combination of landmarks and Network Voronoi Diagrams (NVDs) to only compute lower bounds to a small subset of objects that may be kNNs. Our extensive experimental study shows these techniques (particularly NVDs) significantly improve on the previous best techniques in terms of both heuristic and query time performance.

    Original languageEnglish
    Title of host publicationDatabase Systems for Advanced Applications
    Subtitle of host publication22nd International Conference, DASFAA 2017, Suzhou, China, March 27-30, 2017
    EditorsSelcuk Candan, Lijun Chang, Lei Chen, Wen Hua, Torben Bach Pedersen
    Place of PublicationCham Switzerland
    Number of pages16
    ISBN (Electronic)9783319556994
    ISBN (Print)9783319556987
    Publication statusPublished - 2017
    EventDatabase Systems for Advanced Applications 2017 - Nanlin Hotel , Suzhou, China
    Duration: 27 Mar 201730 Mar 2017
    Conference number: 22nd
    https://link-springer-com/book/10.1007/978-3-319-55753-3 (Proceedings)

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    ConferenceDatabase Systems for Advanced Applications 2017
    Abbreviated titleDASFAA 2017
    Internet address


    • Landmark lower bounds
    • Nearest neighbor
    • Road networks

    Cite this