Optimal suffix selection

Gianni Franceschini, Shan Muthukrishnan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

Given a string S[1 ⋯ n], the suffix selection problem is to find the kth lexicographically smallest amongst the n suffixes S[i ⋯ n], for i = 1, . . . , n. In particular, the fundamental question is if selection can be performed more efficiently than sorting all the suffixes. If one considered n numbers, they can be sorted using Θ(n log n) comparisons and the classical result from 70's is that selection can be done using O(n) comparisons. Thus selection is provably more efficient than sorting, for n numbers. Suffix sorting can be done using Θ(n log n) comparisons, but does suffix selection need suffix sorting? We settle this fundamental problem by presenting an optimal, deterministic algorithm for suffix selection using O(n) comparisons.

Original languageEnglish (US)
Title of host publicationSTOC'07
Subtitle of host publicationProceedings of the 39th Annual ACM Symposium on Theory of Computing
Pages328-337
Number of pages10
DOIs
StatePublished - Oct 30 2007
EventSTOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 11 2007Jun 13 2007

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing

Other

OtherSTOC'07: 39th Annual ACM Symposium on Theory of Computing
CountryUnited States
CitySan Diego, CA
Period6/11/076/13/07

Fingerprint

Suffix
Sorting
Deterministic Algorithm
Strings

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Order statistics
  • Selection
  • Strings
  • Suffixes

Cite this

Franceschini, G., & Muthukrishnan, S. (2007). Optimal suffix selection. In STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (pp. 328-337). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/1250790.1250840
Franceschini, Gianni ; Muthukrishnan, Shan. / Optimal suffix selection. STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. 2007. pp. 328-337 (Proceedings of the Annual ACM Symposium on Theory of Computing).
@inproceedings{e259b2aaf89341fead66f521c0e46cf2,
title = "Optimal suffix selection",
abstract = "Given a string S[1 ⋯ n], the suffix selection problem is to find the kth lexicographically smallest amongst the n suffixes S[i ⋯ n], for i = 1, . . . , n. In particular, the fundamental question is if selection can be performed more efficiently than sorting all the suffixes. If one considered n numbers, they can be sorted using Θ(n log n) comparisons and the classical result from 70's is that selection can be done using O(n) comparisons. Thus selection is provably more efficient than sorting, for n numbers. Suffix sorting can be done using Θ(n log n) comparisons, but does suffix selection need suffix sorting? We settle this fundamental problem by presenting an optimal, deterministic algorithm for suffix selection using O(n) comparisons.",
keywords = "Order statistics, Selection, Strings, Suffixes",
author = "Gianni Franceschini and Shan Muthukrishnan",
year = "2007",
month = "10",
day = "30",
doi = "https://doi.org/10.1145/1250790.1250840",
language = "English (US)",
isbn = "1595936319",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
pages = "328--337",
booktitle = "STOC'07",

}

Franceschini, G & Muthukrishnan, S 2007, Optimal suffix selection. in STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 328-337, STOC'07: 39th Annual ACM Symposium on Theory of Computing, San Diego, CA, United States, 6/11/07. https://doi.org/10.1145/1250790.1250840

Optimal suffix selection. / Franceschini, Gianni; Muthukrishnan, Shan.

STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. 2007. p. 328-337 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Optimal suffix selection

AU - Franceschini, Gianni

AU - Muthukrishnan, Shan

PY - 2007/10/30

Y1 - 2007/10/30

N2 - Given a string S[1 ⋯ n], the suffix selection problem is to find the kth lexicographically smallest amongst the n suffixes S[i ⋯ n], for i = 1, . . . , n. In particular, the fundamental question is if selection can be performed more efficiently than sorting all the suffixes. If one considered n numbers, they can be sorted using Θ(n log n) comparisons and the classical result from 70's is that selection can be done using O(n) comparisons. Thus selection is provably more efficient than sorting, for n numbers. Suffix sorting can be done using Θ(n log n) comparisons, but does suffix selection need suffix sorting? We settle this fundamental problem by presenting an optimal, deterministic algorithm for suffix selection using O(n) comparisons.

AB - Given a string S[1 ⋯ n], the suffix selection problem is to find the kth lexicographically smallest amongst the n suffixes S[i ⋯ n], for i = 1, . . . , n. In particular, the fundamental question is if selection can be performed more efficiently than sorting all the suffixes. If one considered n numbers, they can be sorted using Θ(n log n) comparisons and the classical result from 70's is that selection can be done using O(n) comparisons. Thus selection is provably more efficient than sorting, for n numbers. Suffix sorting can be done using Θ(n log n) comparisons, but does suffix selection need suffix sorting? We settle this fundamental problem by presenting an optimal, deterministic algorithm for suffix selection using O(n) comparisons.

KW - Order statistics

KW - Selection

KW - Strings

KW - Suffixes

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

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

U2 - https://doi.org/10.1145/1250790.1250840

DO - https://doi.org/10.1145/1250790.1250840

M3 - Conference contribution

SN - 1595936319

SN - 9781595936318

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 328

EP - 337

BT - STOC'07

ER -

Franceschini G, Muthukrishnan S. Optimal suffix selection. In STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. 2007. p. 328-337. (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/1250790.1250840