File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Online tracking of the dominance relationship of distributed multi-dimensional data

TitleOnline tracking of the dominance relationship of distributed multi-dimensional data
Authors
Lam, TWLiu, CMTing, HF
KeywordsCompetitive algorithms
Competitive ratio
D-dimensional grids
Distributed data sources
Lower bounds
Issue Date2010
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 8th Workshop on Approximation and Online Algorithms (WAOA 2010), Liverpool, UK., 9-10 September 2010. In Lecture Notes in Computer Science, 2010, v. 6534, p. 178-189 How to Cite?
DOI: http://dx.doi.org/10.1007/978-3-642-18318-8_16
AbstractWe consider the online problem for a root (or a coordinator) to maintain a set of filters for the purpose of keeping track of the dominance relationship of some distributed multi-dimensional data. Such data keep changing from time to time. The objective is to minimize the communication between the root and the distributed data sources. Assume that data are chosen from the d-dimensional grid {1, 2,⋯, U}d, we give an O(d logU)-competitive algorithm for this online problem. The competitive ratio is asymptotically tight as it is relatively easy to show an Ω(d logU) lower bound. © 2011 Springer-Verlag.
DescriptionLNCS v. 6534 has title: Approximation and online algorithms : 8th international workshop, WAOA 2010, Liverpool, UK, September 9-10, 2010 : revised papers
Persistent Identifierhttp://hdl.handle.net/10722/151990
ISSN
0302-9743
2023 SCImago Journal Rankings: 0.606
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_US
dc.contributor.authorLiu, CMen_US
dc.contributor.authorTing, HFen_US
dc.date.accessioned2012-06-26T06:32:11Z-
dc.date.available2012-06-26T06:32:11Z-
dc.date.issued2010en_US
dc.identifier.citationThe 8th Workshop on Approximation and Online Algorithms (WAOA 2010), Liverpool, UK., 9-10 September 2010. In Lecture Notes in Computer Science, 2010, v. 6534, p. 178-189en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/10722/151990-
dc.descriptionLNCS v. 6534 has title: Approximation and online algorithms : 8th international workshop, WAOA 2010, Liverpool, UK, September 9-10, 2010 : revised papers-
dc.description.abstractWe consider the online problem for a root (or a coordinator) to maintain a set of filters for the purpose of keeping track of the dominance relationship of some distributed multi-dimensional data. Such data keep changing from time to time. The objective is to minimize the communication between the root and the distributed data sources. Assume that data are chosen from the d-dimensional grid {1, 2,⋯, U}d, we give an O(d logU)-competitive algorithm for this online problem. The competitive ratio is asymptotically tight as it is relatively easy to show an Ω(d logU) lower bound. © 2011 Springer-Verlag.en_US
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_US
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectCompetitive algorithms-
dc.subjectCompetitive ratio-
dc.subjectD-dimensional grids-
dc.subjectDistributed data sources-
dc.subjectLower bounds-
dc.titleOnline tracking of the dominance relationship of distributed multi-dimensional dataen_US
dc.typeConference_Paperen_US
dc.identifier.emailLam, TW: twlam@cs.hku.hken_US
dc.identifier.emailLiu, CM: cmliu@cs.hku.hken_US
dc.identifier.emailTing, HF: hfting@cs.hku.hk-
dc.identifier.authorityLam, TW=rp00135en_US
dc.identifier.authorityTing, HF=rp00177en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/978-3-642-18318-8_16en_US
dc.identifier.scopuseid_2-s2.0-79551570315en_US
dc.identifier.hkuros177023-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-79551570315&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume6534en_US
dc.identifier.spage178en_US
dc.identifier.epage189en_US
dc.publisher.placeGermanyen_US
dc.description.otherThe 8th Workshop on Approximation and Online Algorithms (WAOA 2010), Liverpool, UK., 9-10 September 2010. In Lecture Notes in Computer Science, 2010, v. 6534, p. 178-189-
dc.identifier.scopusauthoridTing, HF=7005654198en_US
dc.identifier.scopusauthoridLiu, CM=36918796000en_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats