discrepancy in KNN function

[David Anderson]

I am using the new KNN functionality to extract polygon adjacency.  I do this by testing where the distance is 0

As I was looking at the results I noticed that polygon A is adjacent to B yet B is not adjacent to A.

Example:

Looking at polygon 144247 we see that polygon 13409 is adjacent

yet when looking at polygon 13409 polygon 144247 is not adjacent.

Any ideas as to why this is occurring?

David

[David Anderson]

Update.  It might be a geometry type issue.  The geometry with the problem was type MULTIPOLYGON ZM that I had mentioned in a prior post.  I cast the geometry to XY, recovered the spatial index.  When I did that the query worked properly.

[David Anderson]

I ran into a similar problem with KNN.  It is not working correctly for some polygons.

WHen looking in a square grid of polygons where there should be 8 adjacent or touching polygons there are cases where either 4 or no records are returns.  Yet using the st_touches function the right number of polygons are returned.  I switched from using the st_touches to the KNN because it is so much faster.

Not returning any touching/adjacent with KNN

With the ST_TOUCHES there correct number of 8 touching is returned.

[a.fu...@lqt.it]

On Fri, 19 Aug 2016 14:19:30 -0700 (PDT), David Anderson wrote:
> I ran into a similar problem with KNN.  It is not working correctly
> for some polygons.
> WHen looking in a square grid of polygons where there should be 8
> adjacent or touching polygons there are cases where either 4 or no
> records are returns.  Yet using the st_touches function the right
> number of polygons are returned.  I switched from using the
> st_touches to the KNN because it is so much faster.
>
> Not returning any touching/adjacent with KNN
>

> With the ST_TOUCHES there correct number of 8 touching is returned.
>

Hi David,

a couple of screenshots is not really useful in order to
identify what is cauising this issue.

if you could kindly send me a sample DB and some SQL
statement exactly reproducing the problem I'll then
be able to set up a proper debug session.

bye Sandro

[David Anderson]

I agree screen shots are not useful for figuring  out the problem.  I put them up to show the query and the results.

I have sent an email with a link to the data set on Google drive.  Included are the queries shown in the screen shots.

[David Anderson]

Just wondering if any progress had been made on identifying the problem.

Using st_touches as a workaround is at least an order of magnitude slower, which adds up when processing a few hundred thousand polygons.

[David Anderson]

Bumping this to the top.  Wondering why an error in a function does not seem to be receiving any attention.

For those that want to replicate the problem here is the text of the email that I sent:

Here is the SQLite data with the data.
https://drive.google.com/file/d/0B_wUhean78RKRE5DdHRNMlhCTnc/view?usp=sharing

Here is the KNN Query that is not returning the adjacent polygons
select 277838 as slink,aa.slink as adj_slink,k.distance
 from ashland_att aa join knn k
 on k.fid=aa.rowid
 where k.f_table_name='ashland_att'
 and k.ref_geometry=(select shape from ashland_att where slink=277838)
 and k.max_items=20
group by k.pos
having k.distance=0

The query return 0 rows for me.

That there are adjacent polygons is shown in this query:

select slink as adj_slink,st_distance(a.shape,b.shape)
 from ashland_att a,ashland_att b
where st_touches(a.shape,b.shape)
and b.slink=277838

This returns 8 rows for me.

The KNN query is working correctly for most of the data.  For example using 10000 instead of 277838
should return 8 records for the KNN query.

[Brad Hards]

> Bumping this to the top. Wondering why an error in a function does not
> seem to be receiving any attention.

This comes across as pretty aggressive.

I don't know this function, and don't have time to work on it in any case.

Perhaps Sandro is on holidays, or is busy on something else, or is sick.

Perhaps consider what you could do to fix it, instead of expecting free
support?

Brad

[mj10777]

On Thursday, 15 September 2016 00:27:38 UTC+2, David Anderson wrote:

Bumping this to the top.  Wondering why an error in a function does not seem to be receiving any attention.

I concur with Brands comments below, you may assume the second given possibility to be correct.

For those that want to replicate the problem here is the text of the email that I sent:

Here is the SQLite data with the data.
https://drive.google.com/file/d/0B_wUhean78RKRE5DdHRNMlhCTnc/view?usp=sharing

Here is the KNN Query that is not returning the adjacent polygons
select 277838 as slink,aa.slink as adj_slink,k.distance
 from ashland_att aa join knn k
 on k.fid=aa.rowid
 where k.f_table_name='ashland_att'
 and k.ref_geometry=(select shape from ashland_att where slink=277838)
 and k.max_items=20
group by k.pos
having k.distance=0

The query return 0 rows for me.

That there are adjacent polygons is shown in this query:

select slink as adj_slink,st_distance(a.shape,b.shape)
 from ashland_att a,ashland_att b
where st_touches(a.shape,b.shape)
and b.slink=277838

This returns 8 rows for me.

The KNN query is working correctly for most of the data.  For example using 10000 instead of 277838
should return 8 records for the KNN query.

Now that there is data to work with, the likelihood of this being 'bumped up' is higher, when time permits. 

I can confirm that:

1) this first query returns 0 results.

2) the second returns 8 records after the faulty sql was corrected ('select slink as adj_slink' to 'select b.slink as adj_slink')

3) the third query brings 9 results, not 8

Mark

[a.fu...@lqt.it]

On Thu, 15 Sep 2016 08:59:59 +1000, Brad Hards wrote:
>> Bumping this to the top. Wondering why an error in a function does
>> not
>> seem to be receiving any attention.
> This comes across as pretty aggressive.
>
> I don't know this function, and don't have time to work on it in any
> case.
>
> Perhaps Sandro is on holidays, or is busy on something else, or is
> sick.
>

Hi Brad,

thank a lot for your kind support.

I'm not sick, and I wasn't on holidays: what really happened is
that David sent to me his sample-db showing the KNN issue on
August 22.

Unhappily the day after an earthquake hit the central section
of the Apennines killing about 300 peoples [1]
The corpse of Fabrizio [2], a dear friend of mine, was finally
found by the Fire Brigade only after two days of painful
uncertainty about his fate.
Just for the chronicles, Fabrizio was a graphic web designer
and a strong Linux supporter, and he contributed several
artworks to the KDE project.

Funeral followed, and after this Fabrizio's mother (a dear
past fiance' of mine) started suffering from severe heart
attacks caused by unbearable sorrow and still continues to
be recovered into one of the main hospitals in Rome for
medical cares.

Facing unexpected real world events often has an higher
priority than resolving software issues.

bye Sandro

[1] https://en.wikipedia.org/wiki/2016_Central_Italy_earthquake
[2]
http://www.repubblica.it/cronaca/2016/08/25/foto/terremoto_storie_e_volti_delle_vittime-146597660/1/#1

[David Anderson]

Sando, Let me first offer my condolences on the loss of your friend. Eternal rest grant unto him and my perpetual light shine upon him. And a prayer of healing for your other friend.

I figured something else besides software development was going on as I did not see any posts from Sandro.  Which is why I did not push the issue for several weeks and I was just waiting patiently.  Until I saw the post about the characters in the path name issue.  I saw a bunch of discussion about trouble shooting a minor problem in another piece of software.  To me that post is someone asking for free support.  My post is noting that I have found a error condition in a new piece of Spatialite functionality.  I thought Sandro might want to know about this error.  So yeah, I admit I was a little bothered that people seem more than ready to help with what appear to me to be peripheral issues and not with core issues.

I thought this forum was the place to bring issues.  Not a place criticize and rebuke those trying to help.  A simple reply of we are still looking into the issue would have sufficed.

[David Anderson]

On Wednesday, September 14, 2016 at 5:00:14 PM UTC-6, Brad Hards wrote:

> Bumping this to the top.  Wondering why an error in a function does not
> seem to be receiving any attention.
This comes across as pretty aggressive.

I don't know this function, and don't have time to work on it in any case.

It came out about 10 months ago in the 4.4.rc 0 version.  It is kind of new.  It is also really fast and great for doing work that involves spatial adjacency.  You should try it out when you have time.

 

Perhaps Sandro is on holidays, or is busy on something else, or is sick.

Perhaps consider what you could do to fix it, instead of expecting free
support?

 

Please explain to me how this post:

linker errors while building libspatialite-4.4.0-RC0

https://groups.google.com/forum/#!topic/spatialite-users/-DDqzRnERcw

is not someone looking for free support? which you provided

 

Brad

[David Anderson]

Sandro requested that the data be sent to him as you can see by reading the entire thread.  Which is what I did.  If you wanted the data all you had to do was ask.

I can confirm that:

1) this first query returns 0 results.

2) the second returns 8 records after the faulty sql was corrected ('select slink as adj_slink' to 'select b.slink as adj_slink')

The SQL in query 2 is not faulty, though it is not fully specified.  I want the polygons in  table a that are adjacent to the polygon in table b.  Correct SQL would be select a.slink as adj_slink.  Using b.slink just repeats the where clause for 8 rows.  Not particularly useful information.

 

3) the third query brings 9 results, not 8

I forgot a to include a part of the where clause.  where aa.slink<>277838.  Otherwise the KNN will return the calling feature, where the feature and the adjacent feature are the same.  Sorry about the mixup.

[mj10777]

It is assumed that when data is not made public, that there are good reason for not doing so

- such as copyright or confidentiality restrictions  

I can confirm that:

1) this first query returns 0 results.

2) the second returns 8 records after the faulty sql was corrected ('select slink as adj_slink' to 'select b.slink as adj_slink')

The SQL in query 2 is not faulty, though it is not fully specified.  I want the polygons in  table a that are adjacent to the polygon in table b.  Correct SQL would be select a.slink as adj_slink.  Using b.slink just repeats the where clause for 8 rows.  Not particularly useful information.

 

3) the third query brings 9 results, not 8

I forgot a to include a part of the where clause.  where aa.slink<>277838.  Otherwise the KNN will return the calling feature, where the feature and the adjacent feature are the same.  Sorry about the mixup.

I have opened a ticket

 https://www.gaia-gis.it/fossil/libspatialite/tktview/000b0fb3fda6d0df6e7319414f069914ade0df7f

showing the results of what I could determine.

In short: a final conclusion as to the cause cannot be made at the moment.

In the database itself, I could find no faults.

The used code looks sane.

With a subset of the main table, both queries work correctly.

The (sqlite3) callback function (vknn_query_callback) is not receiving all of the data that needs to be filtered

- Speculation: some sort of time out ?? 

So other than ruling out many possible causes, the problem remains open.

Mark

[mj10777]

It is possible that something has been found that could also be the cause of this problem

- not knowing your data as well as the data I used, it could not be reproduced

-- had however a similar effect, so I hope it is the same problem

The cause is at the moment not clear, but the symptoms are

- so we now have something to look for.

Mark

[David Anderson]

On Tuesday, September 20, 2016 at 8:23:27 AM UTC-6, mj10777 wrote:

It is possible that something has been found that could also be the cause of this problem

- not knowing your data as well as the data I used, it could not be reproduced

-- had however a similar effect, so I hope it is the same problem

The cause is at the moment not clear, but the symptoms are

- so we now have something to look for.

M

 Mark,

Thanks for opening the ticket and starting the debugging process.

For reference the geometry was generated using the ST_SquareGrid function on a large area, then using the ElementaryGeometries function on the result from the square_grid function. 

David