Wireless Communications and Mobile Computing (Jan 2021)

Tree Index Nearest Neighbor Search of Moving Objects along a Road Network

  • Wei Jiang,
  • Fangliang Wei,
  • Guanyu Li,
  • Mei Bai,
  • Yongqiang Ren,
  • Jingmin An

DOI
https://doi.org/10.1155/2021/2050489
Journal volume & issue
Vol. 2021

Abstract

Read online

With the widespread application of location-based service (LBS) technology in the urban Internet of Things, urban transportation has become a research hotspot. One key issue of urban transportation is the nearest neighbor search of moving objects along a road network. The fast-updating operations of moving objects along a road network suppress the query response time of urban services. Thus, a tree-indexed searching method is proposed to quickly find the answers to user-defined queries on frequently updating road networks. First, a novel index structure, called the double tree-hash index, is designed to reorganize the corresponding relationships of moving objects and road networks. Second, an index-enhanced search algorithm is proposed to quickly find the k-nearest neighbors of moving objects along the road network. Finally, an experiment shows that compared with state-of-the-art algorithms, our algorithm shows a significant improvement in search efficiency on frequently updating road networks.