开放科学（资源服务）标志码（OSID）：

0 概述

Skyline是解决数据库中多目标决策问题的重要手段，其可以在多维数据查询中为用户推荐较好的选择，方便用户做出决策。具体地，给定一个多维数据点的集合P及数据点p，p'∈P，如果点p在每个维度中的值都比p'好，并且在至少一个维度上更好，则点p支配p'。所有不被集合中的其他点支配的点被称为Skyline点。

近年来，随着全球定位系统和无线通信技术的发展，基于位置的服务（LBS）逐渐地被越来越多的用户所使用，LBS系统的主要目的是获取用户所在的位置，并向用户提供即时信息以便用户做出决策。例如，在导航系统中，旅客在城市中是想要找到满足自己偏好的酒店。其中用户到酒店的距离是空间属性，酒店的价格、评分是非空间属性。但现有的基于位置的查询只是针对单一维度进行的查询，解决诸如“查找距离查询位置q最近的旅社”类似问题，显然，这样单一的查询无法满足用户多样化的需求。

因此，在路网环境下基于位置的Skyline查询成为LBS研究的热点。近年来，一些学者针对路网数据中的Skyline问题进行了研究^[1-3]。文献[1]提出一种SSI算法，主要是针对路网上每个数据点p计算一个Skyline区域，只要查询位置q位于该区域，p就是一个Skyline点。然而，该方法的问题在于提前建立的索引代价过大，并且在数据点更新时就不再适用。文献[2]提出一种最近邻算法，通过广度优先遍历的方式找到Skyline点，最近邻算法的问题在于用户必须提前给定阈值边界，否则会一直进行下去，直到遍历完整个路网。文献[3]提出一种Skyline查询方法，该方法基于空间数据点构建网络Voronoi图，并对查询点建立查询凸包，通过网络Voronoi图的性质与查询区域的位置关系对数据集约减，从而节省路网距离计算的开销。然而，该方法在构建Voronoi图索引时代价过大，当数据点更新时就不再适用。

本文设计一种对路网上的数据点进行管理和更新的倒排索引结构，并提出路网上的Skyline算法DSR。倒排索引结构可用于管理路网数据点的维度，并且根据数据点在各个维度的值由优到劣进行排序，使用该索引可以对不需要计算路网距离的数据点进行过滤，同时加快数据点间支配关系的判定。DSR算法采取有效的扫描策略，只计算小部分数据点的路网距离即可高效地进行支配判定，在数据点更新的情况下给出DSR算法的动态维护。最终采用真实的道路网数据，对本文算法的高效性以及有效性进行验证。

1 相关研究

近年来，在路网环境下的Skyline查询处理引起研究人员的关注。CHOMICKI等^[4]介绍了Skyline的相关概念，并提出一些基础计算方法。DONG等^[5]提出组合式Skyline的求解算法，并给出相关的更新算法。文献[6]提出空间Skyline的概念，即将路网距离换为欧式距离作为求解时考虑的一个维度。

DENG等^[7]提出在路网上进行Skyline查询的方法，给出了相对应的算法，并围绕此问题，提出了相对应的协同扩张、下界约束等算法。然而，算法在大型路网上的距离计算成本过大。SAFAR等^[2]提出在路网上运用NN算法，以查询点为起点进行广度优先遍历，创建候选表，每扫描到一个数据点就与候选表的数据点进行比较，直到达到阈值边界。

另外，文献[1]提出的SSI算法，提前是为每个路网上的数据点计算一个查询区域Skyline scope，只要发起查询的位置在该区域上，该数据点就是一个Skyline点。然而，该算法提前建立索引代价过大，且每当发生数据点的更新时，整个索引需要重新计算。文献[8-10]的算法都是在该索引基础上进行扩展而来。

文献[1]在针对路网环境下基于位置的Skyline查询提出了Cdε-SQ（Continuous d-ε-Skyline Query）和CKnn-SQ（Continuous K nearest neighbor-Skyline Query）两种算法。Cdε-SQ的主要目的是为了节省路网距离计算的开销，而CKnn-SQ的主要目的是返回距离查询位置最近的k个Skyline数据点。然而，文献[1]算法在路网距离计算方面存在一定缺陷，故而查询效率较低。随后，HUANG等^[11]又提出了在动态路网上的Skyline查询。

文献[9-10, 12]介绍了多重属性道路网（MCN）中传统Skyline查询问题（MCN Skyline）。MCN中每条边具有多维属性，例如该边的长度、经过该边所需要的时间、经过该边的费用等。

LIN^[13]等与ZHOU^[14]等研究了路网环境下针对移动对象的Skyline查询。该查询假设路网上所有的查询对象的位置都在不断变化，查询结果随时都在更新。XU^[15]等研究了路网环境下针对用户发起查询位置的隐私保护问题。TAO^[16]等研究了流环境中的Skyline计算。HUANG^[17]等解决了在具有时变信息的动态道路网络中有效处理天际线内连续查询的问题。LIU^[18]等提出一种ZINC模型，结合ZB树的优势，并支持高效的Skyline计算。

2 问题描述

本节给出路网下基于位置的Skyline问题的形式化定义。表 1为本文所使用的符号。

2.1 问题定义

道路网络建模为无向加权图G=（V，E，W），其中：V是道路顶点集合；E是道路边集合；W是边长的集合。本文中讨论的距离都是路网上的最短路径距离。

在本文中，要求数据点的位置不能重合，给定数据点p∈P，每个数据点由多个非空间维度和一个空间维度组成，其中P的非空间属性集合为D_cont={d₁，d₂，…，d_m}，数据点可以表示为p= < p[d₁]，p[d₂]，…，p[d_m] > ，其中p[d_i]表示p在维度d_i上的值。P的空间属性表示为d_spatial，任意数据点p的空间属性值是p的地理位置坐标，用一个三元组 < v_i，v_j，distance > 表示，其中，v_i和v_j表示p的路网中所在边的两端顶点，distance表示p到道路顶点v_i的距离，dis（p，q）表示数据点p和q的路网上的最短距离。

图 1给出Skyline查询的示例，其中每个数据点对应一条旅社记录，具有评分、价格2个维度（注意，在该示例中用户希望评分越高越好和价格越低越好）。所以，根据图 1中的旅社信息列表来评估，数据点p₁支配p₄，因为p₁评分维度和p₄相同，在价格维度优于p₄。

例1    如图 1（b）所示，p₁的地理坐标为（v₉，v₁₀，3），表示p₁在v₉、v₁₀边上，p₁到v₉的距离为3。查询位置q的地理坐标为（v₂，v₈，4）。

与传统的Skyline查询不同，在道路网络中处理Skyline查询需要考虑数据点的空间属性。如图 1所示，在z市中一共有20家酒店（p₁~p₂₀），用户在q位置召开会议，他想找到合适的酒店来给参会人员安排住宿，希望找到在价格和评分方面有优势并且距离开会地点近的酒店。在这种情况下，当用户从位置q发起查询时，需要首先计算每个酒店到用户的距离，然后结合价格、评分，来找到q的Skyline结果集。可以看出，p₄的价格和评分优于p₃（见图 1），并且因为p₄比p₃更接近q（即p₄在空间维度上更好），则p₄支配p₃。最终，基于位置q返回满足用户条件的酒店集合是{p₁，p₄，p₅，p₆，p₇，p₁₂，p₁₃，p₁₆，p₁₇}。

定义1（空间支配）    给定路网G上的数据点集合P和查询位置q，p₁，p₂∈P，p₁关于q空间支配p₂（记作p₁$ \prec $_q p₂）需要满足以下2个条件：

1）∀d_i∈D_cont∪{d_spatial}，p₁[d_i]不差于p₂[d_i]；

2）∃ d_j∈D_cont∪{d_spatial}，p₁[d_j]好于p₂[d_j]。

定义2（路网Skyline集合）    给定路网G上的数据点集合P和查询位置q，道路网Skyline点集合就是不被其他数据点关于位置q空间支配的点的集合，记作SKY（q，P）＝{p₂|p₁，p₂∈P，p₁$ \prec $_qp₂}。

例2    利用图 1的数据集举例说明，若不考虑其空间属性，得到的Skyline集合为{p₁，p₆，p₇，p₉，p₁₆，p₁₇，p₂₀}，但在加入了空间属性后，得到的Skyline集合变为了{p₁，p₃，p₄，p₆，p₇，p₉，p₁₆，p₁₇}。

2.2 G-tree索引

本文采用G-tree索引^[19]来快速计算路网上任意数据点到查询位置间的最短路网距离。

G-tree是将道路网递归地划分为子网络，并在子网络的顶部构造树结构索引，其中每个G-tree节点都对应一个子网络。针对图 1对应的路网结构，进行的图划分结构如图 2（a）所示，建立好的G-tree索引如图 2（b）所示。其中，各非叶节点内都存储了该节点对应子图内边界点集合以及相应的距离矩阵，各叶节点内存储了该子图内边界点到该子图内其余路网节点的距离矩阵。

定义3（边界点）    给定图G的子图G_i，节点b₁∈V_i，节点b₂不属于V_i。若满足$ \exists $（b₁，b₂）∈E，则称节点b₁、b₂为边界点，B（G_i）为G_i内的边界点集合。

给定数据点p∈P，以及查询位置q，下面介绍借助G-tree索引，求出distance（p，q）。

例3    图 2展示了如何计算从q到p₂₀的距离，首先通过距离排序列表找到距离q和p₂₀最近的边界点v₂和v₂₁。随后通过哈希表（将边界点映射到叶子节点）找到叶子节点G₃（对于v₂）和G₆（对于v₂₁），它们的最小公共祖先节点是G₀，通过节点G₃、G₁、G₂、G₆来计算最短路网距离，图 2（c）中每个元素代表 < v_i，distance（q，v_i） > 。通过动态规划算法最终可以得到distance（q，p₂₀）=35，如图 2（c）所示，最短路径包括q、v₂、v₃、v₂₁、p₂₀。

3 查询处理算法DSR

本节介绍管理路网数据点的倒排索引，利用该索引提出DSR查询处理方法对数据提前进行处理，并过滤剪枝数据集，使得进行Skyline查询时不必扫描整个路网数据集，避免大量计算路网距离的开销。

3.1 管理路网数据点的倒排索引

对于路网上的数据点，采用特殊的倒排索引结构进行管理，在建立倒排索引时只针对将非空间维度的属性映射到倒排索引中，对于距离维度，在使用时才进行计算。具体地，对数据点在每一个维度上的值都按照从优到劣的顺序进行排序，距离维度初始时为空。

扫描策略：由于数据点可能在不同维度上表现各不相同，因此在扫描过程中，用count变量表示已经在该维度上扫描过的数据点个数。对每一个数据点p_i维护一个num变量，表示数据点被扫描过的次数。每次扫描时都选择count值最小的维度，按照数据点由好到坏的顺序进行扫描（若数据点值相同，则进行支配关系的判定）。

值得注意的是，针对距离维度，数据点的扫描顺序是在路网上从查询点q开始进行广度遍历，按照距离q由近及远的顺序进行处理，建立堆H用于存储距离维度已处理的信息。初始H={ < q，0 > }，每次取堆首元素处理，若处理的元素是查询点或路网节点，则找到与该节点相连的数据点或路网节点重新加入堆中并按与q的路网距离进行排序。若堆首元素是数据点，直接进行Skyline结果判定，把该数据点加入距离维度，同时距离维度的count值加1。

例4    如图 3所示，当第一次扫描到距离维度时，建立堆H，H={<q，0>}。初始处理q，找到与q直接相连的路网节点及数据点v₂、p₃和v₈，将其加入堆中，H={<v₂，2>，<p₃，4>，<v₈，5>}。然后处理v₂，此时出堆的元素为路网节点，找到与v₂相连的数据点以及路网节点加入H中，此时，H={<p₃，4>，<v₈，5>，< p₄，7>，<v₃，6>，<p₉，9>，<v₁₆，11>}。

随后处理p₃，此时出堆的元素为数据点，即距离维度第一次扫描到的数据点是p₃，进行Skyline结果判定，把该数据点加入距离维度，同时距离维度的count值加1。

扫描结束点：当数据点p_i在所有维度上都被扫描过一次时，称p_i为扫描结束点。

定理1    对于数据点p_i，若其被扫描过的次数与维度数相同，则对于未扫描过的数据点p_j（p_j的扫描次数为0）都一定被p_i支配。

证明    根据支配的定义，假设p_j不被p_i支配，则∃ d_j∈D_cont∪{d_spatial}，p_j [d_j]好于p_i [d_j]。即在维度d_j上p_j的扫描次序在p_i之前，违背了给定的条件，在所有维度上p_i的扫描次序优于p_j。得证。

定理2    给定维度d_i，对于扫描到的在维度d_i上的数据点p_i，若p_i不被d_i上已扫描过的Skyline点支配，则p_i是Skyline点。

证明    若∃p_j支配p_i，根据支配的定义，p_j支配p_i，需满足条件之一为∀d_j∈D_cont∪{d_spatial}，p_j[d_j]不差于p_i[d_j]；然而，定理2给定条件中p_j在维度d_i上的扫描次序在p_i之后，即p_i在维度d_i上优于p_j，与支配定义矛盾。得证。

如图 4所示，当扫描到价格维度的数据点p₁时，只将其与p₁₇进行空间支配关系比较即可，而不用与p₁₆、p₂₀比较，大幅提高了计算效率。因此，对每一个维度d_i建立结果集Rⁱ，存储该维度上已扫描过的所有Skyline点。

数据点处理策略：根据扫描策略可知，当前维度扫描到的数据点只有可能被当前维度结果集Rⁱ中的数据点支配，同时，若数据点p_i在当前维度确定为Skyline点时，只处理1次，在其他维度再次扫描到p_i时，只对p_i的计数器加1，每个数据点第一次被扫描时，计算其距离维度上的值。

3.2 DSR算法

本节描述算法DSR查询的全过程。首先对整个数据集建立倒排索引，随后针对维度d_i∈D_cont∪{d_spatial}建立结果集Rⁱ，然后根据扫描策略开始扫描维度（若扫描维度为d_spatial时，借助堆H进行广度遍历），在得到待处理数据集P_i后，利用G-tree索引，计算其中数据点的距离维度，随后与Rⁱ中的数据点进行支配关系的判定，将不被支配的数据点加入到结果集R中，最后输出结果集。

算法1    DSR算法描述

输入    路网G=（V，E，W），索引r

输出    Skyline结果集R

1.初始化每个维度上的结果集Rⁱ=∅；

2.对所有维度d_i∈（D_count∪d_spatial）建立倒排索引，d_spatial初始为空；

3.建立数据维度初始堆H={ < q，0 > }；

4.While（计算未结束）

5.根据扫描策略得到count值最小的维度d_i；

6.If（d_i= d_spatial）

7.处理H得到待处理数据集P_i；

8.Else

9.在非空间维度d_i上得到扫描数据集P_i；

10.计算出P_i中数据点的路网距离；

11.d_i.count= d_i.count +|P_i|；

12.Foreach（p_i∈P_i）

13.If（p_i不被P_i中其他数据点空间支配）

14.If（p_i.num=0）

15.If（p_i不被Rⁱ中的数据点空间支配）

16.将数据点p_i加入当前维度的结果集Rⁱ；

17.p_i.num ++；

18.Else

19.p_i.num ++；

20.If（p_i.num = | D_count |）

21.扫描结束，退出循环；

22.对所有Rⁱ取并集得到最终结果集R；

23.return R；

算法1第2行通过建立倒排索引来维护数据。第3行~第22行是算法主体，第5行根据count值确定扫描维度d_i，若d_i不是距离维度，则在得到待处理数据集后，算法第10行使用基于G-tree索引的动态规划算法来计算P_i中数据点的最短路径距离，其计算代价为O（lb f×|V|）²，V是路网上节点的个数，f为G-tree上节点的分支数量。算法第12行~第23行是算法的主体，每扫描到一次数据点，若该数据点不被P_i中其他数据点空间支配且num值为0，则将数据点加入到Rⁱ中且num值加1，当有一个数据点的num值与维度数相同时，此时，该数据点为扫描结束点，结束算法。DSR算法主要受|Rⁱ|的影响，|Rⁱ|为在维度d_i上的结果集，这部分算法的计算代价为O（|Rⁱ|×|d|）。算法第25行返回Skyline结果集R，算法整体时间复杂度为O（lb f×|V|×|Rⁱ|×|d|）²。

例5    在图 5（a）中，在初始时各维度计数值分别为0、0、0。第一次扫描顺序为价格维度，扫描到的数据点为p₁₇，此时维度计数器被更新为1、0、0，p₁₇扫描次数更新为1。接着处理评分维度，扫描到的数据点为p₁₆、p₂₀，维度计数器被更新为1、2、0，p₁₆、p₂₀扫描次数更新为1、1。接着处理距离维度，堆H处理的第一个数据点是p₄，维度计数器被更新为1、2、1，p₄扫描次数更新为1。这样一直扫描下去，直到p₉的扫描次数更新为3，此时p₉成为扫描结束点，算法结束，最终结果集R={p₁，p₃，p₄，p₆，p₇，p₉，p₁₆，p₁₇}。从图 5（b）可以看到，DSR算法仅计算了少部分数据点的路网距离。

4 DSR算法动态维护

DSR算法的动态维护主要是在路网环境下，当数据点发生更新时DSR算法的动态维护。动态维护主要包括新增数据点的处理以及失效数据点的处理两个操作。

4.1 失效数据点的处理

定理3    假设数据点p_i在维度d_i∈D_total上已经被扫描过，若数据点p_i只被数据点p_old空间支配，且p_old不是扫描结束点，则p_i在维度d_i上的值一定不好于p_old，且优于当前扫描位置处的数据点。

证明    若只满足p_old$ \prec $_qp_i，则∀d_i∈D_cont∪{d_spatial}，p_old[d_i]不差于p_i[d_i]，即在维度d_i上，p_old扫描位置一定不差于p_i，假设当前扫描位置处数据点为p_j，若p_j$ \prec $_q p_i不成立，则需满足∃ d_i∈D_cont∪{d_spatial}，p_i [d_i]好于p_j[d_i]，即在维度d_i上，p_i扫描位置好于p_j。得证。

若p_old不在现有的各个维度的结果集合并集中，则直接在倒排索引中删去。如果p_old属于结果集合，则首先需要找到所有只被p_old空间支配的数据点，具体做法是根据定理3，对所有已扫描过p_old的维度上表现不好于p_old但是优于当前扫描位置的数据点取交集，加入到候选集合R^t中。再将R^t中的数据点与R中的Skyline点进行空间支配关系的判定，R^t中不被R的任意Skyline点空间支配的数据点即是只被p_old空间支配的数据点。随后，判断p_old是否为扫描结束点。若p_old是扫描结束点，则p_old失效后算法未结束，需要找到新的扫描结束点p_end。

例6    如图 6所示，若被删除的数据点是p₉，则p₉是Skyline点，若此时的扫描位置为p₁，对在所有维度上表现不优于p₉但是优于p₁的数据点取交集，如图 6中的黑框部分所示，对黑框部分中的数据点取交集，将不在R中的数据点加入到候选集R^t中，得到R^t={p₅，p₈，p₁₃，p₁₅，p₂₀，p₁₂}，将R^t中的数据点与R进行空间支配关系判定后，得到最终只被p₉支配的数据点为p₅、p₈、p₁₃、p₂₀。随后，由于p₉是扫描结束点，因此算法继续运行直到找到新的扫描结束点，输出最终结果集。

4.2 新插入数据点的处理

本文从以下2个方面考虑p_new本身是否会成为空间Skyline点以及p_new是否会支配掉结果集中的点：1）如果p_new不受任何维度上的结果集中的数据点支配，则p_new是空间Skyline点，将其加入到该维度对应的结果集中，反之，p_new被支配掉；2）根据定理1，首先需要将结果集中的数据点与p_new进行支配关系的判定（不在结果集中的数据点一定被空间支配），因此需要将各个维度上结果集的并集中的数据点与p_new进行支配关系的判定（不在结果集中的数据点一定被空间支配），随后在结果集中过滤掉所有被p_new空间支配的数据点。

算法2描述了DSR算法更新维护过程的细节。当数据点发生更新时，算法需要找到所有仅只被p_old空间支配的数据点，具体做法是：首先，找到候选集合R^t中所有只被p_old空间支配的数据点，其次，每找到一个数据点就与R比较，判断其是否被R中的其他数据点空间支配。如果只能被p_old空间支配，则将其从候选集中取出添加到结果集中。算法第17行~第23行描述了在有新插入数据点p_new的情况下DSR的动态维护。

算法2    DSR算法动态维护

输入    路网G=（V，E，W），查询点q，索引，查询点q，更新的数据点p_new，失效的数据点p_old

输出    Skyline结果集R

1.While（计算未结束）

2.删除失效数据点p_old //处理失效数据点p_old

3.If（p_old属于结果集）

4.找到当前扫描位置对应的数据点p_now

5.将各个维度上表现不好于p_old但是优于p_now的非Skyline数据点取交集，加入到候选集合R^t中

6.Foreach p_i∈R^t

7.If（p_old空间支配p_i）

8.If（p_i不被Rⁱ中的数据点空间支配）

9.将p_i加入到R中

10.If（p_old是扫描结束点）

11.继续执行算法1的第12行~第21行

12.//处理新数据点p_new

13.If（p_new不被R中的数据点空间支配）

14.将p_new添加到R中

15.Foreach p_i∈R

16.If（p_new空间支配p_i）

17.删除p_i

18.return R；

算法2第3行~第11行描述了当倒排索引中的数据点失效时的情形，若p_old属于结果集合，根据算法第3行~第11行，算法找到只被p_old支配的数据点的计算代价为O（|R^t|）。若p_old不属于结果集合，算法只需要O（1）次操作，第13行~第17行描述了在有新插入数据点p_new的情况下DSR的动态维护。在处理新插入数据点p_new时，需要判定p_new是否被R中的数据点支配，在最坏情况下，要将p_new与R中所有数据点进行比较，计算代价为O（|Rⁱ|×|d|），随后，删除掉所有被p_new支配的数据点，DSR算法动态维护的计算代价为O（|Rⁱ|×|d|）。

5 实验结果与分析

本节主要验证所提DSR算法的性能。该实验环境配置为Inter Core i5 7300HQ 2.50 GHz CPU，8 GB内存，1T硬盘，Windows 10操作系统的PC。算法用C++语言编写。为验证本文所提算法的有效性，将SSI算法和BSS算法作为对比实验。设定    对于G-tree，设定f为4，$ \tau $为64。本文使用真实路网数据验证算法性能。真实数据采用的是两个真实的路网数据集，出处来自GitHub开源项目TransportationNetworks（网址为https://github.com/bstabler/TransportationNetworks），第1个路线图是奥尔登堡罗德（德国的一个城市）网络，由约6 000个节点和7 000条边组成，第2个路线图是加利福尼亚公路网，其中包含21 048个节点和21 693条边。这些数据集的统计信息如表 1所示。实验默认在道路网络上模拟生成1 000个对象。每个对象都有3个非空间属性，其值均匀分布在[0, 100]范围内。实验参数如表 2所示。

5.1 数据点数量变化对算法性能的影响

在第1组实验中，本文研究了非空间维度的变化对SSI、BSS算法以及本文DSR算法的性能影响。图 7所示为数据点集规模变化的实验结果。可以看出，SSI算法要优于本文DSR算法以及BSS算法，这是因为SSI算法提前计算了所有数据点两两之间的空间支配关系以及互相之间的距离，只用确定查询位置q的位置，即可直接返回结果集。而DSR算法的效率远远优于BSS算法，这是因为DSR算法在映射后采用倒排索引进行扫描，在找到扫描结束点后，可以直接结束算法，节省了计算时间与计算成本。

5.2 数据点更新速度对查询性能的影响

在第2组实验中，本文研究了数据点更新变化对BSS、SSI算法以及本文DSR算法的性能的影响。如图 8所示，数据点更新速度从1到150。可以看出，随着数据点更新速度的增加，3种算法的性能都有所下降，但DSR算法远远优于BSS算法以及SSI算法，主要是由于后者需要进行大量的路网距离计算，而基于倒排索引的DSR算法只需要计算部分数据点的路网距离，在找到扫描结束点之后，就能直接返回整个Skyline结果集。

5.3 数据点数量对索引建立时间的影响

在第3组实验中，本文研究了数据点数量的变化对SSI、BSS算法及本文DSR算法性能的影响。如图 9所示，数据点数量从范围为500到2 000。可以看到，随着数据点规模的增加，3种算法索引的建立时间性能都有所增加，但是DSR算法远远优于另外2种算法，主要原因是由于BBS算法需要进行大量的数据点路网距离计算，而SSI索引的建立需要计算好所有数据点之间的两两支配关系，以及遍历整个路网集，可以看到当数据集增加到一定规模后，计算代价过大。而DSR算法不需要直接计算出数据点之间的距离，所需的倒排索引以及G-Tree索引的建立时间明显优于前两种算法。

6 结束语

本文提出一种在路网环境下基于倒排索引的Skyline查询优化方法。将管理路网数据点的倒排索引引入Skyline查询，在查询前进行大量的过滤剪枝，从而提高实验的查询效率。在引入倒排索引的基础上，采用提前分组的形式对算法进行优化，提高对数据点过滤的有效性，加快算法的计算速度。实验结果验证了本文算法的高效性。下一步将运用DSR算法从数据集中快速返回给用户可控数量的Skyline结果，以达到提高算法查询效率、帮助用户快速决策的目的。