支持频繁位置更新的不确定移动对象索引策略.pdfVIP

第 35卷 第 12期 计 算 机 学 报 Vol|35 No．12 2012年 12月 CHINESEjoURNAIOFCOMPUTERS Dec．2012 支持频繁位置更新的不确定移动对象索引策略 丁晓锋 金 海 赵 娜 (华中科技大学服务计算技术与系统教育部重点实验室 武汉 430074) (华中科技大学集群与网格计算湖北省重点实验室 武汉 430074) 摘 要 移动数据采集和处理技术的迅速发展给研究人员提出了新的应用需求，如何在频繁位置更新应用中索引 不确定移动对象的当前及未来位置信息成为当前的研究热点之一．TPu树是针对不确定移动对象的当前及未来 位置信息索引的策略，其具有较高的概率域查询效率，但是其采用的传统 自顶向下更新算法，存在频繁位置更新效 率低下的问题．通过在 TPU树上增加一个记录不确定移动对象状态特征的更新备忘录 (UM)内存结构，文中提出 了一种支持频繁位置更新的不确定移动对象索引策略 TPu M树 ，并在此基础之上提 出了一种改进 的基于备忘录 (MMBU／I)的更新 ／插入算法．代价分析和实验仿真表明，采用 MMBU／I算法的TPuM 树频繁更新性能大大优 于TPU树和 ABx树索引，且概率查询性能与传统索引大致相当，因此具有很好的实用价值和广泛的应用前景． 关键词 不确定移动对象；索引结构 ；基于备忘录更新 ；TPu树 ；概率查询 中图法分类号 TP392 DOI号：10．3724／SP．J．1016．2012．02587 IndexingofUncertainMoving0bjectswithFrequentUpdates DING Xiao—Feng JIN Hai ZHAONa (KeyLaboratoryofServicesComputingTechnologyandSystemo{MinistryofEducation， HuazhongUniversityofScienceandTechnology，Wuhan 430074) (KeyLaboratoryofClusterandGridComputingofHubeiProvince，HuazhongUniversityofScienceandTechnology，Wuhan 430074) Abstract Therapidadvancesinmobiledatacollectingandprocessingtechnologyhasproposed theresearchersnew challenges：how tomonitor the currentand futurepositionsofuncertain movingobjectsunderfrequentandhighextentupdates．TPU—treeiscurrentlyapopularindexing methodforthecurrentandfuturepositionsofuncertainmovingobjects．Itcanspeeduptheprob— abilisticrangequery efficiency，butthetraditionaltop—down updatemethod ofTPU～treehas madeitsfrequentupdatesperformanceverylow．Inthispaper，weproposetheTPU M —treefor movingobjectswithfrequentupdates。whichisbasedonTPU—tree．supplementedbyamemory— basedupdate—memostructurerecordingthestateofuncertainmovingobjects．Furthermore，a modifie