Near-optimal online multiselection in internal and external memory

详细信息    查看全文

• 作者：Jé ; ré ; my Barbay^a ; ¹ ; ^{jeremy@barbay.cl" class="auth_mail" title="E-mail the corresponding author} ; Ankur Gupta^b ; ² ; ^{agupta@butler.edu" class="auth_mail" title="E-mail the corresponding author} ; Srinivasa Rao Satti^c ; ³ ; ^{ssrao@cse.snu.ac.kr" class="auth_mail" title="E-mail the corresponding author} ; Jon Sorenson^b ; ^{jsorenso@butler.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Selection ; Sorting ; Multiselection ; Online algorithms ; Deferred data structures ; Dynamic ; External memory
• 刊名：Journal of Discrete Algorithms
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：36
• 期：Complete
• 页码：3-17
• 全文大小：453 K

文摘

We introduce an online version of the multiselection problem, in which q selection queries are requested on an unsorted array of n elements. We provide the first online algorithm that is 1-competitive with the offline algorithm proposed by Kaligosi et al. [14] in terms of comparison complexity. Our algorithm also supports online search queries efficiently. We then extend our algorithm to the dynamic setting, while retaining online functionality, by supporting arbitrary insertions and deletions   on the array. Assuming that the insertion of an element is immediately preceded by a search for that element, our dynamic online algorithm performs an optimal number of comparisons, up to lower order terms and an additive class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S157086671500115X&_mathId=si1.gif&_user=111111111&_pii=S157086671500115X&_rdoc=1&_issn=15708667&md5=7af9468b153e432dbb8e24cb5ffe9f1f" title="Click to view the MathML source">O(n)class="mathContainer hidden">class="mathCode">$O(n)$ term.

For the external memory model, we describe the first online multiselection algorithm that is class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S157086671500115X&_mathId=si2.gif&_user=111111111&_pii=S157086671500115X&_rdoc=1&_issn=15708667&md5=857b68aff37d538a9ef47f52d439a19e" title="Click to view the MathML source">O(1)class="mathContainer hidden">class="mathCode">$O(1)$-competitive. This result improves upon the work of Sibeyn [20] when class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S157086671500115X&_mathId=si3.gif&_user=111111111&_pii=S157086671500115X&_rdoc=1&_issn=15708667&md5=621885b3e4d379c9785c37122c23cf58" title="Click to view the MathML source">q=ω(m^1−ϵ)class="mathContainer hidden">class="mathCode">$q=\omega (m^{1-ϵ})$ for any fixed positive constant ϵ, where m is the number of blocks that can be stored in main memory. We also extend it to support searches, insertions, and deletions of elements efficiently.