空间数据库最优位置查询算法研究

1
引言
在地理信息系统、 决策支持、 智能运输和资源调度等实际
2
问题定义
按照上述应用， 提出了一种新颖的空间查询类型——最优
应用中， 空间数据库扮演着重要的角色。空间数据库不仅能 够存储点、 线段、 矩形和多边形等空间数据对象， 而且支持数 据模型、 索引和查询操作。 近年来， 数据库领域的学者们提出了众多类型的空间数 据库查询算法， 具有代表性的空间查询包括最近邻查询、 范围 查询、 连接查询和最近对查询等[1-4]。 除了这些查询类型之外， 存在一些使用空间数据的实际 应用， 有待利用空间查询技术高效地解决它们。考虑下面应 用示例。为了保证公共安全， 需要将有限数量的救生员策略 地部署在最繁忙的海域上。救生员的部署位置应该尽量紧邻 容易发生溺水事故的海域， 假设救生员负责的救生区域用 R 表 示， 容易发生溺水事故的海域位置 ai 的集合用 A 表示， 救生员 的最长有效救生距离用 d 表示， 可能部署救生员所的位置 bj 的 集合用 B 表示。与救生员的部署位置 bj 距离不超过 d 的事故海 域位置 ai 组成的集合为 {ai|ai Î A Ù ai Î R Ù distt (ai b j) £ d }， 该 集合的元素个数越多， 说明部署位置 b j 越适合。
b2.x－d 0 1 2 b5 b2 3 4 b2.x+d a6 5 b1 b5.x+d a3 a2 a7 6 7 8 9 10 b3 x
å distt (ai b j) 。目标对象 b j 的累 a Î OS (b )
i j
加距离 AD （b） 目标对象 bj 的优先权越高。在图 1 中， 虽 j 越小， 然 |OS （b1） |=|OS （b5） |=2 ， 但是 b1 的优先权大于 b5， 这是因为 AD （b1） <AD （b5） ， 其中： AD （b1） =dist（ b1） +dist（ b1） =0.7+1.2=2.1 2 a3 ， 2 a4， AD （b5） =dist（ b5） +dist（ b5） =1.5+1.1=2.6 2 a4 ， 2 a1， 定义 3 （优先权） 设数据对象集合 A， 目标对象集合 B， 查询区域 R， 临界距离 d ， bj Î B Ù bj Ï R， 目标对象 b1， 47 （18）
Computer Engineering and Applications 计算机工程与应用
R2 R a1 R3 a4 a7 a2 R6 R5 a5 a8 R3 R3 a1 a4 RA R4 R4 a3 a6 R1 R2 R5 R5 a5 a8 R6 R6 a2 a7
Î Rd， 定义 1 （距离函数[5]） 设点 p= （p1， p2， …， pd） 点 q= （q1，
q2， …， qd ）Î Rd， 点 p 到点 q 的距离定义为 dist（ q ） = （ |p1 － q1|t + t p，
t |p2 － q2|t + … + |pd － qd|t）1/（ 1≤t<∞ ）， 当 t=∞ 时 dist ∞（p ， q）=
PR(b j) = |OS (b j)| AD(b j) d ´ |OS (b j)| + 1
定义 4 （最优位置查询） 设数据对象集合 A， 目标对象集合 B， 查询区域 R， 临界距离 d， 最优位置查询返回具有最大优先 权的目标对象 bj， 其满足 ("b′j Î B Ù b′j Î R)PR(b j) > PR(b′j) 。 定义 5 （k 最优位置查询） 设数据对象集合 A， 目标对象集
优位置查询概念， 提出目标对象的优先权度量标准、 删减数据对象的启发式规则和最优位置查询算法， 分析最优位置查询算法的 时间复杂度。实验结果表明， 在参数不同取值情况下最优位置查询算法的查询性能仍然高效。 关键词： 空间数据库； 最优位置查询； 优先权； 启发式规则； 查询算法 DOI： 10.3778/j.issn.1002-8331.2011.18.006 文章编号： 1002-8331 （2011） 18-0019-03 文献标识码： A 中图分类号： TP311
max1≤i≤d{|pi－qi|}。 距离函数 dist（ q） 是衡量 d 维空间中两点之间距离的标 t p， 准， 当 t=1 时 dist（ q） 表示曼哈顿距离； 当 t=2 时 dist（ q） 表 1 p， 2 p， 示欧几里得距离； 当 t=∞时 dist∞ （p， q） 表示车比雪夫距离。 定义 2 （最优集） 设数据对象集合 A={a1， a2， …， an}， 目标 对象集合 B={b1， b2， …， bm}， 查询区域 R 和临界距离 d， 目标对 象 bj 的最优集 OS （b） （ b） j 定义为{ai|aiÎ A Ù aiÎ R Ù dist t ai， j £ d}|。 当两个目标对象的最优集包含的元素相同时， 目标对象 到其最优集中每个元素的距离之和决定其优先权。通常， 距 离救生员部署位置较近的易发事故地点更容易救援。从救生 员部署位置 bj 到其最优集 OS （b） j 中所有的易发事故地点 ai 的 累加距离表示为 AD(b j) =
a6 R4 R1 a3
图 3 数据对象对应的 R 树 RA
b2 R4 b5 R1 b6 R3 R b1 b3 b8 R5 R2 b7 b4 R3 R6 R3 b1 b6 RB R4 b2 R4 b5 R1 R2 R5 R5 b3 b8 R6 R6 b4 b7
图 4 数据对象对应的 R 树 RB
数据对象， 将它们保存在队列 SA 中； 然后， 利用基于 R 树的范围 查询算法查询目标对象集合 B 中到查询区域 R 的最短距离小 于等于 d 的所有目标对象， 将它们保存在队列 SB 中； 接下来， 对 队列 SB 中的每个目标对象利用启发式规则遍历队列 SA， 从而 求得其优先集， 同时计算目标对象的优先权。 不使用启发式规则， 队列 SB 中每个目标对象需要与队列 SA 中每个数据对象进行距离计算， 因此， 该操作的时间复杂度 为O （|SA|×|SB|） 。然而， 只有那些到目标对象 bj 的距离小于等 于临界距离 d 的数据对象才属于 bj 的优先集。为了避免存取 队列 SA 中所有的数据对象， 提出一条启发式规则。 启发式规则： 首先， 判断队列 SA 中所有数据对象在哪一维 上坐标值的取值范围最大。然后， 将队列 SA 和 SB 中的对象按 照具有最大范围的维度值进行排序。设 maxi 和 mini 表示对象 在维度 i 上的最大和最小坐标值， 第 i 维坐标具有最大范围， 则 满足 ("j ¹ i) maxi - mini ³ max j - min j 。如果数据对象 a 和目 标对象 b 在第 i 维上的坐标距离大于 d， 那么数据对象 a 到目标 对象 b 的距离比定大于 d。数据对象 a 不属于目标对象 b 的优 先集。 在图 2 中 SA={a6， a3， a2， a7}， SA 中数据对象沿着 x 轴坐标 值的区间大于沿着 y 轴坐标值的区间， 因此， 在 SA 和 SB 中对 象按照 x 轴坐标值的升序进行排序， 排序结果如图 5 如示。 如果 |b.x-a.x|>d， 那么能够保证 dist（ a） >d， 因此 a 将从 b 的 2 b， 优先集中排除。没有排序之前， 目标对象 b2 需要与 SA 中所有 4 个数据对象计算距离， 然而， 数据对象按照 x 轴坐标值排序 之后， 只有对象 a6 的 x 坐标值位于区间 [b2.x － 2 ， b2.x+2] ， 只需 要计算 b2 和 a6 之间的距离。启发式规则大大减少了距离计 算次数。
位置查询。最优位置查询返回具有最高优先权的位置。提出优 先权度量标准和最优位置查询形式化定义之前， 首先使用图 1 示 例的最优位置查询类型。对于指定的救生员部署位置 bj， 只有距 离救生员位置 bj 不超过长度 d 的易发事故的海滩位置 ai， 救生员 才能够及时有效地救援。从救生员部署位置 bj 出发能够救援的 位置 ai 组成 bj 的优先集， 记作 OS （b） （b） j 。优先集 OS j 包含的元素 越多， 救生员部署位置 bj 的优先权越高。位置 b1 的优先权大于位 置 b3的优先权， 因为|OS （b1） |=|{a3， a4}|=2， |OS （b3） |=|{a2}|=1。
9 8 7 6 5 4 3 2 1
d b5
b4 d a1 R a4 a3 d b2 d a2 b3 d
y
b1
0 1 2 3 4 5 6 7 8 9 x
图 1 最优位置查询图
基金项目： 国家自然科学基金 （the National Natural Science Foundation of China under Grant No.60803036） ； 黑龙江省自然科学基金 （No.F200903） ； 黑龙江省教育厅科学技术研究项目 （No.11533049） 。 作者简介： 徐红波 （1980—） ， 男， 博士， 讲师， 研究方向： 空间数据库查询算法； 韩启龙 （1974—） ， 男， 博士， 副教授， 硕士生导师； 潘海为 （1974—） ， 男， 博士， 副教授， 硕士生导师。E-mail： x_h_b@ 收稿日期： 2011-02-21； 修回日期： 2011-04-22
Computer Engineering and Applications 计算机工程与应用
2011， 47 （18）
19
空间数据库最优位置查询算法研究
徐红波 1， 韩启龙 2， 潘海为 2 XU Hongbo1， HAN Qilong2， PAN Haiwei2
1.哈尔滨商业大学 计算机与信息工程学院， 哈尔滨 150028 2.哈尔滨工程大学 计算机科学与技术学院， 哈尔滨 150001 1.College of Computer and Information Engineering， Harbin University of Commerce， Harbin 150028， China 2.College of Computer Science and Technology， Harbin Engineering University， Harbin 150001， China XU Hongbo， HAN Qilong， PAN Haiwei.Research on best location query algorithm in spatial puter Engineering and Applications， 2011， 47 （18） ： 19-21. Abstract：As to the demand of real application， this paper presents a new kind of spatial query type， best location query.After describing real application， it presents the best location query， the priority of target object， the heuristic rule to delete data objects， and analyzes the time complexity of the algorithm.The experimental result shows that the query efficiency of the optimal location query algorithm remains effective with the parameters varying. Key words：spatial database； best location query； priority； heuristic rule； query algorithm 摘 要： 针对实际应用的查询要求， 提出一种新颖的空间数据库查询类型—最优位置查询。在叙述实际应用的基础上抽象出最