File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: An Ω(1/εlog1/ε) space lower bound for finding e-approximate quantiles in a data stream

TitleAn Ω(1/εlog1/ε) space lower bound for finding e-approximate quantiles in a data stream
Authors
Issue Date2010
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 4th International Frontiers of Algorithmics Workshop (FAW 2010), Wuhan, China, 11-13 August 2010. In Lecture Notes in Computer Science, 2010, v. 6213, p. 89-100 How to Cite?
AbstractThis paper studies the space complexity of the ε-approximate quantiles problem, which asks for some data structure that enables us to determine, after reading a whole data stream, a φ-quantile (for any 0 ≤ φ ≤ 1) of the stream within some error bound ε. The best known algorithm for the problem uses O(1/εlogεN) words where N is the total number of items in the stream, or uses O(1/εlog |U|) words where U is the set of possible items. It is known that the space lower bound of the problem is Ω(1/ε) words; however, improvement of this bound is elusive. In this paper, we prove that any comparison-based algorithm for finding ε-approximate quantiles needs Ω(1/εlog1/ε) words.
DescriptionThis LNCS vol. is the Proceedings of FAW 2010
Persistent Identifierhttp://hdl.handle.net/10722/125715
ISBN
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorHung, RYSen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-10-31T11:47:42Z-
dc.date.available2010-10-31T11:47:42Z-
dc.date.issued2010en_HK
dc.identifier.citationThe 4th International Frontiers of Algorithmics Workshop (FAW 2010), Wuhan, China, 11-13 August 2010. In Lecture Notes in Computer Science, 2010, v. 6213, p. 89-100en_HK
dc.identifier.isbn978-3-642-14552-0-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/125715-
dc.descriptionThis LNCS vol. is the Proceedings of FAW 2010-
dc.description.abstractThis paper studies the space complexity of the ε-approximate quantiles problem, which asks for some data structure that enables us to determine, after reading a whole data stream, a φ-quantile (for any 0 ≤ φ ≤ 1) of the stream within some error bound ε. The best known algorithm for the problem uses O(1/εlogεN) words where N is the total number of items in the stream, or uses O(1/εlog |U|) words where U is the set of possible items. It is known that the space lower bound of the problem is Ω(1/ε) words; however, improvement of this bound is elusive. In this paper, we prove that any comparison-based algorithm for finding ε-approximate quantiles needs Ω(1/εlog1/ε) words.-
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.titleAn Ω(1/εlog1/ε) space lower bound for finding e-approximate quantiles in a data streamen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailHung, RYS: yshung@cs.hku.hken_HK
dc.identifier.emailTing, HF: hfting@cs.hku.hken_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-14553-7_11-
dc.identifier.scopuseid_2-s2.0-77955884033-
dc.identifier.hkuros178825en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77955884033&selection=ref&src=s&origin=recordpage-
dc.identifier.volume6213-
dc.identifier.spage89en_HK
dc.identifier.epage100en_HK
dc.publisher.placeGermany-
dc.description.otherThe 4th International Frontiers of Algorithmics Workshop (FAW 2010), Wuhan, China, 11-13 August 2010. In Lecture Notes in Computer Science, 2010, v. 6213, p. 89-100-
dc.identifier.scopusauthoridHung, RYS=14028462000-
dc.identifier.scopusauthoridTing, HF=7005654198-
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats