Property suffix array with applications

Panagiotis Charalampopoulos; Costas S. Iliopoulos; Chang Liu; Solon P. Pissis

doi:10.1007/978-3-319-77404-6_22

Property suffix array with applications

Panagiotis Charalampopoulos, Costas S. Iliopoulos, Chang Liu, Solon P. Pissis^*

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

The suffix array is one of the most prevalent data structures for string indexing; it stores the lexicographically sorted list of suffixes of a given string. Its practical advantage compared to the suffix tree is space efficiency. In Property Indexing, we are given a string x of length n and a property Π, i.e. a set of Π -valid intervals over x. A suffix-tree-like index over these valid prefixes of suffixes of x can be built in time and space O(n). We show here how to directly build a suffix-array-like index, the Property Suffix Array (PSA), in time and space O(n). We mainly draw our motivation from weighted (probabilistic) sequences: sequences of probability distributions over a given alphabet. Given a probability threshold 1z, we say that a string p of length m matches a weighted sequence X of length n at starting position i if the product of probabilities of the letters of p at positions i, …, i+ m- 1 in X is at least 1z. Our algorithm for building the PSA can be directly applied to build an O(nz) -sized suffix-array-like index over X in time and space O(nz).

Original language	English
Title of host publication	LATIN 2018
Subtitle of host publication	Theoretical Informatics - 13th Latin American Symposium, Proceedings
Editors	Miguel A. Mosteiro, Michael A. Bender, Martin Farach-Colton
Publisher	Springer Verlag
Pages	290-302
Number of pages	13
ISBN (Print)	9783319774039
DOIs	https://doi.org/10.1007/978-3-319-77404-6_22
Publication status	Published - 1 Jan 2018
Externally published	Yes
Event	13th International Symposium on Latin American Theoretical Informatics, LATIN 2018 - Buenos Aires, Argentina Duration: 16 Apr 2018 → 19 Apr 2018

Publication series

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

Conference

Conference	13th International Symposium on Latin American Theoretical Informatics, LATIN 2018
Country/Territory	Argentina
City	Buenos Aires
Period	16/04/18 → 19/04/18

Funding

P. Charalampopoulos—Supported by the Graduate Teaching Scholarship scheme of the Department of Informatics at King’s College London and by the A.G. Leventis Foundation.

Access to Document

10.1007/978-3-319-77404-6_22

Persistent URL (handle)

Persistent link

Cite this

Charalampopoulos, P., Iliopoulos, C. S., Liu, C., & Pissis, S. P. (2018). Property suffix array with applications. In M. A. Mosteiro, M. A. Bender, & M. Farach-Colton (Eds.), LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings (pp. 290-302). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10807 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-77404-6_22

Charalampopoulos, Panagiotis ; Iliopoulos, Costas S. ; Liu, Chang et al. / Property suffix array with applications. LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings. editor / Miguel A. Mosteiro ; Michael A. Bender ; Martin Farach-Colton. Springer Verlag, 2018. pp. 290-302 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{48c377b2660c4929bb47e14749c1fb85,

title = "Property suffix array with applications",

abstract = "The suffix array is one of the most prevalent data structures for string indexing; it stores the lexicographically sorted list of suffixes of a given string. Its practical advantage compared to the suffix tree is space efficiency. In Property Indexing, we are given a string x of length n and a property Π, i.e. a set of Π -valid intervals over x. A suffix-tree-like index over these valid prefixes of suffixes of x can be built in time and space O(n). We show here how to directly build a suffix-array-like index, the Property Suffix Array (PSA), in time and space O(n). We mainly draw our motivation from weighted (probabilistic) sequences: sequences of probability distributions over a given alphabet. Given a probability threshold 1z, we say that a string p of length m matches a weighted sequence X of length n at starting position i if the product of probabilities of the letters of p at positions i, …, i+ m- 1 in X is at least 1z. Our algorithm for building the PSA can be directly applied to build an O(nz) -sized suffix-array-like index over X in time and space O(nz).",

author = "Panagiotis Charalampopoulos and Iliopoulos, {Costas S.} and Chang Liu and Pissis, {Solon P.}",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-77404-6_22",

language = "English",

isbn = "9783319774039",

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

publisher = "Springer Verlag",

pages = "290--302",

editor = "Mosteiro, {Miguel A.} and Bender, {Michael A.} and Martin Farach-Colton",

booktitle = "LATIN 2018",

address = "Germany",

note = "13th International Symposium on Latin American Theoretical Informatics, LATIN 2018 ; Conference date: 16-04-2018 Through 19-04-2018",

}

Charalampopoulos, P, Iliopoulos, CS, Liu, C & Pissis, SP 2018, Property suffix array with applications. in MA Mosteiro, MA Bender & M Farach-Colton (eds), LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10807 LNCS, Springer Verlag, pp. 290-302, 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018, Buenos Aires, Argentina, 16/04/18. https://doi.org/10.1007/978-3-319-77404-6_22

Property suffix array with applications. / Charalampopoulos, Panagiotis; Iliopoulos, Costas S.; Liu, Chang et al.
LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings. ed. / Miguel A. Mosteiro; Michael A. Bender; Martin Farach-Colton. Springer Verlag, 2018. p. 290-302 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10807 LNCS).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Property suffix array with applications

AU - Charalampopoulos, Panagiotis

AU - Iliopoulos, Costas S.

AU - Liu, Chang

AU - Pissis, Solon P.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - The suffix array is one of the most prevalent data structures for string indexing; it stores the lexicographically sorted list of suffixes of a given string. Its practical advantage compared to the suffix tree is space efficiency. In Property Indexing, we are given a string x of length n and a property Π, i.e. a set of Π -valid intervals over x. A suffix-tree-like index over these valid prefixes of suffixes of x can be built in time and space O(n). We show here how to directly build a suffix-array-like index, the Property Suffix Array (PSA), in time and space O(n). We mainly draw our motivation from weighted (probabilistic) sequences: sequences of probability distributions over a given alphabet. Given a probability threshold 1z, we say that a string p of length m matches a weighted sequence X of length n at starting position i if the product of probabilities of the letters of p at positions i, …, i+ m- 1 in X is at least 1z. Our algorithm for building the PSA can be directly applied to build an O(nz) -sized suffix-array-like index over X in time and space O(nz).

AB - The suffix array is one of the most prevalent data structures for string indexing; it stores the lexicographically sorted list of suffixes of a given string. Its practical advantage compared to the suffix tree is space efficiency. In Property Indexing, we are given a string x of length n and a property Π, i.e. a set of Π -valid intervals over x. A suffix-tree-like index over these valid prefixes of suffixes of x can be built in time and space O(n). We show here how to directly build a suffix-array-like index, the Property Suffix Array (PSA), in time and space O(n). We mainly draw our motivation from weighted (probabilistic) sequences: sequences of probability distributions over a given alphabet. Given a probability threshold 1z, we say that a string p of length m matches a weighted sequence X of length n at starting position i if the product of probabilities of the letters of p at positions i, …, i+ m- 1 in X is at least 1z. Our algorithm for building the PSA can be directly applied to build an O(nz) -sized suffix-array-like index over X in time and space O(nz).

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

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

U2 - 10.1007/978-3-319-77404-6_22

DO - 10.1007/978-3-319-77404-6_22

M3 - Conference contribution

AN - SCOPUS:85045398695

SN - 9783319774039

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

SP - 290

EP - 302

BT - LATIN 2018

A2 - Mosteiro, Miguel A.

A2 - Bender, Michael A.

A2 - Farach-Colton, Martin

PB - Springer Verlag

T2 - 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018

Y2 - 16 April 2018 through 19 April 2018

ER -

Charalampopoulos P, Iliopoulos CS, Liu C, Pissis SP. Property suffix array with applications. In Mosteiro MA, Bender MA, Farach-Colton M, editors, LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings. Springer Verlag. 2018. p. 290-302. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-77404-6_22

Property suffix array with applications

Abstract

Publication series

Conference

Funding

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this