计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2015年
5期
204-210
,共7页
王飞%秦小麟%刘亮%沈尧
王飛%秦小麟%劉亮%瀋堯
왕비%진소린%류량%침요
k-近邻连接%数据流%MapReduce%计算框架
k-近鄰連接%數據流%MapReduce%計算框架
k-근린련접%수거류%MapReduce%계산광가
kNN join%Data stream%MapReduce%Framework
k-近邻连接查询是空间数据库中一种常用的操作,该查询处理过程涉及连接和最近邻查询两个复杂操作.传统的集中式k-近邻连接查询算法已不能适应当前呈爆炸式增长的数据规模,设计分布式k-近邻连接查询算法成为了目前亟需解决的问题.现有的分布式k-近邻连接查询算法都包括了多轮串行的MapReduce任务,而每个MapReduce任务均需要读写分布式文件系统,导致MapReduce不能有效表达多个任务之间的依赖关系,因此算法效率低下.首先提出了一种基于数据流的计算框架,该框架建立在MapReduce之上,将数据处理过程按照数据流图建模.在该框架基础上,提出了一种高效的k-近邻连接算法,它利用空间填充曲线将多维数据映射为一维数据,从而将k-近邻连接查询转化为一维范围查询.实验结果表明,该算法的可扩展性较高,且效率比现有算法更优.
k-近鄰連接查詢是空間數據庫中一種常用的操作,該查詢處理過程涉及連接和最近鄰查詢兩箇複雜操作.傳統的集中式k-近鄰連接查詢算法已不能適應噹前呈爆炸式增長的數據規模,設計分佈式k-近鄰連接查詢算法成為瞭目前亟需解決的問題.現有的分佈式k-近鄰連接查詢算法都包括瞭多輪串行的MapReduce任務,而每箇MapReduce任務均需要讀寫分佈式文件繫統,導緻MapReduce不能有效錶達多箇任務之間的依賴關繫,因此算法效率低下.首先提齣瞭一種基于數據流的計算框架,該框架建立在MapReduce之上,將數據處理過程按照數據流圖建模.在該框架基礎上,提齣瞭一種高效的k-近鄰連接算法,它利用空間填充麯線將多維數據映射為一維數據,從而將k-近鄰連接查詢轉化為一維範圍查詢.實驗結果錶明,該算法的可擴展性較高,且效率比現有算法更優.
k-근린련접사순시공간수거고중일충상용적조작,해사순처리과정섭급련접화최근린사순량개복잡조작.전통적집중식k-근린련접사순산법이불능괄응당전정폭작식증장적수거규모,설계분포식k-근린련접사순산법성위료목전극수해결적문제.현유적분포식k-근린련접사순산법도포괄료다륜천행적MapReduce임무,이매개MapReduce임무균수요독사분포식문건계통,도치MapReduce불능유효표체다개임무지간적의뢰관계,인차산법효솔저하.수선제출료일충기우수거류적계산광가,해광가건립재MapReduce지상,장수거처리과정안조수거류도건모.재해광가기출상,제출료일충고효적k-근린련접산법,타이용공간전충곡선장다유수거영사위일유수거,종이장k-근린련접사순전화위일유범위사순.실험결과표명,해산법적가확전성교고,차효솔비현유산법경우.
