1
$\begingroup$

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).

Edit:

To clarify: I would like to find a solution which is sub $O(d log(n))$ for queries.

The successor problem can be solved in at least $O(d)$, even if using some kind of tree. See this resource for an overview.

$\endgroup$
0
$\begingroup$

One approach is to use $d$ binary search trees, one tree per element in $\mathcal{K}$.

The tree for $k \in \mathcal{K}$ stores all items $\hat{x_i} = (p_i, k_i, v_{k_i})$ such that $k_i=k$, keyed on the value $v_{k_i}$.

To insert an item, insert it into the appropriate tree. This can be done in $O(\log n)$ time.

The lookup operation can be done by searching in each binary tree, and taking the best match. When searching in the tree for $k \in \mathcal{K}$, you search for the key $y[k]$. This takes $O(d \log n)$ time.

The successor operation can be implemented similarly to the lookup operation, and also takes $O(d \log n)$ time.

You can speed up the operations to take expected $O(1)$, $O(d)$, and $O(d)$ time (respectively) by replacing each binary search tree with a hash table.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I guess this is essentially my proposed solution. Though I believe you can easily reduce the successor complexity to O(1) or O(d), even with trees. "Efficiency" here would ideally mean completely erasing d from the lookup complexity $\endgroup$ – milck Apr 18 at 7:48
  • $\begingroup$ @milck, I recommend that you edit your question to state that requirement -- I don't see that anywhere in the question. I'm not optimistic that you're going to find a data structure with that complexity. $\endgroup$ – D.W. Apr 18 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.