Skip site navigation (1) Skip section navigation (2)

Re: application of KNN code to US zipcode searches?

From: Heikki Linnakangas <heikki(dot)linnakangas(at)enterprisedb(dot)com>
To: Mark Stosberg <mark(at)summersault(dot)com>
Cc: pgsql-performance(at)postgresql(dot)org
Subject: Re: application of KNN code to US zipcode searches?
Date: 2011-02-17 16:41:29
Message-ID: 4D5D4FB9.8020709@enterprisedb.com (view raw or flat)
Thread:
Lists: pgsql-performance
On 17.02.2011 17:20, Mark Stosberg wrote:
>> I thought the benefit of KNN was that you could retrieve the rows in
>> distance order, so that a query for the closest 20 locations (for
>> example) would be very fast.  I wouldn't have expected it to be
>> helpful when you're selecting all the rows regardless of distance.
>
> Kevin,
>
> Thanks for the feedback. You are right that my "reduced test case"
> wasn't a good approximation. I added a limit, to simulate finding the
> 100 zipcodes closest to 90210.
>
> Below I compare 4 approaches to the same query:
>
> 1. Cube search
> 2. Earth Distance Search
> 3. Simple point distance (no index)
> 4. Simple point distance (KNN)
>
> Now KNN benchmarks to be almost 100x faster! That's very promising.
> Then there's only the issue that simple point distance is not expected
> to be a good enough approximation of earth-distances. Perhaps that can
> be solved by pre-computing coordinates based on the lat/long pairs....
> much like the map projections used to present a curved surface on a flat
> map? Given that's OK to be be a few miles off, it seems we have some
> leeway here.
>
> Recommendations?

The existing opclasses only support distance-to-a-point, but I believe 
the KNN gist code is flexible enough that it could be used for distance 
to the edge of a shape as well. Someone just needs to write the 
operators and support functions.

-- 
   Heikki Linnakangas
   EnterpriseDB   http://www.enterprisedb.com

In response to

Responses

pgsql-performance by date

Next:From: Mark StosbergDate: 2011-02-17 16:41:51
Subject: Re: application of KNN code to US zipcode searches?
Previous:From: Mark StosbergDate: 2011-02-17 15:55:53
Subject: Re: application of KNN code to US zipcode searches?

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group