论文标题
Dysky：不确定图的动态天际线查询
DySky: Dynamic Skyline Queries on Uncertain Graphs
论文作者
论文摘要
给定图形和一组查询顶点（顶点的子集），动态的天际线查询问题返回了基于某些距离度量的其他数据顶点，这些数据顶点的子集（除查询顶点除外）不受其他数据顶点的控制。在本文中，我们研究了不确定图（Dysky）的动态天际线查询问题。此问题的输入是一个不确定的图表，其节点的子集作为查询顶点，而这里的目标是返回所有不受其他人主导的数据顶点。我们在不确定的图中采用了两个距离度量，即\ emph {多数距离}和\ emph {预期距离}。我们的方法将大致分为三个步骤：\ emph {Pruning}，\ emph {distance Computation}和\ emph {Skyline顶点set generation}。我们使用三个可公开的数据集实施了提出的方法，并观察到它可以找到Skyline Vertex设置，而无需花费很多时间，即使涉及预期的距离，也可以花费很多时间。特别是，修剪策略大大减少了计算时间。
Given a graph, and a set of query vertices (subset of the vertices), the dynamic skyline query problem returns a subset of data vertices (other than query vertices) which are not dominated by other data vertices based on certain distance measure. In this paper, we study the dynamic skyline query problem on uncertain graphs (DySky). The input to this problem is an uncertain graph, a subset of its nodes as query vertices, and the goal here is to return all the data vertices which are not dominated by others. We employ two distance measures in uncertain graphs, namely, \emph{Majority Distance}, and \emph{Expected Distance}. Our approach is broadly divided into three steps: \emph{Pruning}, \emph{Distance Computation}, and \emph{Skyline Vertex Set Generation}. We implement the proposed methodology with three publicly available datasets and observe that it can find out skyline vertex set without taking much time even for million sized graphs if expected distance is concerned. Particularly, the pruning strategy reduces the computational time significantly.
