Re: (tye)Re2: Algorythym for searching closest neighbor

Hey!

Well I'm glad I helped out at least a little. I reread last nights post (I'm feeling -much- better now after 8 hours of sleep) and I agree, my description was mostly incomprehensible. I think I needed a picture or a phD last night to do better :) , sorry.

I definitely agree, that a voronoi diagram isn't suited for a relational database. At least, you shouldn't put your code in SQL or some such pseudo-language (hmm, that -wasn't- flame bait, I'm having to do a website at work, for the second time, in SQL ...shudder...). But I think it's easy enough to put the voronoi data in the database, and then use something secondary (hmm, perl? :) ) to process it.

Anyway the other method I described seems to be halfway between yours and the voronoi. But, your method seems -very- complicated. It seems that you -might- have been too worried about trimming tests than doing tests (I don't know for certain since I don't have the actual code in front of me :) ). With the simple method you do a -very- quick test, and you've limited the search space to, hopefully, much less than a hunderd or so points (probably just ten or so). If you want to guarantee even less points, do a up-down as well as a left-right initial search. Anyway, you do some quick tests, and you can limit the tests to a reasonable amount. Then you test, you can't be afraid of testing, or you might spend more time avoiding tests than what you save :) .

Time for work!

Ciao,
Gryn

Comment on Re: (tye)Re2: Algorythym for searching closest neighbor

Replies are listed 'Best First'.
(tye)Re3: Algorythym for searching closest neighbor by tye (Sage) on Apr 04, 2001 at 21:07 UTC
Two quick notes: First, the point is to not have to load the entire structure into RAM so the Voroni diagram would have to be coded into the database such that you could use a database index to find the part of the diagram that you need to worry about. I don't see a way to do that. Second, the problem isn't that I'd have to compare a few more points, it is that I'd have to read records. The I/O for reading a record usually takes much longer than comparing a few hundred points would. So, yes, I did some extra work to avoid reading more records, but I don't think the resulting implementation was much more complicated than you'd get implementing the algorithm you described if you factor the problem well and deal with all of the edge/corner cases. - tye (but my friends call me "Tye")	[reply]

Replies are listed 'Best First'.

(tye)Re3: Algorythym for searching closest neighbor
by tye (Sage) on Apr 04, 2001 at 21:07 UTC

Two quick notes: First, the point is to not have to load the entire structure into RAM so the Voroni diagram would have to be coded into the database such that you could use a database index to find the part of the diagram that you need to worry about. I don't see a way to do that.

Second, the problem isn't that I'd have to compare a few more points, it is that I'd have to read records. The I/O for reading a record usually takes much longer than comparing a few hundred points would. So, yes, I did some extra work to avoid reading more records, but I don't think the resulting implementation was much more complicated than you'd get implementing the algorithm you described if you factor the problem well and deal with all of the edge/corner cases.

tye

[reply]