Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: multi-dimensional range lookup

by mattr (Curate)
on May 10, 2007 at 08:26 UTC ( #614566=note: print w/ replies, xml ) Need Help??


in reply to multi-dimensional range lookup

I looked at mysql's spatial point types which are 2D but you can add an index to them to perhaps make them 3D.. but hey that's not fun right?

I treated the problem as finding points within a sphere of some radius around a point in question. It's not something you want to do for a million photos just yet, but... Actually it's quite fast! (So you can use Perl DBI or DBIx::Class with about the same speed.) This is a search for all points within a 20 pixel radius sphere centered around the color (25,25,25).

# mysql -uroot -pPu5huqep space -e 'desc point' +-------+---------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +-------+---------+------+-----+---------+----------------+ | id | int(11) | | PRI | NULL | auto_increment | | x | int(11) | | | 0 | | | y | int(11) | | | 0 | | | z | int(11) | | | 0 | | | alpha | int(11) | | | 0 | | +-------+---------+------+-----+---------+----------------+ # for (( i=1; i<=1; i++ )); do `mysql -uroot -pPu5huqep space -e 'ins +ert into point (x,y,z) values (255*RAND(),255*RAND(),255*RAND());'` ; +done # mysql space -e 'select count(*) from point' +----------+ | count(*) | +----------+ | 10105 | +----------+ # time mysql space -e 'select count(*) from point where (( ((x-25)*(x- +25))+((y-25)*(y-25))+((z-25)*(z-25))) < 400)' +----------+ | count(*) | +----------+ | 39 | +----------+ real 0m0.013s user 0m0.006s sys 0m0.003s
So the idea would be to generate a palette of say the top 100 colors for each photo, where the photo id goes in the 'w' column and the r,g,b for each point goes in columns x,y,z. Then the 10,000 points I used would represent 100 photos. So it would seem in 10 seconds mysql could return a query for 100,000 photos using this method (I haven't timed it for that many yet though). Here's a bigger test, the search takes the same amount of time regardless of radius.
# mysql space -e 'select count(*) from point ' +----------+ | count(*) | +----------+ | 100106 | +----------+ # time mysql space -e 'select count(*) from point where (( ((x-25)*(x- +25))+((y-25)*(y-25))+((z-25)*(z-25))) < 400)' +----------+ | count(*) | +----------+ | 310 | +----------+ real 0m0.049s user 0m0.006s sys 0m0.002s


Comment on Re: multi-dimensional range lookup
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://614566]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (9)
As of 2014-09-16 15:06 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (32 votes), past polls