[jira] [Created] (IOTDB-5168) Refactor traverse of AbstractTreeVisitor to FA-based traverse

["Yukun Zhou (Jira)" <ji...@apache.org>]

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)