VIP-tree

An effective index for indoor spatial queries

    Research output: Contribution to journalArticleResearchpeer-review

    3 Citations (Scopus)

    Abstract

    Due to the growing popularity of indoor location-based services, indoor data management has received significant research attention in the past few years. However, we observe that the existing indexing and query processing techniques for the indoor space do not fully exploit the properties of the indoor space. Consequently, they provide below par performance which makes them unsuitable for large indoor venues with high query workloads. In this paper, we propose two novel indexes called Indoor Partitioning Tree (IP-Tree) and Vivid IP-Tree (VIP-Tree) that are carefully designed by utilizing the properties of indoor venues. The proposed indexes are lightweight, have small pre-processing cost and provide near-optimal performance for shortest distance and shortest path queries. We also present efficient algorithms for other spatial queries such as k nearest neighbors queries and range queries. Our extensive experimental study on real and synthetic data sets demonstrates that our proposed indexes outperform the existing algorithms by several orders of magnitude.
    Original languageEnglish
    Pages (from-to)325-336
    Number of pages12
    JournalProceedings of the VLDB Endowment
    Volume10
    Issue number4
    DOIs
    Publication statusPublished - Nov 2016

    Cite this

    @article{43bc48a29c07446ab1f4835242ab9f54,
    title = "VIP-tree: An effective index for indoor spatial queries",
    abstract = "Due to the growing popularity of indoor location-based services, indoor data management has received significant research attention in the past few years. However, we observe that the existing indexing and query processing techniques for the indoor space do not fully exploit the properties of the indoor space. Consequently, they provide below par performance which makes them unsuitable for large indoor venues with high query workloads. In this paper, we propose two novel indexes called Indoor Partitioning Tree (IP-Tree) and Vivid IP-Tree (VIP-Tree) that are carefully designed by utilizing the properties of indoor venues. The proposed indexes are lightweight, have small pre-processing cost and provide near-optimal performance for shortest distance and shortest path queries. We also present efficient algorithms for other spatial queries such as k nearest neighbors queries and range queries. Our extensive experimental study on real and synthetic data sets demonstrates that our proposed indexes outperform the existing algorithms by several orders of magnitude.",
    author = "Zhou Shao and Cheema, {Muhammad Aamir} and David Taniar and Hua Lu",
    year = "2016",
    month = "11",
    doi = "10.14778/3025111.3025115",
    language = "English",
    volume = "10",
    pages = "325--336",
    journal = "Proceedings of the VLDB Endowment",
    issn = "2150-8097",
    publisher = "VLDB Endowment",
    number = "4",

    }

    VIP-tree : An effective index for indoor spatial queries. / Shao, Zhou; Cheema, Muhammad Aamir; Taniar, David; Lu, Hua.

    In: Proceedings of the VLDB Endowment, Vol. 10, No. 4, 11.2016, p. 325-336.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

    T1 - VIP-tree

    T2 - An effective index for indoor spatial queries

    AU - Shao, Zhou

    AU - Cheema, Muhammad Aamir

    AU - Taniar, David

    AU - Lu, Hua

    PY - 2016/11

    Y1 - 2016/11

    N2 - Due to the growing popularity of indoor location-based services, indoor data management has received significant research attention in the past few years. However, we observe that the existing indexing and query processing techniques for the indoor space do not fully exploit the properties of the indoor space. Consequently, they provide below par performance which makes them unsuitable for large indoor venues with high query workloads. In this paper, we propose two novel indexes called Indoor Partitioning Tree (IP-Tree) and Vivid IP-Tree (VIP-Tree) that are carefully designed by utilizing the properties of indoor venues. The proposed indexes are lightweight, have small pre-processing cost and provide near-optimal performance for shortest distance and shortest path queries. We also present efficient algorithms for other spatial queries such as k nearest neighbors queries and range queries. Our extensive experimental study on real and synthetic data sets demonstrates that our proposed indexes outperform the existing algorithms by several orders of magnitude.

    AB - Due to the growing popularity of indoor location-based services, indoor data management has received significant research attention in the past few years. However, we observe that the existing indexing and query processing techniques for the indoor space do not fully exploit the properties of the indoor space. Consequently, they provide below par performance which makes them unsuitable for large indoor venues with high query workloads. In this paper, we propose two novel indexes called Indoor Partitioning Tree (IP-Tree) and Vivid IP-Tree (VIP-Tree) that are carefully designed by utilizing the properties of indoor venues. The proposed indexes are lightweight, have small pre-processing cost and provide near-optimal performance for shortest distance and shortest path queries. We also present efficient algorithms for other spatial queries such as k nearest neighbors queries and range queries. Our extensive experimental study on real and synthetic data sets demonstrates that our proposed indexes outperform the existing algorithms by several orders of magnitude.

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

    U2 - 10.14778/3025111.3025115

    DO - 10.14778/3025111.3025115

    M3 - Article

    VL - 10

    SP - 325

    EP - 336

    JO - Proceedings of the VLDB Endowment

    JF - Proceedings of the VLDB Endowment

    SN - 2150-8097

    IS - 4

    ER -