Efficient monitoring of skyline queries over distributed data streams

doi:10.1007/s10115-009-0269-0

CORC > 北京大学 > 软件与微电子学院

	Efficient monitoring of skyline queries over distributed data streams
	Sun, Shengli ; Huang, Zhenghua ; Zhong, Hao ; Dai, Dongbo ; Liu, Hongbin ; Li, Jinjiu
刊名	knowledge and information systems
	2010
关键词	Distributed data streams Skyline Communication-optimal processing Progressive refinement
DOI	10.1007/s10115-009-0269-0
英文摘要	Data management and data mining over distributed data streams have received considerable attention within the database community recently. This paper is the first work to address skyline queries over distributed data streams, where streams derive from multiple horizontally split data sources. Skyline query returns a set of interesting objects which are not dominated by any other objects within the base dataset. Previous work is concentrated on skyline computations over static data or centralized data streams. We present an efficient and an effective algorithm called BOCS to handle this issue under a more challenging environment of distributed streams. BOCS consists of an efficient centralized algorithm GridSky and an associated communication protocol. Based on the strategy of progressive refinement in BOCS, the skyline is incrementally computed by two phases. In the first phase, local skylines on remote sites are maintained by GridSky. At each time, only skyline increments on remote sites are sent to the coordinator. In the second phase, a global skyline is obtained by integrating remote increments with the latest global skyline. A theoretical analysis shows that BOCS is communication-optimal among all algorithms which use a share-nothing strategy. Extensive experiments demonstrate that our proposals are efficient, scalable, and stable.; http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000284486700007&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=8e1609b174ce4e31116a60747a720701 ; Computer Science, Artificial Intelligence; Computer Science, Information Systems; SCI(E); 14; ARTICLE; 3; 575-606; 25
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/164163]
专题	软件与微电子学院
推荐引用方式 GB/T 7714	Sun, Shengli,Huang, Zhenghua,Zhong, Hao,et al. Efficient monitoring of skyline queries over distributed data streams[J]. knowledge and information systems,2010.
APA	Sun, Shengli,Huang, Zhenghua,Zhong, Hao,Dai, Dongbo,Liu, Hongbin,&Li, Jinjiu.(2010).Efficient monitoring of skyline queries over distributed data streams.knowledge and information systems.
MLA	Sun, Shengli,et al."Efficient monitoring of skyline queries over distributed data streams".knowledge and information systems (2010).