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)