DySky: dynamic skyline queries on uncertain graphs

Show simple item record

dc.contributor.author Banerjee, Suman
dc.contributor.author Pal, Bithika
dc.date.accessioned 2020-04-20T07:26:30Z
dc.date.available 2020-04-20T07:26:30Z
dc.date.issued 2020-04
dc.identifier.citation Banerjee, Suman and Pal, Bithika, "DySky: dynamic skyline queries on uncertain graphs", arXiv, Cornell University Library, DOI: arXiv:2004.02564, Apr. 2020. en_US
dc.identifier.uri http://arxiv.org/abs/2004.02564
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/5328
dc.description.abstract 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.
dc.description.statementofresponsibility by Suman Banerjee and Bithika Pal
dc.language.iso en_US en_US
dc.publisher Cornell University Library en_US
dc.title DySky: dynamic skyline queries on uncertain graphs en_US
dc.type Pre-Print en_US
dc.relation.journal arXiv

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account