Efficient algorithm for dynamic text indexing

Ming Gu; Martin Farach; Richard Beigel

Efficient algorithm for dynamic text indexing

Ming Gu, Martin Farach, Richard Beigel

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

Abstract

Text indexing is one of the fundamental problems of string matching. Indeed, the suffix tree, the central data structure of string matching, was developed as an efficient static text indexer. The text indexing problem is that of building a data structure on a text which allows the occurrences of patterns to be quickly looked up. All previous text indexing schemes have been static in the sense that if the text is modified, the data structure must be rebuilt from scratch. In this paper, we present a first dynamic data structure and algorithms for the On-line Dynamic Text Indexing problem. Our algorithms are based on a novel data structure, the border tree, which exploits string periodicities.

Original language	English (US)
Title of host publication	Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
Publisher	Publ by ACM
Pages	697-704
Number of pages	8
ISBN (Print)	0898713293
State	Published - 1994
Event	Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms - Arlington, VA, USA Duration: Jan 23 1994 → Jan 25 1994

Publication series

Name	Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

Other

Other	Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms
City	Arlington, VA, USA
Period	1/23/94 → 1/25/94

ASJC Scopus subject areas

Software
General Mathematics

Cite this

@inproceedings{1ad96db545714fd88c7354839ed5eb06,

title = "Efficient algorithm for dynamic text indexing",

abstract = "Text indexing is one of the fundamental problems of string matching. Indeed, the suffix tree, the central data structure of string matching, was developed as an efficient static text indexer. The text indexing problem is that of building a data structure on a text which allows the occurrences of patterns to be quickly looked up. All previous text indexing schemes have been static in the sense that if the text is modified, the data structure must be rebuilt from scratch. In this paper, we present a first dynamic data structure and algorithms for the On-line Dynamic Text Indexing problem. Our algorithms are based on a novel data structure, the border tree, which exploits string periodicities.",

author = "Ming Gu and Martin Farach and Richard Beigel",

year = "1994",

language = "English (US)",

isbn = "0898713293",

series = "Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms",

publisher = "Publ by ACM",

pages = "697--704",

booktitle = "Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms",

note = "Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms ; Conference date: 23-01-1994 Through 25-01-1994",

}

TY - GEN

T1 - Efficient algorithm for dynamic text indexing

AU - Gu, Ming

AU - Farach, Martin

AU - Beigel, Richard

PY - 1994

Y1 - 1994

N2 - Text indexing is one of the fundamental problems of string matching. Indeed, the suffix tree, the central data structure of string matching, was developed as an efficient static text indexer. The text indexing problem is that of building a data structure on a text which allows the occurrences of patterns to be quickly looked up. All previous text indexing schemes have been static in the sense that if the text is modified, the data structure must be rebuilt from scratch. In this paper, we present a first dynamic data structure and algorithms for the On-line Dynamic Text Indexing problem. Our algorithms are based on a novel data structure, the border tree, which exploits string periodicities.

AB - Text indexing is one of the fundamental problems of string matching. Indeed, the suffix tree, the central data structure of string matching, was developed as an efficient static text indexer. The text indexing problem is that of building a data structure on a text which allows the occurrences of patterns to be quickly looked up. All previous text indexing schemes have been static in the sense that if the text is modified, the data structure must be rebuilt from scratch. In this paper, we present a first dynamic data structure and algorithms for the On-line Dynamic Text Indexing problem. Our algorithms are based on a novel data structure, the border tree, which exploits string periodicities.

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

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

M3 - Conference contribution

AN - SCOPUS:0028197844

SN - 0898713293

T3 - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

SP - 697

EP - 704

BT - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

PB - Publ by ACM

T2 - Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms

Y2 - 23 January 1994 through 25 January 1994

ER -

Efficient algorithm for dynamic text indexing

Abstract

Publication series

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this