Efficient evaluation of shortest average distance query on heterogeneous neighboring objects in road networks

Yuan Ko Huang, Chiang Lee, Chun Hsing Su, Chu Hung Ho

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Recently, the research community has introduced various methods for processing the location-based queries on a single type of objects in road networks. However, in real-life applications user may be interested in obtaining information about different types of objects, in terms of their neighboring relationship. The sets of different types of objects closer to each other are termed the heterogeneous neighboring object sets (HNOSs for short). In this paper, we present a novel type of location-based queries, the shortest average distance query (SADQ for short), on the HNOSs in road networks. Given a query object q and a distance d, the SADQ retrieves a HNOS, such that the road distances between any two objects in this set are less than or equal to d and its average road distance to q is the shortest among all HNOSs.As the SADQ provides object information by preserving both the spatial closeness of objects to the query object and the neighboring relationship between objects, it is useful in many fields and application domains. A grid index is first designed to manage information of data objects and road networks, and then the SADQ algorithm is developed, which is combined with the grid index to efficiently process the SADQ. Extensive experiments using real road network datasets demonstrate the efficiency of the proposed SADQ algorithm.

Original languageEnglish
Title of host publicationProceedings of the 21st International Database Engineering and Applications Symposium, IDEAS 2017
EditorsJun Hong, Richard McClatchey, Bipin C. Desai
PublisherAssociation for Computing Machinery
Pages209-218
Number of pages10
ISBN (Electronic)9781450352208
DOIs
Publication statusPublished - 2017 Jul 12
Event21st International Database Engineering and Applications Symposium, IDEAS 2017 - Bristol, United Kingdom
Duration: 2017 Jul 122017 Jul 14

Publication series

NameACM International Conference Proceeding Series
VolumePart F129476

Other

Other21st International Database Engineering and Applications Symposium, IDEAS 2017
CountryUnited Kingdom
CityBristol
Period17-07-1217-07-14

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Efficient evaluation of shortest average distance query on heterogeneous neighboring objects in road networks'. Together they form a unique fingerprint.

  • Cite this

    Huang, Y. K., Lee, C., Su, C. H., & Ho, C. H. (2017). Efficient evaluation of shortest average distance query on heterogeneous neighboring objects in road networks. In J. Hong, R. McClatchey, & B. C. Desai (Eds.), Proceedings of the 21st International Database Engineering and Applications Symposium, IDEAS 2017 (pp. 209-218). (ACM International Conference Proceeding Series; Vol. Part F129476). Association for Computing Machinery. https://doi.org/10.1145/3105831.3105848