skip to main content
10.5555/1347082.1347201acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article

Real-time indexing over fixed finite alphabets

Published: 20 January 2008 Publication History

Abstract

The quest for a real-time indexing algorithm is ove three decades old. To date there is no convincing understandable solution to this problem. This paper provides a real-time indexing algorithm over a constant sized alphabet. Assuming the text is arriving at a constant rate, the algorithm spends O(1) time on every text symbol. Whenever a length m pattern is given, the algorithm decides in time O(m) whether there is an occurrence of the pattern in the text thus far.

References

[1]
A. Amir, T. Kopelowitz, M. Lewenstein, and N. Lewenstein. Towards real-time suffix tree construction. In Proc. 12th Symposium on String Processing and Information Retrieval (SPIRE), volume 3772 of LNCS, pages 67--78. Springer, 2005.
[2]
M. Farach. Optimal suffix tree construction with large alphabets. Proc. 38th IEEE Symposium on Foundations of Computer Science, pages 137--143, 1997.
[3]
Z. Galil. On converting on-line algorithms into real-time and on real-time algorithms for string matching and palindrome recognition. SIGACT News, pages 26--30, 1975.
[4]
R. Grossi and G. F. Italiano. Efficient techniques for maintaining multidimensional keys in linked data structures. In Proc. 26th Intl. Col. on Automata, Languages and Programming (ICALP), pages 372--381, 1999.
[5]
Juha Kärkkäinen and Peter Sanders. Simple linear work suffix array construction. In Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP 03), pages 943--955, 2003. LNCS 2719.
[6]
S. Rao Kosaraju. Real-time pattern matching and quasi-real-time construction of suffix trees. Proc. 26th STOC, pages 310--316, 1994.
[7]
U. Manber and G. Myers. Suffix arrays: A new method for on-line string searches. In Proc. 1st ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 319--327, 1990.
[8]
E. M. McCreight. A space-economical suffix tree construction algorithm. J. of the ACM, 23:262--272, 1976.
[9]
A. O. Slisenko. Recognition of palindromes by multi-head turing machines. In Proc. of the Steklov Math. Inst., volume 129, pages 30--202. Acad. of Sciences of the USSR, 1973.
[10]
E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14:249--260, 1995.
[11]
P. Weiner. Linear pattern matching algorithm. Proc. 14 IEEE Symposium on Switching and Automata Theory, pages 1--11, 1973.

Cited By

View all
  • (2017)Full-Fledged Real-Time Indexing for Constant Size AlphabetsAlgorithmica10.1007/s00453-016-0199-779:2(387-400)Online publication date: 1-Oct-2017
  • (2011)Near real-time suffix tree construction via the fringe marked ancestor problemProceedings of the 18th international conference on String processing and information retrieval10.5555/2051073.2051089(156-167)Online publication date: 17-Oct-2011
  • (2011)Persistency in suffix trees with applications to string interval problemsProceedings of the 18th international conference on String processing and information retrieval10.5555/2051073.2051081(67-80)Online publication date: 17-Oct-2011

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms
January 2008
1289 pages
  • Program Chair:
  • Shang-Hua Teng

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 20 January 2008

Check for updates

Author Tags

  1. pattern matching
  2. quasi real time
  3. real time
  4. suffix tree

Qualifiers

  • Research-article

Conference

SODA08
Sponsor:
SODA08: 19th ACM-SIAM Symposium on Discrete Algorithms
January 20 - 22, 2008
California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2017)Full-Fledged Real-Time Indexing for Constant Size AlphabetsAlgorithmica10.1007/s00453-016-0199-779:2(387-400)Online publication date: 1-Oct-2017
  • (2011)Near real-time suffix tree construction via the fringe marked ancestor problemProceedings of the 18th international conference on String processing and information retrieval10.5555/2051073.2051089(156-167)Online publication date: 17-Oct-2011
  • (2011)Persistency in suffix trees with applications to string interval problemsProceedings of the 18th international conference on String processing and information retrieval10.5555/2051073.2051081(67-80)Online publication date: 17-Oct-2011

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media