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

研究成果: Conference contribution

摘要

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.

原文English
主出版物標題CIKM'11 - Proceedings of the 2011 ACM International Conference on Information and Knowledge Management
頁面795-804
頁數10
DOIs
出版狀態Published - 2011
事件20th ACM Conference on Information and Knowledge Management, CIKM'11 - Glasgow, United Kingdom
持續時間: 2011 10月 242011 10月 28

出版系列

名字International Conference on Information and Knowledge Management, Proceedings

Other

Other20th ACM Conference on Information and Knowledge Management, CIKM'11
國家/地區United Kingdom
城市Glasgow
期間11-10-2411-10-28

All Science Journal Classification (ASJC) codes

  • 決策科學 (全部)
  • 商業、管理和會計 (全部)

指紋

深入研究「Coupling or decoupling for KNN search on road networks? A hybrid framework on user query patterns」主題。共同形成了獨特的指紋。

引用此