File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-642-14553-7_11
- Scopus: eid_2-s2.0-77955884033
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: An Ω(1/εlog1/ε) space lower bound for finding e-approximate quantiles in a data stream
| Title | An Ω(1/εlog1/ε) space lower bound for finding e-approximate quantiles in a data stream |
|---|---|
| Authors | |
| Issue Date | 2010 |
| Publisher | Springer 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? |
| Abstract | This 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. |
| Description | This LNCS vol. is the Proceedings of FAW 2010 |
| Persistent Identifier | http://hdl.handle.net/10722/125715 |
| ISBN | |
| ISSN | 2023 SCImago Journal Rankings: 0.606 |
| References |
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Hung, RYS | en_HK |
| dc.contributor.author | Ting, HF | en_HK |
| dc.date.accessioned | 2010-10-31T11:47:42Z | - |
| dc.date.available | 2010-10-31T11:47:42Z | - |
| dc.date.issued | 2010 | en_HK |
| dc.identifier.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 | en_HK |
| dc.identifier.isbn | 978-3-642-14552-0 | - |
| dc.identifier.issn | 0302-9743 | - |
| dc.identifier.uri | http://hdl.handle.net/10722/125715 | - |
| dc.description | This LNCS vol. is the Proceedings of FAW 2010 | - |
| dc.description.abstract | This 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.language | eng | en_HK |
| dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | - |
| dc.relation.ispartof | Lecture Notes in Computer Science | en_HK |
| dc.rights | The original publication is available at www.springerlink.com | - |
| dc.title | An Ω(1/εlog1/ε) space lower bound for finding e-approximate quantiles in a data stream | en_HK |
| dc.type | Conference_Paper | en_HK |
| dc.identifier.email | Hung, RYS: yshung@cs.hku.hk | en_HK |
| dc.identifier.email | Ting, HF: hfting@cs.hku.hk | en_HK |
| dc.identifier.authority | Ting, HF=rp00177 | en_HK |
| dc.description.nature | link_to_subscribed_fulltext | - |
| dc.identifier.doi | 10.1007/978-3-642-14553-7_11 | - |
| dc.identifier.scopus | eid_2-s2.0-77955884033 | - |
| dc.identifier.hkuros | 178825 | en_HK |
| dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-77955884033&selection=ref&src=s&origin=recordpage | - |
| dc.identifier.volume | 6213 | - |
| dc.identifier.spage | 89 | en_HK |
| dc.identifier.epage | 100 | en_HK |
| dc.publisher.place | Germany | - |
| dc.description.other | 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 | - |
| dc.identifier.scopusauthorid | Hung, RYS=14028462000 | - |
| dc.identifier.scopusauthorid | Ting, HF=7005654198 | - |
| dc.identifier.issnl | 0302-9743 | - |