Yukun Zhou created IOTDB-5168:
---------------------------------
Summary: Refactor traverse of AbstractTreeVisitor to FA-based
traverse
Key: IOTDB-5168
URL: https://issues.apache.org/jira/browse/IOTDB-5168
Project: Apache IoTDB
Issue Type: Improvement
Reporter: Yukun Zhou
Assignee: Yukun Zhou
Fix For: master branch
The current traverse of AbstractTreeVisitor is implemented based on a mixed
style of traceback and DP.
It has two drawbacks:
1. When encouting **, there's definitely traceback cost. The time complexity of
current traverse is O(mn), m is the length of pattern and n is the num of tree
node.
2. When processing multi pattern or pattern tree, there's no other way but
process them one by one, which costs redundant process of prefix.
FA-based traverse can fix these two problems for the following reason:
1. The time complexity of NFA-based traverse is O(mn) and that of DFA-based
traverse is O(m^2) + O(n), m is the num of state and is of same magnitude as
pattern length. Obviously, DFA-based traverse is quite friendly for tremendous
tree traverse.
2. Multi patterns and pattern tree can be converted to one FA, and it helps
eliminate the redundant process of prefix.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
