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.

$\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$ Feb 27 '15 at 4:27
  • $\begingroup$ @YuvalFilmus Better now? $\endgroup$
    – Raphael
    Mar 4 '15 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 '15 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 '15 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 '15 at 17:45
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.

$\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 '15 at 12:40

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.