Databases
StackOverflow2013
Postsdbo
POApproximate, incremental nearest-neighbour algorithm for moving bodies
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POApproximate, incremental nearest-neighbour algorithm for moving bodies
    primarykey
    data
    text
    <h3>Bounty</h3> <p>This question raises several issues. The bounty will go to an answer which addresses them holistically.</p> <hr> <p>Here's a problem I've been playing with.</p> <p><strong>NOTE</strong> I'm especially interested in solutions that are <strong>not based in Euclidian space.</strong></p> <p>There is a set of Actors which form a crowd of size K. The distance <code>d(ActorA,ActorB)</code> is easily computable for any two actors (solutions should work for various definitions of 'distance') and we can find the set of N nearest neighbours for any given Actor using any of a number of established algorithms.</p> <p>This neighbour set is correct at the first instant but <strong>the Actors are always moving</strong> and I want to maintain the evolving list of N nearest neighbours for each Actor. What I am interested in is <em>approximate</em> solutions which are more efficient than perfect solutions.</p> <ol> <li><strong>Solutions should converge to correctness</strong> after errors have been introduced.</li> <li>It is acceptable to sometimes perform a full recomputation if the errors become too large but <strong>detecting these errors should be cheap</strong>.</li> </ol> <p>So far I have been using a <em>friend-of-a-friend</em> algorithm:</p> <pre><code>recompute_nearest (Actor A) { Actor f_o_f [N*N]; for each Actor n in A.neighbours append n to f_o_f if n != A and n not in f_o_f Distance distances [N*N]; for 0 &lt;= i &lt; f_o_f.size distances [i] = distance (A, f_o_f [i]) sort (f_o_f, distances) A .neighbours = first N from f_o_f } </code></pre> <p>This performs reasonably well when the crowd is slow-moving and N is suitably large. It converges after small errors, satisfying the first criteria, but</p> <ul> <li>I don't have good way to detect large errors,</li> <li>I have no quantitative description of the size and frequency of errors,</li> <li>it converges in practice but I can't <em>prove</em> that it always will.</li> </ul> <p>Can you help with any of these points?</p> <p>Also, do you know of any alternative approaches which perform well</p> <ul> <li>when the crowd is fast-moving,</li> <li>when <em>some</em> actors are fast-moving,</li> <li>when N is small,</li> <li>when the crowd is sparse in some places and dense in others,</li> <li>or with particular spacial-indexing algorithms?</li> </ul> <p>The extension I'm working on at the moment is to generalise friend-of-a-friend to take the friend-of-a-friend-of-a-friend in cases when a neighbour is fast-moving. I suspect that this doesn't scale to well and it's hard to derive the right parameters without a quantification of the errors.</p> <p>I welcome all suggestions! It's a fun little problem :-)</p> <hr> <h3>Notable Suggestions So Far</h3> <p>Fexvez: sample random extra neighbours, sample size depending on the speed of the Agent. <em>Sampling from the area it's about to move into would probably also help.</em></p> <p>Resample the neighbours when an agents <code>speed*delta_time</code> exceeds the distance to the furthest known neighbour.</p> <p>Maintain the <a href="http://en.wikipedia.org/wiki/Delaunay_triangulation" rel="nofollow">Delaunay triangulation</a> which is a superset of the nearest-neighbour graph. <em>Only accounts for <strong>one</strong> nearest neighbour.</em></p> <p>David Mount's <a href="http://www.cs.umd.edu/~mount/ANN/" rel="nofollow">ANN library</a> <em>Doesn't seem to handle <strong>moving</strong> bodies.</em></p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USsbridges
    1. USspraff
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    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. POApproximate, incremental nearest-neighbour algorithm for moving bodies
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POApproximate, incremental nearest-neighbour algorithm for moving bodies
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POApproximate, incremental nearest-neighbour algorithm for moving bodies
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWhat is the problem's dimensionality?
      singulars
      1. POApproximate, incremental nearest-neighbour algorithm for moving bodies
      1. USDon Reba
    2. COI'm defining "distance" as a combination of 2D/3D Euclidian distance and also fuzzy set membership in arbitrarily high dimensions (in practice, less than 10).
      singulars
      1. POApproximate, incremental nearest-neighbour algorithm for moving bodies
      1. USspraff
    3. COGot a max K? Is distance() the only func given? Or can u compute an actor's path or next position, or reasonably estimate it's path by comparing subsequent positions? Eg, is it possible to compute 4 each actor which other actors can never become a nearer neighbor if their current paths remain unchanged? Hasn't this already been tackled inside galaxy simulators? Is your crowd like a flock of birds or travelers on the floor of Grand Central or something else? Ie, u got any (rough) metrics of how often/how many actors' nearest neighbors change? By "more efficient" u mean faster? Memory is free?
      singulars
      1. POApproximate, incremental nearest-neighbour algorithm for moving bodies
      1. USjoe snyder
 

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