Databases
StackOverflow2013
Postsdbo
POOptimizing cartesian requests with affine costs
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POOptimizing cartesian requests with affine costs
    primarykey
    data
    text
    <p>I have a cost optimization request that I don't know how if there is literature on. It is a bit hard to explain, so I apologize in advance for the length of the question.</p> <p>There is a server I am accessing that works this way:</p> <ul> <li>a request is made on records (r1, ...rn) and fields (f1, ...fp)</li> <li>you can only request the Cartesian product (r1, ..., rp) x (f1,...fp)</li> <li>The cost (time and money) associated with a such a request is affine in the size of the request:</li> </ul> <p><code>T((r1, ..., rn)x(f1, ..., fp) = a + b * n * p</code></p> <p>Without loss of generality (just by normalizing), we can assume that <code>b=1</code> so the cost is:</p> <p><code>T((r1, ...,rn)x(f1,...fp)) = a + n * p</code></p> <ul> <li>I need only to request a subset of pairs <code>(r1, f(r1)), ... (rk, f(rk))</code>, a request which comes from the users. My program acts as a middleman between the user and the server (which is external). I have a lot of requests like this that come in (tens of thousands a day).</li> </ul> <p>Graphically, we can think of it as an n x p sparse matrix, for which I want to cover the nonzero values with a rectangular submatrix:</p> <pre> r1 r2 r3 ... rp ------ ___ f1 |x x| |x| f2 |x | --- ------ f3 .. ______ fn |x x| ------ </pre> <p>Having:</p> <ul> <li>the number of submatrices being kept reasonable because of the constant cost</li> <li>all the 'x' must lie within a submatrix</li> <li>the total area covered must not be too large because of the linear cost </li> </ul> <p>I will name g the sparseness coefficient of my problem (number of needed pairs over total possible pairs, <code>g = k / (n * p)</code>. I know the coefficient <code>a</code>.</p> <p>There are some obvious observations:</p> <ul> <li>if a is small, the best solution is to request each (record, field) pair independently, and the total cost is: <code>k * (a + 1) = g * n * p * (a + 1)</code></li> <li>if a is large, the best solution is to request the whole Cartesian product, and the total cost is : <code>a + n * p</code></li> <li>the second solution is better as soon as <code>g &gt; g_min = 1/ (a+1) * (1 + 1 / (n * p))</code></li> <li>of course the orders in the Cartesian products are unimportant, so I can transpose the rows and the columns of my matrix to make it more easily coverable, for example:</li> </ul> <pre> f1 f2 f3 r1 x x r2 x r3 x x </pre> <p>can be reordered as</p> <pre> f1 f3 f2 r1 x x r3 x x r2 x </pre> <p>And there is an optimal solution which is to request <code>(f1,f3) x (r1,r3) + (f2) x (r2)</code></p> <ul> <li>Trying all the solutions and looking for the lower cost is not an option, because the combinatorics explode:</li> </ul> <pre> for each permutation on rows: (n!) for each permutation on columns: (p!) for each possible covering of the n x p matrix: (time unknown, but large...) compute cost of the covering </pre> <p>so I am looking for an approximate solution. I already have some kind of greedy algorithm that finds a covering given a matrix (it begins with unitary cells, then merges them if the proportion of empty cell in the merge is below some threshold).</p> <p>To put some numbers in minds, my n is somewhere between 1 and 1000, and my p somewhere between 1 and 200. The coverage pattern is really 'blocky', because the records come in classes for which the fields asked are similar. Unfortunately I can't access the class of a record...</p> <p><em>Question 1</em>: Has someone an idea, a clever simplification, or a reference for a paper that could be useful? As I have a lot of requests, an algorithm that works well <em>on average</em> is what I am looking for (but I can't afford it to work very poorly on some extreme case, for example requesting the whole matrix when n and p are large, and the request is indeed quite sparse).</p> <p><em>Question 2</em>: In fact, the problem is even more complicated: the cost is in fact more like the form: <code>a + n * (p^b) + c * n' * p'</code>, where b is a constant &lt; 1 (once a record is asked for a field, it is not too costly to ask for other fields) and <code>n' * p' = n * p * (1 - g)</code> is the number of cells I don't want to request (because they are invalid, and there is an additional cost in requesting invalid things). I can't even dream of a rapid solution to this problem, but still... an idea anyone?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USLeMiz
    1. USLeMiz
    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
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POOptimizing cartesian requests with affine costs
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POOptimizing cartesian requests with affine costs
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POOptimizing cartesian requests with affine costs
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYou have an oracle that tells you which (row,col) are empty for free?
      singulars
      1. POOptimizing cartesian requests with affine costs
      1. USJonathan Graehl
    2. COYou get to name the row and field sets explicitly, i.e. you don't have to specify a contiguous rectangle in a fixed coordinate system (particular row and col permutations)?
      singulars
      1. POOptimizing cartesian requests with affine costs
      1. USJonathan Graehl
    3. CORe: my first question, the answer is yes, if I understand the "requests coming from users" part correctly.
      singulars
      1. POOptimizing cartesian requests with affine costs
      1. USJonathan Graehl
 

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