Databases
StackOverflow2013
Postsdbo
POSplitting a set of object into several subsets according to certain evaluation
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSplitting a set of object into several subsets according to certain evaluation
    primarykey
    data
    text
    <p>Suppose I have a set of objects, <code>S</code>. There is an algorithm <code>f</code> that, given a set <code>S</code> builds certain data structure <code>D</code> on it: <code>f(S) = D</code>. If <code>S</code> is large and/or contains vastly different objects, <code>D</code> becomes large, to the point of being unusable (i.e. not fitting in allotted memory). To overcome this, I split <code>S</code> into several non-intersecting subsets: <code>S = S1 + S2 + ... + Sn</code> and build <code>Di</code> for each subset. Using <code>n</code> structures is less efficient than using one, but at least this way I can fit into memory constraints. Since size of <code>f(S)</code> grows faster than <code>S</code> itself, combined size of <code>Di</code> is much less than size of <code>D</code>.</p> <p>However, it is still desirable to reduce <code>n</code>, i.e. the number of subsets; or reduce the combined size of <code>Di</code>. For this, I need to split <code>S</code> in such a way that each <code>Si</code> contains "similar" objects, because then <code>f</code> will produce a smaller output structure if input objects are "similar enough" to each other.</p> <p>The problems is that while "similarity" of objects in <code>S</code> and size of <code>f(S)</code> do correlate, there is no way to compute the latter other than just evaluating <code>f(S)</code>, and <code>f</code> is not quite fast.</p> <p>Algorithm I have currently is to iteratively add each next object from <code>S</code> into one of <code>Si</code>, so that this results in the least possible (at this stage) increase in combined <code>Di</code> size:</p> <pre><code>for x in S: i = such i that size(f(Si + {x})) - size(f(Si)) is min Si = Si + {x} </code></pre> <p>This gives practically useful results, but certainly pretty far from optimum (i.e. the minimal possible combined size). Also, this is <em>slow</em>. To speed up somewhat, I compute <code>size(f(Si + {x})) - size(f(Si))</code> only for those <code>i</code> where <code>x</code> is "similar enough" to objects already in <code>Si</code>.</p> <p>Is there any standard approach to such kinds of problems?</p> <p>I know of branch and bounds algorithm family, but it cannot be applied here because it would be prohibitively slow. My guess is that it is simply not possible to compute optimal distribution of <code>S</code> into <code>Si</code> in reasonable time. But is there some common iteratively improving algorithm?</p> <p><strong>EDIT:</strong></p> <p>As comments noted, I never defined "similarity". In fact, all I want is to split in such subsets <code>Si</code> that combined size of <code>Di = f(Si)</code> is minimal or at least small enough. "Similarity" is defined only as this and unfortunately simply cannot be computed easily. I do have a simple approximation, but it is only that — an approximation.</p> <p>So, what I need is a (likely heuristical) algorithm that minimizes <code>sum f(Si)</code> given that there is <em>no</em> simple way to compute the latter — only approximations I use to throw away cases that are very unlikely to give good results.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USdoublep
    1. USdoublep
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. COHow do you define "similar"? Maybe you can formulate it in a way to be able to use an apriori algorithm.
      singulars
      1. POSplitting a set of object into several subsets according to certain evaluation
      1. USBenjamin Bannier
    2. COSince the size delta is completely dependent on `f(S)`, and is correlated with "similarity"... I'm not sure what kind of algorithm you'd expect to find, or how it could help, other than defining "similarity" specifically for size impact on `f(S)` (as @honk) said, and then it becomes trivial to partition.
      singulars
      1. POSplitting a set of object into several subsets according to certain evaluation
      1. USStephen
    3. CO@honk: Well, "similarity" is some intrinsic property of objects or, rather, a set of them. In my case the objects themselves can be seen as maps of points to values; similar objects have many common points, even better if they have the same values at the same points. Unfortunately, this is related but *not* directly defining the size of `f` output.
      singulars
      1. POSplitting a set of object into several subsets according to certain evaluation
      1. USdoublep
 

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