1
$\begingroup$

I was playing with geolocation on maps and stumbled on an interesting problem: I retrieve data from the db ordered by increasing distance from a user input, like a postcode or street, which makes sense as long as I don't use a combination of paging and map browsing, at which point the dataset no longer makes sense. Since the data on the map will be represented in concentric circles, if a user starts browsing the map needs to zoom out in order to accommodate for changing pages. So I thought a better way of sorting data would be by elements' proximity to each other, rather than the user, which is a logical representation of a map I guess (in a geographical sense). But how then given any point on this map can we retrieve an equivalent 1D array that would convey this information?

EDIT: Thanks for your comments. I think it may be that my problem isn't as theoretical as you answers, it's been a few years since I had to cram for my algorithm exams and I've forgotten a whole lot. I'll to give some details, perhaps that will make it clearer:

In this particular case I am looking at around 350 points on the map, and page of around 10. (I think that makes k in Suresh's comment about 20, because on/after the second page distance from q - in this case position of user's query - is not the only relevant factor)

I had a, possibly a not so smart an idea, which I would like to try to explain with the of a crudely drawn diagram in paint:

enter image description here

So diagram A is what I have now, where concentric red circles represent paged results as points get further and further away from the centre red dot. I'd like to be able to drag the map, so that paged results get updated with what's currently closest to the centre of the screen (much like Google results) but with current sorting it's impossible without zooming out to accommodate all the points. A possible solution is to apply some clustering to get a bunch of probably overlapping areas that represent pages as shown in diagram B. That would mean there is some duplication in the returned dataset, but the duplication factor could be tweaked. The green spiral in both diagram indicates roughly increase in distance.

Having said all that, I'm now beginning to think it would be much easier to just use viewport to determine what's currently visible to the user and simply show the results on the page as that. :S

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I think you want to look at en.wikipedia.org/wiki/Nearest_neighbor_search However, I cannot really understand the question. $\endgroup$
    – Radu GRIGore
    Commented Dec 8, 2010 at 15:43
  • $\begingroup$ You may want to check the literature on geometric clustering. $\endgroup$
    – Tsuyoshi Ito
    Commented Dec 8, 2010 at 15:45
  • $\begingroup$ What you probably need is a $k$-NN query where $k$ is appropriately large. In general, if your query result is all the points in the table sorted by increasing distance from the query, then that's a lot harder. What would k be in your example ? (i.e how many points would you need to return before the vantage point changes ? ) $\endgroup$
    – Suresh Venkat
    Commented Dec 8, 2010 at 16:02
  • 1
    $\begingroup$ (in response to your edit): I was going to suggest using a kd-tree-like structure, which might respond well to viewport queries, after which you could then do a local sort. $\endgroup$
    – Suresh Venkat
    Commented Dec 8, 2010 at 17:14

3 Answers 3

Reset to default
3
$\begingroup$

Although it's hard to discern a precise question here, evidently it concerns spatial data structures for efficient local searches of objects. Hanan Samet's books on the subject are classics and almost encyclopedic. He wrote a brief overview of the subject available here. I suspect a simple quadtree would be an attractive solution. In many cases, exploiting a pre-sorting by one of the coordinates provides fine performance and is simple to code.

Improve this answer
$\endgroup$
1
  • $\begingroup$ good reference ! Samet's book is quite comprehensive. $\endgroup$
    – Suresh Venkat
    Commented Dec 9, 2010 at 7:48
1
$\begingroup$

It might be useful to store the data in a graph of nodes corresponding to the Delaunay Triangulation of the geometric data points. Then if you wanted to query an area you could do so by starting with a vertex in your region and then growing a subgraph of the triangulation.

Improve this answer
$\endgroup$
1
$\begingroup$

You should check out R-tree indexes: http://en.wikipedia.org/wiki/R-tree

There are a number of implementations that are available. You would probably want to traverse the tree in a custom manner. Maybe cut the tree at some level and process each subtree in distance from user to bounding box order.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.