The position heap of a trie

Yuto Nakashima; Tomohiro I; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda

doi:10.1007/978-3-642-34109-0_38

The position heap of a trie

Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Mathematical Informatics

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

8 Citations (Scopus)

Abstract

The position heap is a text indexing structure for a single text string, recently proposed by Ehrenfeucht et al. [Position heaps: A simple and dynamic text indexing data structure, Journal of Discrete Algorithms, 9(1):100-121, 2011]. In this paper we introduce the position heap for a set of strings, and propose an efficient algorithm to construct the position heap for a set of strings which is given as a trie. For a fixed alphabet our algorithm runs in time linear in the size of the trie. We also show that the position heap can be efficiently updated after addition/removal of a leaf of the input trie.

Original language	English
Title of host publication	String Processing and Information Retrieval - 19th International Symposium, SPIRE 2012, Proceedings
Publisher	Springer Verlag
Pages	360-371
Number of pages	12
ISBN (Print)	9783642341083
DOIs	https://doi.org/10.1007/978-3-642-34109-0_38
Publication status	Published - 2012
Event	19th International Symposium on String Processing and Information Retrieval, SPIRE 2012 - Cartagena de Indias, Colombia Duration: Oct 21 2012 → Oct 25 2012

Publication series

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

Other

Other	19th International Symposium on String Processing and Information Retrieval, SPIRE 2012
Country/Territory	Colombia
City	Cartagena de Indias
Period	10/21/12 → 10/25/12

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-34109-0_38

Cite this

Nakashima, Y., I, T., Inenaga, S., Bannai, H., & Takeda, M. (2012). The position heap of a trie. In String Processing and Information Retrieval - 19th International Symposium, SPIRE 2012, Proceedings (pp. 360-371). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7608 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-34109-0_38

The position heap of a trie. / Nakashima, Yuto; I, Tomohiro; Inenaga, Shunsuke et al.
String Processing and Information Retrieval - 19th International Symposium, SPIRE 2012, Proceedings. Springer Verlag, 2012. p. 360-371 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7608 LNCS).

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

Nakashima, Y, I, T, Inenaga, S, Bannai, H & Takeda, M 2012, The position heap of a trie. in String Processing and Information Retrieval - 19th International Symposium, SPIRE 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7608 LNCS, Springer Verlag, pp. 360-371, 19th International Symposium on String Processing and Information Retrieval, SPIRE 2012, Cartagena de Indias, Colombia, 10/21/12. https://doi.org/10.1007/978-3-642-34109-0_38

Nakashima Y, I T, Inenaga S, Bannai H, Takeda M. The position heap of a trie. In String Processing and Information Retrieval - 19th International Symposium, SPIRE 2012, Proceedings. Springer Verlag. 2012. p. 360-371. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-34109-0_38

@inproceedings{6faed5793bd74bd3a500b87ed2dbde89,

title = "The position heap of a trie",

abstract = "The position heap is a text indexing structure for a single text string, recently proposed by Ehrenfeucht et al. [Position heaps: A simple and dynamic text indexing data structure, Journal of Discrete Algorithms, 9(1):100-121, 2011]. In this paper we introduce the position heap for a set of strings, and propose an efficient algorithm to construct the position heap for a set of strings which is given as a trie. For a fixed alphabet our algorithm runs in time linear in the size of the trie. We also show that the position heap can be efficiently updated after addition/removal of a leaf of the input trie.",

author = "Yuto Nakashima and Tomohiro I and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda",

year = "2012",

doi = "10.1007/978-3-642-34109-0_38",

language = "English",

isbn = "9783642341083",

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

publisher = "Springer Verlag",

pages = "360--371",

booktitle = "String Processing and Information Retrieval - 19th International Symposium, SPIRE 2012, Proceedings",

address = "Germany",

note = "19th International Symposium on String Processing and Information Retrieval, SPIRE 2012 ; Conference date: 21-10-2012 Through 25-10-2012",

}

TY - GEN

T1 - The position heap of a trie

AU - Nakashima, Yuto

AU - I, Tomohiro

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

PY - 2012

Y1 - 2012

N2 - The position heap is a text indexing structure for a single text string, recently proposed by Ehrenfeucht et al. [Position heaps: A simple and dynamic text indexing data structure, Journal of Discrete Algorithms, 9(1):100-121, 2011]. In this paper we introduce the position heap for a set of strings, and propose an efficient algorithm to construct the position heap for a set of strings which is given as a trie. For a fixed alphabet our algorithm runs in time linear in the size of the trie. We also show that the position heap can be efficiently updated after addition/removal of a leaf of the input trie.

AB - The position heap is a text indexing structure for a single text string, recently proposed by Ehrenfeucht et al. [Position heaps: A simple and dynamic text indexing data structure, Journal of Discrete Algorithms, 9(1):100-121, 2011]. In this paper we introduce the position heap for a set of strings, and propose an efficient algorithm to construct the position heap for a set of strings which is given as a trie. For a fixed alphabet our algorithm runs in time linear in the size of the trie. We also show that the position heap can be efficiently updated after addition/removal of a leaf of the input trie.

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

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

U2 - 10.1007/978-3-642-34109-0_38

DO - 10.1007/978-3-642-34109-0_38

M3 - Conference contribution

AN - SCOPUS:84867526977

SN - 9783642341083

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

SP - 360

EP - 371

BT - String Processing and Information Retrieval - 19th International Symposium, SPIRE 2012, Proceedings

PB - Springer Verlag

T2 - 19th International Symposium on String Processing and Information Retrieval, SPIRE 2012

Y2 - 21 October 2012 through 25 October 2012

ER -

The position heap of a trie

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this