Thread: efficient way to do "fuzzy" join

On 4/11/2014 7:50 AM, Rémi Cura wrote:
> Hey dear List,
>
> I'm looking for some advice about the best way to perform a "fuzzy"
> join, that is joining two table based on approximate matching.
>
> It is about temporal matching
> given a table A with rows containing data and a control_time (for
> instance 1 ; 5; 6;  .. sec, not necessarly rounded of evenly-spaced)
>
> given another table B with lines on no precise timing (eg control_time =
> 2.3 ; 5.8 ; 6.2 for example)
>
> How to join every row of B to A based on
> min(@(A.control_time-B.control_time))
> (that is, for every row of B, get the row of A that is temporaly the
> closest),
> in an efficient way?
> (to be explicit, 2.3 would match to 1, 5.8 to 6, 6.2 to 6)
>
> Optionnaly, how to get interpolation efficiently (meaning one has to get
> the previous time and next time for 1 st order interpolation, 2 before
> and 2 after for 2nd order interpolation, and so on)?
> (to be explicit 5.8 would match to 5 and 6, the weight being 0.2 and 0.8
> respectively)
>
>
> Currently my data is spatial so I use Postgis function to interpolate a
> point on a line, but is is far from efficient or general, and I don't
> have control on interpolation (only the spatial values are interpolated).
>
>
> Cheers,
> Rémi-C


Have you seen the range type?

http://www.postgresql.org/docs/9.3/static/rangetypes.html

Not fuzzy, but is indexable.

-Andy

> 2014-04-11 17:09 GMT+02:00 Andy Colson <andy@squeakycode.net
> <mailto:andy@squeakycode.net>>:
>
>     On 4/11/2014 7:50 AM, Rémi Cura wrote:
>
>         Hey dear List,
>
>         I'm looking for some advice about the best way to perform a "fuzzy"
>         join, that is joining two table based on approximate matching.
>
>         It is about temporal matching
>         given a table A with rows containing data and a control_time (for
>         instance 1 ; 5; 6;  .. sec, not necessarly rounded of evenly-spaced)
>
>         given another table B with lines on no precise timing (eg
>         control_time =
>         2.3 ; 5.8 ; 6.2 for example)
>
>         How to join every row of B to A based on
>         min(@(A.control_time-B.__control_time))
>         (that is, for every row of B, get the row of A that is temporaly the
>         closest),
>         in an efficient way?
>         (to be explicit, 2.3 would match to 1, 5.8 to 6, 6.2 to 6)
>
>         Optionnaly, how to get interpolation efficiently (meaning one
>         has to get
>         the previous time and next time for 1 st order interpolation, 2
>         before
>         and 2 after for 2nd order interpolation, and so on)?
>         (to be explicit 5.8 would match to 5 and 6, the weight being 0.2
>         and 0.8
>         respectively)
>
>
>         Currently my data is spatial so I use Postgis function to
>         interpolate a
>         point on a line, but is is far from efficient or general, and I
>         don't
>         have control on interpolation (only the spatial values are
>         interpolated).
>
>
>         Cheers,
>         Rémi-C
>
>
>
>     Have you seen the range type?
>
>     http://www.postgresql.org/__docs/9.3/static/rangetypes.__html
>     <http://www.postgresql.org/docs/9.3/static/rangetypes.html>
>
>     Not fuzzy, but is indexable.
>
>     -Andy
>
>

On 4/11/2014 10:57 AM, Rémi Cura wrote:> Hey,
 > thanks for your answer.
 >
 > I think you are right, range type with index could at least provide a
 > fast matching,
 > thus avoiding the numrow(A) * numrow(B) complexity .
 >
 > Though I don't see how to use it to interpolate for more than 1st order.
 >
 > Cheers,
 > Rémi-C
 >
 >


Hum..  Would you like to set an upper bound on the number of seconds the
join would match?  Maybe range types could give you an indexed upper
bound ("match within +/- 2 seconds only"), then use another match to
find the actual min.  (I do something like this in PostGis, use bounding
box to do quick index lookup, then st_distance to find the nearest)

I can see two row's in A matching the same row in B.  Would that be ok?

TableA
------
1
5
6

TableB
------
0.9
1.1
6.6
7.7

How should those two tables join?

-Andy

On 4/11/2014 7:50 AM, Rémi Cura wrote:
> Hey dear List,
>
> I'm looking for some advice about the best way to perform a "fuzzy"
> join, that is joining two table based on approximate matching.
>
> It is about temporal matching
> given a table A with rows containing data and a control_time (for
> instance 1 ; 5; 6;  .. sec, not necessarly rounded of evenly-spaced)
>
> given another table B with lines on no precise timing (eg control_time =
> 2.3 ; 5.8 ; 6.2 for example)
>
> How to join every row of B to A based on
> min(@(A.control_time-B.control_time))
> (that is, for every row of B, get the row of A that is temporaly the
> closest),
> in an efficient way?
> (to be explicit, 2.3 would match to 1, 5.8 to 6, 6.2 to 6)
>
> Optionnaly, how to get interpolation efficiently (meaning one has to get
> the previous time and next time for 1 st order interpolation, 2 before
> and 2 after for 2nd order interpolation, and so on)?
> (to be explicit 5.8 would match to 5 and 6, the weight being 0.2 and 0.8
> respectively)
>
>
> Currently my data is spatial so I use Postgis function to interpolate a
> point on a line, but is is far from efficient or general, and I don't
> have control on interpolation (only the spatial values are interpolated).
>
>
> Cheers,
> Rémi-C


Ok, here is a just sql way.  No ranges.  No idea if its right.  A first
pass, so to speak.



create table a(t float, data text);
create table b(t float, data text);

insert into a values (1), (5), (6);
insert into b values (2.3), (5.8), (6.2);


select a.t, b.t
from (
   select t, least( least(t, mint), least(t, maxt)) as t2 from (
     select t,
      (select t from a where a.t >= b.t order by a.t limit 1) as mint,
      (select t from a where a.t < b.t order by a.t desc limit 1) as maxt
   from b
   ) as tmp
) as tmp2
inner join a on (tmp2.t2 = a.t)
inner join b on (tmp2.t = b.t)




The middle part is the magic:

select t,
  (select t from a where a.t >= b.t order by a.t limit 1) as mint,
  (select t from a where a.t < b.t order by a.t desc limit 1) as maxt
from b

The rest is just to make it usable.  If t is indexed, it'll probably be
fast too.

-Andy

On 4/11/2014 12:16 PM, Andy Colson wrote:
> On 4/11/2014 7:50 AM, Rémi Cura wrote:
>> Hey dear List,
>>
>> I'm looking for some advice about the best way to perform a "fuzzy"
>> join, that is joining two table based on approximate matching.
>>
>> It is about temporal matching
>> given a table A with rows containing data and a control_time (for
>> instance 1 ; 5; 6;  .. sec, not necessarly rounded of evenly-spaced)
>>
>> given another table B with lines on no precise timing (eg control_time =
>> 2.3 ; 5.8 ; 6.2 for example)
>>
>> How to join every row of B to A based on
>> min(@(A.control_time-B.control_time))
>> (that is, for every row of B, get the row of A that is temporaly the
>> closest),
>> in an efficient way?
>> (to be explicit, 2.3 would match to 1, 5.8 to 6, 6.2 to 6)
>>
>> Optionnaly, how to get interpolation efficiently (meaning one has to get
>> the previous time and next time for 1 st order interpolation, 2 before
>> and 2 after for 2nd order interpolation, and so on)?
>> (to be explicit 5.8 would match to 5 and 6, the weight being 0.2 and 0.8
>> respectively)
>>
>>
>> Currently my data is spatial so I use Postgis function to interpolate a
>> point on a line, but is is far from efficient or general, and I don't
>> have control on interpolation (only the spatial values are interpolated).
>>
>>
>> Cheers,
>> Rémi-C
>
>
> Ok, here is a just sql way.  No ranges.  No idea if its right.  A first
> pass, so to speak.
>
>
>
> create table a(t float, data text);
> create table b(t float, data text);
>
> insert into a values (1), (5), (6);
> insert into b values (2.3), (5.8), (6.2);
>
>
> select a.t, b.t
> from (
>    select t, least( least(t, mint), least(t, maxt)) as t2 from (
>      select t,
>       (select t from a where a.t >= b.t order by a.t limit 1) as mint,
>       (select t from a where a.t < b.t order by a.t desc limit 1) as maxt
>    from b
>    ) as tmp
> ) as tmp2
> inner join a on (tmp2.t2 = a.t)
> inner join b on (tmp2.t = b.t)
>
>
>
>
> The middle part is the magic:
>
> select t,
>   (select t from a where a.t >= b.t order by a.t limit 1) as mint,
>   (select t from a where a.t < b.t order by a.t desc limit 1) as maxt
> from b
>
> The rest is just to make it usable.  If t is indexed, it'll probably be
> fast too.
>
> -Andy
>
>
>
>

Here is a guess with ranges:

select a.t, (select t from b where b.t <@ numrange(a.t-2, a.t+2, '[]')
order by abs(a.t-b.t) limit 1)
from a


It returns:
          t           t
----------  ----------
          1         2.3
          5         5.8
          6         5.8


which is different than the previous sql, but its not wrong.  6 is the
same distance between 5.8 and 6.2, so both are the correct choice.

I had to change my tables (or type cast a lot):

create table a(t numeric);
create table b(t numeric);

insert into a values (1), (5), (6);
insert into b values (2.3), (5.8), (6.2);


-Andy

On 04/12/2014 06:29 AM, Rémi Cura wrote:
> (please note that this random string function is NOT the good way to
> do it, i should random int then use it as index to an array
> containing all the letter)
>
> Thanks a lot for this new version! It seems to be slower than your
> first solution (no index use I guess, I gave up after 5 minutes vs 5
> sec for the previous). Morevover, I canno't make assumption about a
> fixed interval (2 sec in your example). But I think I see where you
> are going.
>
>
> After some test, the fastest is using BETWEEN and range. (it is way
> faster than using the <@, strangely)
>
> Here is the code :

Ah, sorry about that.  I got pulled away to work on work stuff.  I was trying to figure out how to use an index on the
rangequery, but not sure, without adding a new column if it would even work. 

I've never had the need for ranges yet, this is the first time I've gotten to play with them.

I would not have thought about between like that, good call.  I'd have never guess it would be so fast.


If you can't use the fixed interval, then ranges are out.

I was thinking this could be improved:

select t,
  (select t from a where a.t >= b.t order by a.t limit 1) as mint,
  (select t from a where a.t < b.t order by a.t desc limit 1) as maxt
from b

It does two selects into a to find the nearest.  Given this:

create table a(t float);

insert into a values (1), (5), (6);

could you write a single query to find the number nearest 3.5?  If so we might cut the work by 50%.

-Andy

PS: This list prefers you don't top post.