道路网中的移动对象连续K近邻查询.pdf

《道路网中的移动对象连续K近邻查询.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第33卷第8期计算机学报v01．33No．82010年8月CHINESEJOURNALOFCOMPUTERSAug．2010道路网中的移动对象连续K近邻查询赵亮"陈荦"景宁¨廖巍2’1’(国防科学技术大学电子科学与工程学院长沙410073)2’(海军工程大学电子工程学院武汉430033)摘要已有道路网中的连续k近邻查询处理算法采用增蹙式的查询处理机制，当数据频繁更新时性能急剧下降．结合多核多线程技术，提出r一种摹于多线程的连续奁洵处理框架．该框架周期性晕计算所有查询结果。将查询处理分为顺序执行的数据更新阶段和查询执行阶

2、段，分别使用任务并行和数据并行的方法执行各阶段的操作．设计了数据更新阶段使用的数据结构，提出了查询处理阶段的k近邻查询处理策略，包含离线预计算和在线^近邻查询处理箅法两个部分．对^近邻算法复杂性及多线程处理框架的加速比进行了理论分析．实验结果表明，提出的算法在数据频繁更新下，串行执行时性能优于已有算法，而基于多线程处理框架的并行执行在任何参数配置下性能均优于已有算法；且基于多线程处理框架的并行执行具有较好的性能扩展性，加速比可以达到1．51～1．7．关键词移动对象；道路网；连续k近邻查询；多线程；频繁更新中图法分类号T

3、P392DOI号：10．3724／SP．J．1016．2010．01396ContinuousKNearestNeighborQueriesofMovingObjectsinRoadNetworksZHA0Lian91’CHENLuo”JINGNin91’LIAOWei2’’(CollegeofElectronicScienceandEngineering。NationalUniversityofDefPnseTechnology，Changsha410073)”(CollegeofElectronicEngineer

4、ing。NavyUniversityofEngineering，Wuhan430033)AbstractExistingalgorithmsforcontinuous正一nearestneighbor(kNN)queriesofmovingobjectsinroadnetworksadopttheincrementalquerymechanism．whichisverifiedtobeinefficientwhendataupdatefrequently．Consideringtheubiquitousmulti—co

5、reandmulti—threadingtechnologies，amulti—threadingbasedframeworkforcontinuouskNNqueriesofmovingobjectsisproposed．Intheframework，allthequeriesarere-evaluatedperiodically，andthequeryprocessisdividedintotWOsequentialphases：thedataupdatingphaseandthequeryexecutionpha

6、se，taskparallelanddataparallelmechanismareusedrespectivelyineachphasetocarryoutthecorrespondingopera—tions．Intheupdatingphase，thedatastructuresusedintheframeworkaredesigned．Moreover，intheexecutionphaseakNNquerystrategyisproposedwhichincludesanoff·-linepre——compu

7、ta‘‘tionandanon—linequeryalgorithm．Thecomputationalcomplexityofthealgorithmandthespeedupoftheframeworkareanalyzedtheoretically．Experimentalresultsshowthat，underthefrequentupdateenvironment，theproposedqueryalgorithmwhenseriallyexecutedhasbetterperformancethanthet

8、raditionalalgorithms，however，themulti—threadingbasedparallelexecu—tionisbetterinallkindsofparametersetups；what’smore，themulti—threadingbasedparallelexecutionmaintains