0
$\begingroup$

Given $n$ rows with $k$ columns, is there a storage mechanism/data-structure and/or algorithm that enables dynamic restructuring such that I can get the top $t=\mathcal{O}(1)$ results efficiently?

Example strategy 0

$$k_0 \le k_1 \le \cdots \le k_{n-2} \le k_{n-1}$$

Example strategy 1

$$k_{n-1} \le k_{n-2} \le \cdots \le k_1 \le k_0$$

Given [ [0,1] [2,3] [1,2] ] strategy 0 returns: [ [0,1], [1,2] ], where $t=2$.

Restructuring with strategy 1 returns: [ [2,3], [1,2] ]. New strategies can be provided "at runtime".

Given a data-structure solution, here are the methods that it should expose:

  • insert_row (*row) -> inserts a row of $k$ elements into the structure
  • delete_row (*row) -> delete the precisely specified row from structure
  • new_strategy(*k_prioritisation) -> rebalances the structure given the specified strategy
  • top_rows() -> provides top rows after a strategy has been "installed". Number of rows to return is specified at compile time (as a source-code constant).

PS: Bonus points if you can enables strategies like $k_0 \le [\text{all other } k \text{ except } k_0]$, with embedded strategies of much the same.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ I don't understand your question. What is the input (including the runtime constraints), and what is the output? Your example can be solved using sorting in various ways. $\endgroup$
    – Yuval Filmus
    Feb 27, 2015 at 4:27
  • $\begingroup$ @YuvalFilmus Better now? $\endgroup$
    – Raphael
    Mar 4, 2015 at 12:27
  • $\begingroup$ What do you mean by "the weights should propagate down"? What criteria should be used to determine which weights to change, and how? What do you mean by "conflicts are resolved through strict priorities"? Can you define what you mean by "optimal row"? Optimal in what sense? The problem does not seem to be well-specified. Before one can start thinking about an algorithm, the very first step is to make sure you have a precise specification of the algorithmic problem you want solved. $\endgroup$
    – D.W. ♦
    Mar 6, 2015 at 11:47
  • $\begingroup$ @Raphael, no, unfortunately, I still find it unclear (however I can no longer vote to put it on hold until it is clarified, now that it's been re-opened). The question still does not describe what is the desired output and what are the running time constraints (as Yuval suggested). $\endgroup$
    – D.W. ♦
    Mar 6, 2015 at 11:48
  • $\begingroup$ @D.W. I find it clear now; in essence, the goal is to sort w.r.t. an order relation specified by "in column x, smaller/larger is better". There is no runtime restriction, but there does not have to be one. $\endgroup$
    – Raphael
    Mar 6, 2015 at 17:45

1 Answer 1

Reset to default
1
$\begingroup$

Multivariate optimisation (a subproblem of sorting) is usually hard, even offline, because there are no longer "optima" but you have to deal with several Pareto-optimal elements.

Luckily, you have specified that such ties should be broken by strict priorities. In that case, lexicographic sorting (w.r.t. your criteria and in order of the priorities) solves the problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Also one other approach I was considering: 0) Setup k priority queues 1) Iterate over rows, applying weights as you go 2) Pick the top relevant entry in each column. Data-structure: finger tree. $\endgroup$
    – A T
    Mar 4, 2015 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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