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

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • 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
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:August 17,2009
  • Revised:March 04,2010
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
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