Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This problem has the same property of instability on addition of new items that similar NP-complete problems do, so I assume it is one also. Since I suspect that you want something that works reasonably well instead of a proof of why it's hard, I'll focus on an algorithm to give an approximate solution.</p> <p>I would solve this problem by converting this into a graph where bins were valued at 1/N if they had to be read N times per second, and blur the graph with a width of M (e.g. 6), peaked at the original. (For 6, I might use weighting (1/6 1/5 1/4 1/3 1/2 1 1/2 1/3 1/4 1/5 1/6).) Then throw bins at all the local maxima (sort pairs by distance apart and cover close pairs of maxima first if you can). Now you'll have most of your most important values covered. Then catch any missing groups by extending the existing reads, or by adding new reads if necessary. Depending on the structure you may want to add some refinement by shifting locations between reads, but if you're lucky that won't even be necessary.</p> <p>Since this is essentially a local algorithm, if you keep track of the blurred graph, you can fairly easily add new items and re-do the peak-covering locally (and the refinement locally).</p> <p>Just to see how this would work on your data, the two-group case would look like (multiplying by 60 so I don't have to keep track of fractional weights)</p> <pre><code> 60 30 20 15 12 10 00 00 00 &lt;- contribution from left-most location 10 12 15 20 30 60 30 20 15 &lt;- second 00 10 12 15 20 30 60 30 20 &lt;- third 00 00 00 10 12 15 20 30 60 &lt;- rightmost -------------------------- 70 42 47 50 74 B5 B0 80 95 (using "B" to represent 11) ^^ ^^ ^^ Local maxima ------------- ------- dist=6 dist=4 |===========| &lt;- Hit closely-spaced peaks first |==| &lt;- Then remaining </code></pre> <p>So we're done, and the solution is optimal.</p> <p>For the three group example, weighting "5" as "1/5" and multiplying everything by 300 so again there are no fractions,</p> <pre><code>060 030 020 015 012 010 000 000 000 000 000 000 &lt;- from 5 on left 050 060 075 100 150 300 150 100 075 060 050 000 &lt;- 1 on left 000 050 060 075 100 150 300 150 100 075 060 050 &lt;- on right 000 000 000 000 000 000 010 012 015 020 030 060 &lt;- 5 on right ----------------------------------------------- 110 140 155 190 262 460 460 262 190 155 140 110 |=======| &lt;- only one peak, grab it === === &lt;- missed some, so pick them back up </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POAlgorithm to find optimal groups
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USRex Kerr
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POAlgorithm to find optimal groups
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COOK, I'm back on this now. Unfortunately, the above algorithm fails in the latter example if all items update at the same rate - you get the same three groups, whereas you should get only two. I'm trying to see if I can tweak the algorithm to correct this, but it seems fundamentally difficult to get it to prefer a bigger group in order to satisfy what is essentially a non-local criterion (mininizing number of groups).
      singulars
      1. PO
      1. USIan Goldby
    2. COYou could repeatedly try to convert triples to pairs until no triples are improved if rewritten as pairs.
      singulars
      1. PO
      1. USRex Kerr
    3. COI've added a bit more to the original question. I should perhaps explain why I am so concerned about this. I expect that in most practical cases the number of groups in the optimal case will be small: just one, two or three maybe. Adding just one extra group therefore is a very large additional cost, relatively speaking. Makes me wonder if a brute-force attack might be the answer…
      singulars
      1. PO
      1. USIan Goldby
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload