locked
Slow performance on multiple nearest neighbor queries RRS feed

  • Question

  • Hi

    I would like to find the nearest neighbor to each point within a list of geography points. I have followed the directions provided here. In order to find the nearest neighbor for a list of points I have cross applied the list using the required syntax and a spatial query hint. The only problem is that this takes a very long time to process even on a powerful server.

    The following code takes more than 3 mins to run when comparing 100 points against another 100 points. I intend to do this with 10,000 x 10,000 points. Is there a faster way to do this?

    create table #l1 (i int primary key, x geography)
    
    ;with ct1 as (
    	select 1 i union all
    	select i+1 i from ct1 where i < 100
    )
    insert into #l1
    select i
    	,geography::Point(
    		180*(cast(cast(checksum(newid()) as bigint)+2147483648 as float)/4294967296)-90
    		,360*(cast(cast(checksum(newid()) as bigint)+2147483648 as float)/4294967296)-180		
    		,4326) x
    from ct1 
    option (maxrecursion 10000)
    
    create spatial index six ON #l1 (x) using GEOGRAPHY_AUTO_GRID with (CELLS_PER_OBJECT = 16) 
    
    create table #l2 (i int primary key, x geography)
    
    ;with ct1 as (
    	select 1 i union all
    	select i+1 i from ct1 where i < 100
    )
    insert into #l2
    select i
    	,geography::Point(
    		180*(cast(cast(checksum(newid()) as bigint)+2147483648 as float)/4294967296)-90
    		,360*(cast(cast(checksum(newid()) as bigint)+2147483648 as float)/4294967296)-180		
    		,4326) x
    from ct1 
    option (maxrecursion 10000)
    
    create spatial index six ON #l2 (x) using GEOGRAPHY_AUTO_GRID with (CELLS_PER_OBJECT = 16) 
    
    select
        l1.*
      from #l1 l1
      cross apply (
        select top 1 l2.i, l2.x
        from #l2 l2 with(index(six))
        where l2.x.STDistance(l1.x) is not null
        order by l2.x.STDistance(l1.x) asc
      ) l2ca

    Thanks

    Blair

    Friday, November 23, 2012 3:38 PM

All replies