StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It depends a lot on what your <em>usage</em> patterns are (how my writes, for example, in-memory or on-disk) and how your data looks like (that is how it is distributed).</p> <p>R-trees are good because they are <em>balanced</em>, and allow updating. The R*-tree in my experience is clearly better than the other variants because of the split strategy it has. The benefit is that it produces more square pages than the other strategies, so that for many queries you will need to scan fewer pages.</p> <p>kd-trees are good if you are in-memory and static. Updating them is very bad, you will need to rebuild the index quite often.</p> <p>And if your data does not change very often, bulk-loading for the R-tree works very well. You can do <strong>Sort-Tile-Recursive</strong> bulk loading, which essentially requires (partially) sorting your data on X and Y alternatingly, so it takes a low <code>O(n log n)</code> to build the tree; very similar to bulk-loading an kd-tree, except that you multi-split instead of binary splitting. This is very popular.</p> <p>Furthermore, you can keep track of the number of objects in each page. When displaying things on a map, you may want to stop early when a page would display too small on the screen (i.e. smaller than a marker). At this point, you would not scan that page, but only take the number of objects and display that as a clustered marker until the user zooms in.</p> <p>For 2D data, with a limited value domain, do not overlook the simple things. Quadtrees can work really well, too! Simplicity can make it a lot easier to optimize things. Or a classic grid approach. If your users tend to spread their annotations in an area (and not put them all into one place), you can just compute integer x,y grid coordinates, and then hash them and make a list for each grid cell.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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