Dynamic Skyline Queries in Large Graphs | |
Zou, Lei ; Chen, Lei ; Ozsu, M. Tamer ; Zhao, Dongyan | |
2010 | |
英文摘要 | Given a set of query points, a dynamic skyline query reports all data points that are not dominated by other data points according to the distances between data points and query points. In this paper, we study dynamic skyline queries in a large graph (DSG-query for short). Although dynamic skylines have been studied in Euclidean space [14], road network [5], and metric space [3,6], there is no previous work on dynamic skylines over large graphs. We employ a filter-and-reline framework to speed up the query processing that can answer DSG-query efficiently. We propose a novel pruning rule based on graph properties to derive the candidates for DSG-query, that are guaranteed not to introduce false negatives. In the refinement step, with a carefully-designed index structure, we compute short path distances between vertices in O(H), where H is the number of maximal hops between any two vertices. Extensive experiments demonstrate that our methods outperform existing algorithms by orders of magnitude.; http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000278934800005&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=8e1609b174ce4e31116a60747a720701 ; Computer Science, Information Systems; Computer Science, Theory & Methods; EI; CPCI-S(ISTP); 5 |
语种 | 英语 |
DOI标识 | 10.1007/978-3-642-12098-5_5 |
内容类型 | 其他 |
源URL | [http://ir.pku.edu.cn/handle/20.500.11897/321234] |
专题 | 信息科学技术学院 |
推荐引用方式 GB/T 7714 | Zou, Lei,Chen, Lei,Ozsu, M. Tamer,et al. Dynamic Skyline Queries in Large Graphs. 2010-01-01. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论