Finding Skyline Nodes in Large Networks
Authors:
- Arijit KhanAKArijit Khan
- Vishwakarma SinghVSVishwakarma Singh
- Jian WuJWJian Wu
- 1 April 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 198-204
Abstract
Given a query node q in some graph dataset, we say that a node u is not dominated by another node v, if (1) the distance between u and q is less than the distance between v and q, or (2) the set of query node labels carried by u is a superset of the set of query node labels carried by v. A node is called a skyline node with respect to some query node, if it is not dominated by any other node in the graph, except the query node. Given a query node, the set of skyline nodes are more interesting, because any non-skyline node is farther from the query node and also it carries less number of query node labels, compared to some skyline node. Since there can be many such skyline nodes, they are usually ranked based on how many nodes each of them dominates. In this paper, we propose efficient techniques to determine the top-k skyline nodes from large network datasets.Keywords
This publication has 26 references indexed in Scilit:
- Dynamic Skyline Queries in Large Graphs2010
- Processing spatial skyline queries in both vector spaces and spatial network databasesACM Transactions on Database Systems, 2009
- Skyline Query Processing for Incomplete Data2008
- Multi-source Skyline Query Processing in Road Networks2007
- Selecting Stars: The k Most Representative Skyline Operator2007
- Maintaining sliding window skylines on data streamsIEEE Transactions on Knowledge and Data Engineering, 2006
- Skyline with presorting2004
- The Skyline operator2002
- Distance browsing in spatial databasesACM Transactions on Database Systems, 1999
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978