Continuous K Nearest Neighbor Queries over Moving Objects Based on Multi-Core and Multi- Threading
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [10]
  • |
  • Related
  • |
  • Cited by [1]
  • | |
  • Comments
    Abstract:

    To solve the problem of multiple continuous K nearest neighbor (KNN) queries over moving objects, considering the development of multi-core and multi-threading technologies, a two-stage framework is proposed for Multi-Threading Processing of Multiple Continuous KNN Queries (MPMCQ). This includes a preprocessing stage and a query execution stage to carry out the data updating task and the query execution task separately. In each of the stages, techniques are designed to optimize the cache access hit ratio and improve the parallelism through multi-threading. A query grouping technique in the query execution stage is proposed to improve the data temporal locality when accessing the memory. Thus, the cache hit ratio can be guaranteed. A KNN query algorithm is given based on the MPMCQ framework and the grid index for moving objects. Extensive experiments are carried out to verify that by adopting the multi-threading and the cache optimization technologies, the proposed framework implements a much superior performance than other famous algorithms; moreover, it maintains excellent performance scalability when executed under different multi-core CPUs.

    Reference
    [1] Xiong XP, Mokbel MF, Aref WG. SEA-CNN: Scalable processing of continuous K-nearest neighbor queries in spatio-temporal databases. In: Proc. of the 21st IEEE Int’l Conf. on Data Engineering. Tokyo: IEEE Computer Society, 2005. 643?654. [doi: 10.1109/ICDE.2005.128]
    [2] Yu XH, Pu KQ, Koudas N. Mointoring k-nearest neighbor queries over moving objects. In: Proc. of the 21st IEEE Int’l Conf. on Data Engineering. Tokyo: IEEE Computer Society, 2005. 631?642. [doi: 10.1109/ICDE.2005.92]
    [3] Mouratidis K, Hadjieleftheriou M, Papadis D. Conceptual partitioning: An efficient method for continuous nearest neighbor monitoring. In: Proc. of the 24th ACM SIGMOD Int’l Conf. on Management of Data. Baltimore: ACM Press, 2005. 634?645. [doi: 10.1145/1066157.1066230]
    [4] Hu HB, Xu JL, Lee DL. A generic framework for monitoring continuous spatial queries over moving objects. In: Proc. of the 24th ACM SIGMOD Int’l Conf. on Management of Data. Baltimore: ACM Press, 2005. 479?490. [doi: 10.1145/1066157.1066212]
    [5] Hsueh YL, Zimmermann R, Wang HJ, Ku WS. Partition-Based lazy updates for continuous queries over moving objects. In: Proc. of the 15th Int’l Symp. on Advances in Geographic Information Systems. Seattle: ACM Press, 2007. [doi: 10.1145/1341012.发1341060]
    [6] Mouratidis M, Yiu ML, Papadis D, Mamoulis N. Continuous nearest neighbor monitoring in road networks. In: Proc. of the 32nd Int’l Conf. on Very Large Data Bases. Seoul: ACM Press, 2006. 43?54.
    [7] Qiao L, Raman V, Reiss F, Haas PJ, Lohman GM. Main memory scan sharing for multi-core CPUs. In: Proc. of the 34th Int’l Conf. on Very Large Data Bases. Auckland: ACM Press, 2008. 610?621. [doi: 10.1145/1453856.1453924]
    [8] Shekhar S, Chawla S, Wrote; Xie KQ, Ma XJ, Yang DQ, et al., Trans. Spatial Databases A Tour. Beijing: China Machine Press, 2004 (in Chinese).
    [9] Cieslewicz J, Ross KA, Giannakakis I. Parallel buffer for chip multiprocessors. In: Proc. of the 3rd Int’l Workshop on Data Management on New Hardware. Beijing: ACM Press, 2007. [doi: 10.1145/1363189.1363192]
    [10] Sun JX, et al. Pattern Recognition. Changsha: Press of the National University of Defense Technology, 2002 (in Chinese).
    Related
    Comments
    Comments
    分享到微博
    Submit
Get Citation

赵亮,景宁,陈荦,廖巍,钟志农.面向多核多线程的移动对象连续K 近邻查询.软件学报,2011,22(8):1805-1815

Copy
Share
Article Metrics
  • Abstract:4861
  • PDF: 6172
  • HTML: 0
  • Cited by: 0
History
  • Received:August 17,2009
  • Revised:March 04,2010
You are the first2044807Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063