Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

On optimizing syntactic pattern recognition using tries and AI-based heuristic-search strategies.

Ghada Badr1, B John Oommen

  • 1School of Computer Science, Carleton University, Ottawa, ON K1S 5B6, Canada. gbadr@scs.carleton.ca

IEEE Transactions on Systems, Man, and Cybernetics. Part B, Cybernetics : a Publication of the IEEE Systems, Man, and Cybernetics Society
|June 10, 2006
PubMed
Summary

This study introduces clustered beam search (CBS), an AI technique for estimating noisy strings with high accuracy. CBS significantly reduces operations for approximate string matching, improving efficiency by up to 75%.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

The Hierarchical Discrete Pursuit Learning Automaton: A Novel Scheme With Fast Convergence and Epsilon-Optimality.

IEEE transactions on neural networks and learning systems·2023
Same author

Solving Two-Person Zero-Sum Stochastic Games With Incomplete Information Using Learning Automata With Artificial Barriers.

IEEE transactions on neural networks and learning systems·2021
Same author

Achieving Fair Load Balancing by Invoking a Learning Automata-Based Two-Time-Scale Separation Paradigm.

IEEE transactions on neural networks and learning systems·2020
Same author

The Hierarchical Continuous Pursuit Learning Automation: A Novel Scheme for Environments With Large Numbers of Actions.

IEEE transactions on neural networks and learning systems·2019
Same author

A Conclusive Analysis of the Finite-Time Behavior of the Discretized Pursuit Learning Automaton.

IEEE transactions on neural networks and learning systems·2019
Same author

On Solving the Problem of Identifying Unreliable Sensors Without a Knowledge of the Ground Truth: The Case of Stochastic Environments.

IEEE transactions on cybernetics·2017

Area of Science:

  • Computer Science
  • Artificial Intelligence
  • Bioinformatics

Background:

  • Estimating original strings from noisy versions is crucial in various fields.
  • Existing methods for approximate string matching with substitution, insertion, and deletion (SID) errors can be computationally intensive.
  • Dictionary storage in tries is common for efficient string searching.

Purpose of the Study:

  • To develop an enhanced artificial intelligence (AI) technique for accurate estimation of transmitted strings from noisy versions.
  • To introduce a novel heuristic search scheme, clustered beam search (CBS), for approximate string matching.
  • To evaluate the performance of CBS against benchmark methods in terms of speed and accuracy.

Main Methods:

  • Introduced clustered beam search (CBS), a heuristic-based AI search approach.

Related Experiment Videos

  • Applied CBS to approximate string matching on dictionaries stored as tries.
  • Evaluated D (X, Y) for all X in H simultaneously using generalized Levenshtein distance (GLD).
  • Compared CBS with depth-first search (DFS) and standard beam search (BS) on large and small dictionaries.

    • Main Results:

    • Clustered beam search (CBS) demonstrated marked improvement in efficiency, reducing operations by up to 75% on benchmark dictionaries.
    • CBS achieved accuracy comparable to optimal methods.
    • For large dictionaries, CBS showed a significant improvement of over 91% compared to standard beam search (BS).

    Conclusions:

    • Clustered beam search (CBS) offers a highly efficient and accurate solution for approximate string matching.
    • The CBS technique provides substantial performance gains over traditional methods like DFS and BS, especially for large datasets.
    • This AI-driven approach enhances the estimation of noisy strings in various applications.