| 主权项 |
一种空间数据库中排序反向轮廓查询方法：其特征在于该方法的步骤如下：步骤(1)：选择数据库管理系统，并开发一个空间数据库引擎，选用空间数据库索引技术；步骤(2)：开发排序反向轮廓查询过滤引擎；步骤(3)：开发基于动态轮廓裁剪和全局轮廓裁剪的排序反向轮廓查询裁剪引擎，消除步骤(3)中得到的不是最终结果的对象；步骤(4)：开发排序引擎对查询结果进行合并，并按顺序得到最终的查询结果；所述的步骤(1)中选用的数据库管理系统平台支持基本的SQL查询；空间数据库引擎是构建在应用层和数据库层之间的中间件，所述的中间件与选用的数据库管理系统相互配合；空间数据库索引选用R树；所述的步骤(2)中的排序反向轮廓查询过滤引擎，主要是得到排序反向轮廓的一个候选集，即第一层全局轮廓；此外，步骤(2)还需求得第二层全局轮廓，以便在步骤(3)中用来裁剪，计算第一层全局轮廓和第二层全局轮廓的算法如下：2.1)初始化一个最小堆，并将根结点放入堆，该最小堆根据用户给定的距离计算方式所计算的值进行排序；初始化两个对象集合，一个用来保存第一层全局轮廓，另外一个用来保存第二层全局轮廓；2.2)如果最小堆为空，则过滤算法结束，返回两个对象集合，即第一层和第二层全局轮廓；否则取出堆顶元素；2.3)判断取出的堆顶元素被已经找到的第一层和第二层全局轮廓点所全局控制的次数；对于R树索引结点被全局控制的次数，需分两种情况考虑：A)该R树索引结点是中间索引结点，这种状况下根据其被全局控制的次数分为两种：A1)该中间索引结点最多只被一个第一层全局轮廓点所全局控制，那么对于其下的索引孩子结点都加入到最小堆中，并跳到2.2)；A2)该中间索引结点被第一层全局轮廓点所全局控制的次数大于1，那么对于其下的索引孩子结点不做任何操作，并跳到2.2)；B)该R树索引结点是数据索引结点，这种状况下根据其被全局控制的次数分为三种情况：B1)该数据索引结点没有被任何一个已找到的全局轮廓点所全局控制，那么将该数据索引结点加入到第一层全局轮廓结果列表中并跳到2.2)；B2)该数据索引结点被一个已找到的第一层和第二层全局轮廓点所全局控制，那么将该数据索引结点加入到第二层全局轮廓结果列表中并跳到2.2)；B3)该数据索引结点被已找到的第一层和第二层全局轮廓点所全局控制的次数大于1，那么对于该数据索引结点不做任何操作，并跳到2.2)；所述的步骤(3)中的基于动态轮廓裁剪和全局轮廓裁剪的排序反向轮廓查询裁剪引擎，首先利用预处理保存的动态轮廓进行裁剪，再利用全局轮廓进行进一步裁剪；基于动态轮廓精炼的算法如下：i)初始化两个对象集合，一个用来保存最终结果，另一个用来保存的是无法判断的对象；ii)取出一个第一层全局轮廓点，计算出该第一层全局轮廓点的窗口，进行下一步精炼；全局轮廓点的窗口中心点是全局轮廓点，查询点q则是该窗口的一个顶点；如果所有第一层全局轮廓都已经精炼完，则算法结束；如果找到的反向轮廓的个数已经达到用户指定的要求，则算法也结束；否则，算法继续操作；iii)从预处理结果中找到该全局轮廓点对应的动态轮廓，如果查询点落在动态轮廓的动态控制区域中，那么该全局轮廓点不是最终结果，并跳到ii)；如果查询点落在动态非控制区域中，那么该全局轮廓点是最终结果，把该全局轮廓点加到最终结果的集合中并跳到ii)；查询点既不在动态控制区域中，也不在动态非控制区域中，那么步骤iii)无法判断该全局轮廓点是否为最终结果，加入到无法判断的对象集合中并跳到ii)；基于全局轮廓裁剪的算法如下：a)初始化一个对象集合，用来保存最终结果；b)取出无法用动态轮廓判断的一个全局轮廓点，计算出该全局轮廓点的窗口，进行下一步精炼；全局轮廓点的窗口中心点是全局轮廓点，查询点q则是该窗口的一个顶点；如果所有的对象都已经精炼完，则算法结束；如果找到的反向轮廓的个数已经达到用户指定的要求，则算法也结束；否则，继续操作；c)遍历第一层全局轮廓点，如果该全局轮廓点的窗口包含其它第一层全局轮廓点，那么该点不是最终结果并且跳转到b)；d)遍历第二层全局轮廓点，如果该全局轮廓点的窗口包含其它第二层全局轮廓点，那么该点不是最终结果；否则该点是最终结果，加入到最终结果对象集合；跳转到b)；所述的步骤(4)的排序引擎是将步骤(3)中得到的结果进行合并，并根据每个点的值进行排序得到最终的查询结果。 |
