Range medians

Sariel Har-Peled; S. Muthukrishnan

doi:10.1007/978-3-540-87744-8_42

Range medians

Sariel Har-Peled, S. Muthukrishnan

Siebel School of Computing and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We study a generalization of the classical median finding problem to batched query case: given an array of unsorted n items and k (not necessarily disjoint) intervals in the array, the goal is to determine the median in each of the intervals in the array. We give an algorithm that uses O(nlogk + klogk logn) comparisons and show a lower bound of Ω(nlogk) comparisons for this problem. This is optimal for k = O(n/logn).

Original language	English (US)
Title of host publication	Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings
Publisher	Springer
Pages	503-514
Number of pages	12
ISBN (Print)	3540877436, 9783540877431
DOIs	https://doi.org/10.1007/978-3-540-87744-8_42
State	Published - 2008
Event	16th Annual European Symposium on Algorithms, ESA 2008 - Karlsruhe, Germany Duration: Sep 15 2008 → Sep 17 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5193 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	16th Annual European Symposium on Algorithms, ESA 2008
Country/Territory	Germany
City	Karlsruhe
Period	9/15/08 → 9/17/08

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-3-540-87744-8_42

Library availability

Discover UIUC Full Text

Cite this

Range medians. / Har-Peled, Sariel; Muthukrishnan, S.
Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings. Springer, 2008. p. 503-514 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5193 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Har-Peled, S & Muthukrishnan, S 2008, Range medians. in Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5193 LNCS, Springer, pp. 503-514, 16th Annual European Symposium on Algorithms, ESA 2008, Karlsruhe, Germany, 9/15/08. https://doi.org/10.1007/978-3-540-87744-8_42

@inproceedings{080a0ad369ee49b0968df414222197ee,

title = "Range medians",

abstract = "We study a generalization of the classical median finding problem to batched query case: given an array of unsorted n items and k (not necessarily disjoint) intervals in the array, the goal is to determine the median in each of the intervals in the array. We give an algorithm that uses O(nlogk + klogk logn) comparisons and show a lower bound of Ω(nlogk) comparisons for this problem. This is optimal for k = O(n/logn).",

author = "Sariel Har-Peled and S. Muthukrishnan",

year = "2008",

doi = "10.1007/978-3-540-87744-8_42",

language = "English (US)",

isbn = "3540877436",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "503--514",

booktitle = "Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings",

address = "Germany",

note = "16th Annual European Symposium on Algorithms, ESA 2008 ; Conference date: 15-09-2008 Through 17-09-2008",

}

TY - GEN

T1 - Range medians

AU - Har-Peled, Sariel

AU - Muthukrishnan, S.

PY - 2008

Y1 - 2008

N2 - We study a generalization of the classical median finding problem to batched query case: given an array of unsorted n items and k (not necessarily disjoint) intervals in the array, the goal is to determine the median in each of the intervals in the array. We give an algorithm that uses O(nlogk + klogk logn) comparisons and show a lower bound of Ω(nlogk) comparisons for this problem. This is optimal for k = O(n/logn).

AB - We study a generalization of the classical median finding problem to batched query case: given an array of unsorted n items and k (not necessarily disjoint) intervals in the array, the goal is to determine the median in each of the intervals in the array. We give an algorithm that uses O(nlogk + klogk logn) comparisons and show a lower bound of Ω(nlogk) comparisons for this problem. This is optimal for k = O(n/logn).

UR - http://www.scopus.com/inward/record.url?scp=57749083049&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57749083049&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-87744-8_42

DO - 10.1007/978-3-540-87744-8_42

M3 - Conference contribution

AN - SCOPUS:57749083049

SN - 3540877436

SN - 9783540877431

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 503

EP - 514

BT - Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings

PB - Springer

T2 - 16th Annual European Symposium on Algorithms, ESA 2008

Y2 - 15 September 2008 through 17 September 2008

ER -

Range medians

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this