Document Open Access Logo

Continuous Obstructed Detour Queries

Authors Rudra Ranajee Saha, Tanzima Hashem, Tasmia Shahriar, Lars Kulik

PDF
Thumbnail PDF

File

LIPIcs.GISCIENCE.2018.14.pdf
  • Filesize: 0.72 MB
  • 16 pages

Document Identifiers

Author Details

Rudra Ranajee Saha
  • Department of CSE, Bangladesh University of Engineering and Technology, Dhaka, Bangladesh
Tanzima Hashem
  • Department of CSE, Bangladesh University of Engineering and Technology, Dhaka, Bangladesh
Tasmia Shahriar
  • Department of CSE, Bangladesh University of Engineering and Technology, Dhaka, Bangladesh
Lars Kulik
  • Dept of CIS, University of Melbourne, Melbourne, Australia

Cite As Get BibTex

Rudra Ranajee Saha, Tanzima Hashem, Tasmia Shahriar, and Lars Kulik. Continuous Obstructed Detour Queries. In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.GISCIENCE.2018.14

Abstract

In this paper, we introduce Continuous Obstructed Detour (COD) Queries, a novel query type in spatial databases. COD queries continuously return the nearest point of interests (POIs) such as a restaurant, an ATM machine and a pharmacy with respect to the current location and the fixed destination of a moving pedestrian in presence of obstacles like a fence, a lake or a private building. The path towards a destination is typically not predetermined and the nearest POIs can change over time with the change of a pedestrian's current location towards a fixed destination. The distance to a POI is measured as the summation of the obstructed distance from the pedestrian's current location to the POI and the obstructed distance from the POI to the pedestrian's destination. Evaluating the query for every change of a pedestrian's location would incur extremely high processing overhead. We develop an efficient solution for COD queries and verify the effectiveness and efficiency of our solution in experiments.

Subject Classification

ACM Subject Classification
  • Information systems → Location based services
Keywords
  • Obstacles Continuous Detour Queries Spatial Databases

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Anika Anwar and Tanzima Hashem. Optimal obstructed sequenced route queries in spatial databases. In EDBT, pages 522-525, 2017. Google Scholar
  2. Takao Asano, Tetsuo Asano, Leonidas J. Guibas, John Hershberger, and Hiroshi Imai. Visibility of disjoint polygons. Algorithmica, 1(1):49-63, 1986. Google Scholar
  3. Ugur Demiryurek, Farnoush Banaei-Kashani, and Cyrus Shahabi. Efficient continuous nearest neighbor query in spatial networks using euclidean restriction. In SSTD, pages 25-43, 2009. Google Scholar
  4. Yunjun Gao, Jiacheng Yang, Gang Chen, Baihua Zheng, and Chun Chen. On efficient obstructed reverse nearest neighbor query processing. In SIGSPATIAL GIS, pages 191-200, 2011. Google Scholar
  5. Yunjun Gao and Baihua Zheng. Continuous obstructed nearest neighbor queries in spatial databases. In SIGMOD, pages 577-590, 2009. Google Scholar
  6. Yu Gu, Ge Yu, and Xiaonan Yu. An efficient method for k nearest neighbor searching in obstructed spatial databases. J. Inf. Sci. Eng., pages 1569-1583, 2014. Google Scholar
  7. Antonin Guttman. R-trees: a dynamic index structure for spatial searching. In SIGMOD, pages 47-57, 1984. Google Scholar
  8. Tanzima Hashem, Lars Kulik, and Rui Zhang. Countering overlapping rectangle privacy attack for moving knn queries. Inf. Syst., 38(3):430-453, 2013. Google Scholar
  9. Paul J. Heffernan and Joseph S. B. Mitchell. An optimal algorithm for computing visibility in the plane. SIAM J. Comput., 24(1):184-201, 1995. Google Scholar
  10. Chuanwen Li, Yu Gu, Jianzhong Qi, Rui Zhang, and Ge Yu. A safe region based approach to moving knn queries in obstructed space. KAIS, 45:417-451, 2015. Google Scholar
  11. Kyriakos Mouratidis, Man Lung Yiu, Dimitris Papadias, and Nikos Mamoulis. Continuous nearest neighbor monitoring in road networks. In VLDB, pages 43-54, 2006. Google Scholar
  12. Sarana Nutanong, Egemen Tanin, Jie Shao, Rui Zhang, and Ramamohanarao Kotagiri. Continuous detour queries in spatial networks. IEEE TKDE, 24:1201-1215, 2012. Google Scholar
  13. Sarana Nutanong, Rui Zhang, Egemen Tanin, and Lars Kulik. The v*-diagram: a query-dependent approach to moving KNN queries. PVLDB, 1(1):1095-1106, 2008. Google Scholar
  14. Shuo Shang, Ke Deng, and Kexin Xie. Best point detour query in road networks. In SIGSPATIAL GIS, pages 71-80, 2010. Google Scholar
  15. Nusrat Sultana, Tanzima Hashem, and Lars Kulik. Group nearest neighbor queries in the presence of obstacles. In SIGSPATIAL GIS, pages 481-484, 2014. Google Scholar
  16. Nusrat Sultana, Tanzima Hashem, and Lars Kulik. Group meetup in the presence of obstacles. Inf. Syst., 61:24-39, 2016. Google Scholar
  17. Chenyi Xia, David Hsu, and Anthony KH Tung. A fast filter for obstructed nearest neighbor queries. In BICOD, pages 203-215, 2004. Google Scholar
  18. Jin Soung Yoo and Shashi Shekhar. In-route nearest neighbor queries. GeoInformatica, 9(2):117-137, 2005. Google Scholar
  19. Jun Zhang, Dimitris Papadias, Kyriakos Mouratidis, and Manli Zhu. Spatial queries in the presence of obstacles. In EDBT, pages 366-384, 2004. Google Scholar
  20. Huaijie Zhu, Xiaochun Yang, Bin Wang, and Wang-Chien Lee. Range-based obstructed nearest neighbor queries. In SIGMOD, pages 2053-2068, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact