Am I reinventing the wheel?

Question

Data Structures

Residue tree

Recently I came up with the following idea:

If you take a list of primes 2,3,5,7…
You can build a tree where each level of the tree corresponds to a prime number, and all nodes of this level have the same number of children as this number. The position in the tree is determined by taking the remainder of division by a prime number. We can say that we encode the number in the system of residual classes (RCS).
Let's say the number 15 can be encoded like this:
15% 2 = 1
15% 3 = 0
15% 5 = 0
So the search path for an element in the tree will be 1 0 0

Here is an example of a complete tree for base (2,3)
dl.dropbox.com/u /20772796/tree.png

What is your expert opinion, have you met such data structures?

If anyone is interested, I sketched the first implementation on Scala github.com/netslow/rtree

Answer 1

It is necessary to evaluate the complexity of adding / removing and searching for an element in such a tree.
Then compare with standard implementations (Binary, B-Tree, AVL, etc.) and then judge the applicability of this tree to tasks.
It may well turn out that in real use the complexity will be extremely high (taking the integer part is not such an easy task, it takes much longer than simply comparing 2 numbers).

Answer 2

Didn't meet. Have you come up with any use for this yet? The idea is beautiful

Answer 3

It seems to me that it is worth analyzing a specific use case (better 2 - successful and not very good). Then, using the example of solving a problem, it will already be possible to assess the complexity of using this solution and compare it with other options for solving the problem.

Answer 4

at the IPPM RAS, a whole institute is engaged in this. some things count very quickly. and if we add logarithmetic ... in general, this method is at least 50 years old

Answer 5

What is the purpose of this tree? Give a couple more examples for other numbers (for example, 7, 12, 14).

Answer 6

the idea is interesting, but not practical for a large amount of data.
For a large tree, you need to have a large list of primes

Answer 7

huge memory costs, I think in its pure form the algorithm is not applicable in real life.