The position heap of a trie

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

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

8 Citations (Scopus)


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 languageEnglish
Title of host publicationString Processing and Information Retrieval - 19th International Symposium, SPIRE 2012, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783642341083
Publication statusPublished - 2012
Event19th International Symposium on String Processing and Information Retrieval, SPIRE 2012 - Cartagena de Indias, Colombia
Duration: Oct 21 2012Oct 25 2012

Publication series

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


Other19th International Symposium on String Processing and Information Retrieval, SPIRE 2012
CityCartagena de Indias

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'The position heap of a trie'. Together they form a unique fingerprint.

Cite this