so this is more or less a shot in the dark as I am feeling stuck. Maybe some of you have an idea which helps.

Here is the problem description (pseudo formal):

I want to have a structure $ T = \{ \hat{x_1}, \hat{x_2}, … \}$ with $ \hat{x_i} = (p_i, k_i, v_{k_i})$ .

$ p_i \in \mathbb{N}$ can be interpreted as an associated priority. They can be considered unqiue.

$ k_i \in \mathcal{K}$ a *key index*, $ d := |\mathcal{K}|$ is not required to be negligibly small, though generally $ d \lt\lt |T|$

$ v_{k_i} \in \mathcal{V}^{(k_i)}$ a partial key over some universe associated with the given key index. As a little pace killer, this key may not be hashable. The only requirement is totally ordered.

Considering an array $ y = [v_i], i \in \mathcal{K}$ , the structure should be capable of supporting the following operations efficiently:

$ lookup(T, y) \rightarrow \underset{x_i \in T : y[k_i] = v_{k_i}}{arg max}( p_i )$ , i.e. the node $ \hat{x_j}$ with a partial key matching and the highest associated priority.

$ succ(T, y) \rightarrow lookup(T \backslash \{\hat{x_j}\}, y)$ , i.e. the successor (in terms of priority) of a node $ \hat{x_j}$ matching $ y$

Ultimately I would also like efficient insertion and deletion (by priority).

(For insertion: The selection of $ k_i$ for each node is another point of research and can by chosen at the time of insertion. It is essentially possible that this key index is subject to change if it *helps* the overall structure. But it is also not required that all key indices in $ \mathcal{K}$ are supported for each node, i.e. one might need to insert a node which is only queryable by a single $ k_i$ .)

The key indices are somewhat causing a headache for me. My research so far includes standard priority search trees and dynamic variations thereof. I also found this very interesting, though very theoretical, paper which takes care of the increased dimensionality (kind of) caused by the d-dimensional keys.

I know that I can construct d-dimensional binary search trees with a query complexity of $ O(d + n log(n))$ . These should definitely yield a gain though I am not capable of mapping the priority problem to it (Ref).

But I guess the complexity can be reduced even further if we consider that fact, that each node is only storing partial keys anyway.

My approach so far is somewhat naive as it simply creates a hash map for each key index in $ \mathcal{K}$ and queries each hash map upon lookup. It then aggregates all the results and sorts them by priority. This works fine for hashable keys but a fallback structure has to be used whenever they are not (I am using binary search trees).