移动对象的连续k最优有序路径查询

第28卷第7期2011年7月计算机应用与软件

ComputerApplicationsandSoftwareVol.28No．7Jul．2011

移动对象的连续k最优有序路径查询

孙冬璞

12

1

郝忠孝

1，2

（哈尔滨理工大学计算机科学与技术学院（哈尔滨工业大学计算机科学与技术学院

黑龙江哈尔滨150080）黑龙江哈尔滨150001）

要针对最优有序路径查询问题，提出了移动对象的连续k最优有序路径查询问题，并针对移动查询对象和静态数据对象的

情况，通过引入加权相对距离函数的概念提出了SCkOSR算法和DCkOSR算法。SCkOSR算法利用加权相对距离函数确定数据点与摘

移动查询对象的相对关系。DCkOSR算法进一步通过搜索区域的限制减少了计算加权相对距离函数的点的数量。实验表明，动态局部算法具有相对较好的性能。关键词

连续k最优有序路径查询

加权相对距离函数

移动对象

查询算法

THECONTINUOUSKOPTIMALSEQUENCEDROUTEQUERYFORMOVINGOBJECTS

SunDongpu

1

2

1

2

HaoZhongxiao1，

（CollegeofComputerScienceandTechnology，HarbinUniversityofScienceandTechnology，Harbin150080，Heilongjiang，China）

（CollegeofComputerScienceandTechnology，HarbinInstituteofTechnology，Harbin150001，Heilongjiang，China）

AbstractTheconceptofcontinuouskoptimalsequencedroutequeryformovingobjectsisputforwardinconsiderationoftheproblemof

optimalsequencedroutequery．TheSCkOSRandDCkOSRalgorithmsareproposedbyintroducingtheconceptofadditivelyweightedrelativedistancefunctionaimingatsuchcasesaswithamovingqueryobjectandastaticdataobject．Theadditivelyweightedrelativedistancefunctionsbetweendatapointsandmoving-queryarecalculatedbySCkOSRalgorithmtodeterminetheirrelativedistances．RestrictingsearchareasusedinDCkOSRalgorithmreducethequantityofpointsincludedinthecomputationofadditivelyweightedrelativedistancefunctions．ExperimentalresultsshowbetterperformanceoftheDCkOSRalgorithm．Keywords

Continuouskoptimalsequencedroutequery

Additivelyweightedrelativedistancefunction

Movingobject

Queryalgorithm

0引言

M2，…，Mm），2，…，m），若1≤Mi≤n（i=1，称M=（M1，

M2，…，Mm）为一个序列。

M2，…，Mm），定义2给定序列M=（M1，称M1为序列M

的起点，对应的数据集UM1为起始数据集。

［1］d

2，定义3给定R=（p1，p2，…，pr），若pi∈R（i=1，

…，r），p2，…，pr）为一条路径，称R=（p1，其长度为L（R）=

最近邻查询是时空数据库研究的重点之一，它在许多领域

占据着重要的位置，如地理信息系统、多媒体应用以及数据挖掘等。随着研究的深入，最近邻查询出现了许多变体形式，多类型

是对跨越多个数据集的最优路径最近邻查询就是其中的一种，

的求解。最优有序路径OSR（OptimalSequencedRoute）查询是

多类型最近邻查询的特例，是对在多个数据集的某种固定排列顺序下的最优路径的求解。对该类查询及其同类查询问题的研

［1－6］

，究目前已经取得了一定的成果但都是针对静态查询对象

和静态数据对象的情况提出的方法，并且只能求得一个结果。鉴于此，本文提出了移动对象的连续k最优有序路径CkOSR（ContinuouskOptimalSequencedRoute）查询的概念，并提出加权相对距离AWRD（AdditivelyWeightedRelativeDistance）函数的概念，针对移动查询对象和静态数据对象的情况给出SCkOSR算法和DCkOSR算法，最后通过实验对算法进行了性能验证。

p∑d（p，

i

i=1

r－1

i+1

），d（pi，pi+1）表示点pi和pi+1之间的最小距其中，

L（R）=0。离。当r=1时，

p2，…，pr），定义4给定路径R=（p1，称p1为路径R的起

点，记作S（R）=p1。p2，…，pr），p1，p2，…，pr）为若已知R=（p1，则pR=（p，一条以p为起点的新的路径，该路径是在R上加入新的起点形成的。

［1］

定义5给定序列M=（M1，M2，…，Mm），若路径R=（p1，p2，…，pm）满足序列M，即R中的每个点pi∈UMi（i=1，

2，…，m），则称R为基于序列M的有序路径。将基于序列M的所有有序路径的集合记作CM。

定义6

［1］

1相关概念

定义1

［1］

给定对象q以及序列M=（M1，M2，…，Mm），

收稿日期：2010－01－16。黑龙江省自然科学基金项目（F200601）。

M=（M1，给定n个数据集U1，U2，…，Un，

孙冬璞，博士生，主研领域：时空数据库理论及应用。

第1页下一页