Coupling or decoupling for KNN search on road networks? A hybrid framework on user query patterns

Ying Ju Chen, Kun-Ta Chuang, Ming Syan Chen

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

Abstract

We explore in this paper a new KNN algorithm, called the SQUARE algorithm, for searching spatial objects on road networks. Recent works in the literature discussed the necessity to support object updates for promising location-based services. Among them, the decoupling spatial search algorithms, which separate the handle of the network traversal and the object lookup, has been recognized as the most effective approach to cut the maintenance overhead from updates. However, the queue-based network traversal needs to be performed from scratch for each KNN query until the KNN objects are exactly identified, indicating that the query complexity is in proportion to the number of visited network nodes. The query efficiency is concerned for online LBS applications since they only allow lightweight operations for minimizing the query latency. To improve the query scalability while supporting data updates, SQUARE constructs the network index similar to the way used in decoupling models, and meanwhile exploit the coupling idea to maintain the KNN information relative to hot regions in the network index. The hot region denotes the area with frequent queries discovered in the query history. Inspired from the prevalently observed 80-20 rule, SQUARE can maximize the query throughput by returning KNN results in the quasi-constant time for 80% queries that are roughly issued within 20% area (hot regions). As validated in our experimental results, SQUARE outperforms previous works and achieves the significant performance improvement without sacrifice on the maintenance overhead for object updates.

Original languageEnglish
Title of host publicationCIKM'11 - Proceedings of the 2011 ACM International Conference on Information and Knowledge Management
Pages795-804
Number of pages10
DOIs
Publication statusPublished - 2011 Dec 13
Event20th ACM Conference on Information and Knowledge Management, CIKM'11 - Glasgow, United Kingdom
Duration: 2011 Oct 242011 Oct 28

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings

Other

Other20th ACM Conference on Information and Knowledge Management, CIKM'11
CountryUnited Kingdom
CityGlasgow
Period11-10-2411-10-28

All Science Journal Classification (ASJC) codes

  • Decision Sciences(all)
  • Business, Management and Accounting(all)

Fingerprint Dive into the research topics of 'Coupling or decoupling for KNN search on road networks? A hybrid framework on user query patterns'. Together they form a unique fingerprint.

Cite this