File Download
  • No File Attached
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Minimizing the communication cost for continuous skyline maintenance
  • Basic View
  • Metadata View
  • XML View
TitleMinimizing the communication cost for continuous skyline maintenance
 
AuthorsZhang, Z3
Cheng, R1
Papadias, D2
Tung, AKH3
 
KeywordsCommunication
Continuous query
Skyline query
 
Issue Date2009
 
CitationSigmod-Pods'09 - Proceedings Of The International Conference On Management Of Data And 28Th Symposium On Principles Of Database Systems, 2009, p. 495-507 [How to Cite?]
DOI: http://dx.doi.org/10.1145/1559845.1559898
 
AbstractExisting work in the skyline literature focuses on optimizing the processing cost. This paper aims at minimization of the communication overhead in client-server architectures, where a server continuously maintains the skyline of dynamic objects. Our first contribution is a Filter method that avoids transmission of updates from objects that cannot influence the skyline. Specifically, each object is assigned a filter so that it needs to issue an update only if it violates its filter. Filter achieves significant savings over the naive approach of transmitting all updates. Going one step further, we introduce the concept of frequent skyline query over a sliding window (FSQW). The motivation is that snapshot skylines are not very useful in streaming environments because they keep changing over time. Instead, FSQW reports the objects that appear in the skylines of at least θ.s of the s most recent timestamps (0 < θ ≤ 1). Filter can be easily adapted to FSQW processing, however, with potentially high overhead for large and frequently updated datasets. To further reduce the communication cost, we propose a Sampling method, which returns approximate FSQW results without computing each snapshot skyline. Finally, we integrate Filter and Sampling in a Hybrid approach that combines their individual advantages. © 2009 ACM.
 
DescriptionProceedings of the ACM Conference on the Management of Data (SIGMOD 2009)
 
DOIhttp://dx.doi.org/10.1145/1559845.1559898
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorZhang, Z
 
dc.contributor.authorCheng, R
 
dc.contributor.authorPapadias, D
 
dc.contributor.authorTung, AKH
 
dc.date.accessioned2010-07-13T03:31:59Z
 
dc.date.available2010-07-13T03:31:59Z
 
dc.date.issued2009
 
dc.description.abstractExisting work in the skyline literature focuses on optimizing the processing cost. This paper aims at minimization of the communication overhead in client-server architectures, where a server continuously maintains the skyline of dynamic objects. Our first contribution is a Filter method that avoids transmission of updates from objects that cannot influence the skyline. Specifically, each object is assigned a filter so that it needs to issue an update only if it violates its filter. Filter achieves significant savings over the naive approach of transmitting all updates. Going one step further, we introduce the concept of frequent skyline query over a sliding window (FSQW). The motivation is that snapshot skylines are not very useful in streaming environments because they keep changing over time. Instead, FSQW reports the objects that appear in the skylines of at least θ.s of the s most recent timestamps (0 < θ ≤ 1). Filter can be easily adapted to FSQW processing, however, with potentially high overhead for large and frequently updated datasets. To further reduce the communication cost, we propose a Sampling method, which returns approximate FSQW results without computing each snapshot skyline. Finally, we integrate Filter and Sampling in a Hybrid approach that combines their individual advantages. © 2009 ACM.
 
dc.description.naturelink_to_subscribed_fulltext
 
dc.descriptionProceedings of the ACM Conference on the Management of Data (SIGMOD 2009)
 
dc.identifier.citationSigmod-Pods'09 - Proceedings Of The International Conference On Management Of Data And 28Th Symposium On Principles Of Database Systems, 2009, p. 495-507 [How to Cite?]
DOI: http://dx.doi.org/10.1145/1559845.1559898
 
dc.identifier.doihttp://dx.doi.org/10.1145/1559845.1559898
 
dc.identifier.epage507
 
dc.identifier.hkuros162400
 
dc.identifier.scopuseid_2-s2.0-70849121280
 
dc.identifier.spage495
 
dc.identifier.urihttp://hdl.handle.net/10722/61150
 
dc.languageeng
 
dc.relation.ispartofSIGMOD-PODS'09 - Proceedings of the International Conference on Management of Data and 28th Symposium on Principles of Database Systems
 
dc.relation.referencesReferences in Scopus
 
dc.subjectCommunication
 
dc.subjectContinuous query
 
dc.subjectSkyline query
 
dc.titleMinimizing the communication cost for continuous skyline maintenance
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Zhang, Z</contributor.author>
<contributor.author>Cheng, R</contributor.author>
<contributor.author>Papadias, D</contributor.author>
<contributor.author>Tung, AKH</contributor.author>
<date.accessioned>2010-07-13T03:31:59Z</date.accessioned>
<date.available>2010-07-13T03:31:59Z</date.available>
<date.issued>2009</date.issued>
<identifier.citation>Sigmod-Pods&apos;09 - Proceedings Of The International Conference On Management Of Data And 28Th Symposium On Principles Of Database Systems, 2009, p. 495-507</identifier.citation>
<identifier.uri>http://hdl.handle.net/10722/61150</identifier.uri>
<description>Proceedings of the ACM Conference on the Management of Data (SIGMOD 2009)</description>
<description.abstract>Existing work in the skyline literature focuses on optimizing the processing cost. This paper aims at minimization of the communication overhead in client-server architectures, where a server continuously maintains the skyline of dynamic objects. Our first contribution is a Filter method that avoids transmission of updates from objects that cannot influence the skyline. Specifically, each object is assigned a filter so that it needs to issue an update only if it violates its filter. Filter achieves significant savings over the naive approach of transmitting all updates. Going one step further, we introduce the concept of frequent skyline query over a sliding window (FSQW). The motivation is that snapshot skylines are not very useful in streaming environments because they keep changing over time. Instead, FSQW reports the objects that appear in the skylines of at least &#952;.s of the s most recent timestamps (0 &lt; &#952; &#8804; 1). Filter can be easily adapted to FSQW processing, however, with potentially high overhead for large and frequently updated datasets. To further reduce the communication cost, we propose a Sampling method, which returns approximate FSQW results without computing each snapshot skyline. Finally, we integrate Filter and Sampling in a Hybrid approach that combines their individual advantages. &#169; 2009 ACM.</description.abstract>
<language>eng</language>
<relation.ispartof>SIGMOD-PODS&apos;09 - Proceedings of the International Conference on Management of Data and 28th Symposium on Principles of Database Systems</relation.ispartof>
<subject>Communication</subject>
<subject>Continuous query</subject>
<subject>Skyline query</subject>
<title>Minimizing the communication cost for continuous skyline maintenance</title>
<type>Conference_Paper</type>
<description.nature>link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1145/1559845.1559898</identifier.doi>
<identifier.scopus>eid_2-s2.0-70849121280</identifier.scopus>
<identifier.hkuros>162400</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-70849121280&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.spage>495</identifier.spage>
<identifier.epage>507</identifier.epage>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. Hong Kong University of Science and Technology
  3. National University of Singapore