Suppose that graph $G$ is induced by a group $⟨α_1,...,α_r⟩$ acting on a large finite set $X$ for small $r$. To be precise, we have the vertex set $V(G):=X$, and $x_1x_2\in E(G)$ whenever for some $\alpha_i$, $\alpha_i x_1=x_2. $ We are now dealing with large number of query inputs $(e_1,e_2,...,e_r)∈\mathbb{Z_r}$ and gives $α_1^{e_1}α_2^{e_2}...α_r^{e_r}\cdot x$.
Another critical fact is that calculating the group multiplication directly has become computationally infeasible. So in some sense we turn into algorithmic improvement based on graph traversal.
It is worth noting that if $X$ is not large, an $O(∑_{1≤i≤r}\log e_i)$ time (relative to group action) could be achieved by a technique done by what we called the "doubling step method." It basically records the $e_i^{2^j}x$ for all x and combine them into output in each query.
Also, this kind of graph is indeed special, in such sense that it must be sparse and composed of lots of cycles overlapped with one another, since it is a group action with small generating set. And here comes my question.
In this case, since $X$ is large, we could not record the global information in our "double step method," is there any relatively "local" method that do not require memorizing the global information (i.e. all $e_i^{2^j}x$) while improving the query complexity? Perhaps based on some heuristic or local preprocessing?
