fastest way to search in database

[Put Claude]

hi,

Have 1500 utm waypoint in a table, what is the fastest way to search for a match?
By now, I have not the time between two fetches of GPS to search for a match.

Put Claude Belgium

 

[dzt]

Hi,

Store them in a SQLite database table and run SQL SELECT queries. It is much faster than filtering a table control.

 

[alfcen]

Hello Put,

Hard to say without seeing the data and without knowing what you wish to match, however, you could save the table as XML and use the RegEx.dll to match a criteria, such as:

Match1.New1
Regex1.New2("<longitude\b[^>]*>(.*?)</longitude>", true, false)
Match1.Value = Regex1.Match(m)
longitude=StrReplace(Match1.String,"<longitude>","")
longitude=StrReplace(longitude,"</longitude>","")

This example will pick a longitude embraced in the XML <longitude> </longitude> tags or whatever the tag names is in the XML file.

I have only little experience with the RegEx.dll, but it seems to be very fast. Please have a look at Help for the RegEx.dll.

Cheers
Robert

 

[Erel]

You can also try to use ArrayList.IndexOf method.
BTW, what do you mean with "between two fetches of a GPS"?
Maybe you need to increase the interval.

 

[Put Claude]

Yes Erel,

Between 2 NMEA sentences, I have to work with the fetched data...(every second)
In a list of 1500 waypoint, I have to search for match with my actual position point from the sentence.
Suppose I store my position on the last place of the waypointlist, I have to search the list to the end...
On my 400MHz PPC, the time to search the whole waypointlist takes 15 seconds, only to see of a point is in a square with a simple validation routine...
This is what you never hear on a forum... in fact this must be no big deal, because other PPC navigation software must do the job I think.
I am going to try your suggestion to work with arrays, if this is will not do the job, I assume there are special algoritme for PPC use...
Of coarse, I let you hear the results ( otherwise there was no need for a forum |
By the way Erel: it is luxery in speed and use, working with B4PPC

Put Claude Belgium

 

[Erel]

Can you upload your code? It may be interesting to try to optimize it.

 

[Put Claude]

Of coarse it can, give me a day to restore the little changes made to experiment with the data, then you have the absolute working stuff with a lot of comment. I use it very often with a short waypoints list, it warns me for the camera poals in my enviroment where I usely do not think about them...
It warns constantly wen I drive towart, stop warning when I stop / are driving away from the poal, it is made to comfort. Can set or remove waypoints in a easy way while driving, etc... Also (re)connecting Bluetooth is automated...
Wil also write a little Help for it... Thanks for the interest anyway...
I prefare this above many commercial stuff with fancy things, that you can not use, especialy when driving... Oh yes, there is a plotter to, you can drag the plot file into Google Earth to see your plot with speed and all (so I can prove my bike did 150 on that piece of road ;-) ). Have compassion with my code: I am a beginner, and it is still under construction, all comments are welcome...

Put Claude Belgium

 

[Put Claude]

Hi,

Tryed arrays of doubles with UTM point, so being close to just do a compare for a match...
Only gain a few seconds, still get 13 seconds for 1500 points. Have to studie search algorithme...

Put Claude Belgium

 

[LineCutter]

Small tables work, large tables are too slow, but work. You're using GPS data, so can't jump from one end of the table to another without passing through a fair amount of it.

Sort the big data file
Find your start location & filter Lat & Long within a reasonable distance of this (how fast do you drive?).
Copy this to another table & refer to this for the immediate data.
At some distance from the boundary of the GPS data for your filtered table you delete the "wrong" side & add by using a filter the data for the same distance in the direction you are traveling.

Haven't tested this for speed with the filter process in the background & the coordinate processing in full flow.

Alternative would be to use a list & a binary sort routine with boundaries set according to the region of interest, rather than the whole table each time.

 

[Put Claude]

hi LineCutter,

Was thinking this way to, to eliminate as much point as possible, but from the old times, I now some search algorithme that eliminates in jumps of halve the list, so the point of interest from the list must be reached, lets say for a list of 1600 points: in 9 to 10 compares, if this is working, the solution is there... I let the forum now in what I succeeded, and in what not, because I think this is usable for other app to...
Thanks for the interest...

Put Claude Belgium

 

[Erel]

I've compressed one of the images and uploaded your project.

 

[agraham]

I assume that it is sub WPcheck that you want to speed up. A couple of suggestions then :-

Xdistance = WP.Cell("X",i) - utmi(1) 
If abs(Xdistance) < appr Then       
    ' carry on and check Y
End if

The single comparison is neater and faster then the code below. Also saving the distance is faster as it minimises variable accesses and computation time and you would need that result again for its' sign for a binary search (see below).

If WP.Cell("X",i) > utmi(1)-appr Then        '200m voor appr= 200
    If WP.Cell("X",i) < utmi(1)+appr Then    '200m na
        ....
    End if 
End if

If you sort the table by X (or Y)and do a binary search, rather than a linear one like you are doing at the moment, to pick out the possible X (or Y) matches and then do the other comparisons you should end up with a dramatic increase in speed on a large table. Your 1500 item table would only need about 12 of my simplified comparisons above to isolate a WayPoint or decide that you were not near enough to any of them.

 

[LineCutter]

You can cut that further by knowing the region of interest in the data so that the binary search starts inside the absolute boundaries of the list.

For the sake of argument, take the position of the first point found (search the whole database) & then use that index +&-10% of the size of the database as the limits for the next search. Remember, with GPS data at 1 second intervals there are going to be no nasty surprises jumping from one end of the database to the other.

Fewer data points to search == quicker.

 

[Put Claude]

hi agraham, LineCutter,

@ agraham,
did the binair search, and it was a big improvement, only 200 mSec maximum in 11 jumps, In place of 13 Seconds. Now I go try Your code, like you say, it seams that I lost much time going trough approch distance calculations every comparasion. Thanks very much...
Tested your code, great improvement, for 1500 point it speedup from 31 msec to 15 mSec...
@ LineCutter,
After code improvement, I see that your suggestion simply is a must, without going that way it is not possible to get result, so making regions at start with less waypoints to check, I understand, I will be busy for a while now.... Seams you are well now with the problem... and thank you also for pulling me in the right direction..

After reading carfully, I see I misunderstud : I understand now, I have to change the startpoint to search from in the waypointlist from 8 to 10 % around the actual position point every fetch of the new position... so I must only compare a few points in the enviremont.

Put claude Belgium

 

[LineCutter]

After reading carfully, I see I misunderstud : I understand now, I have to change the startpoint to search from in the waypointlist from 8 to 10 % around the actual position point every fetch of the new position... so I must only compare a few points in the enviremont.

You might want to make that +/- 100 points or 10%, whichever is greater. (Or any other numbers, the choice of 100points/10% was arbitrary)

That way you won't miss nearby waypoints in a small database.