Thread: longest prefix match

Hello

Anybody got any ideas/experiences/links for 'longest prefix match'
solution in PostgreSQL ?
Basically,put some telephone prefices in some kind of trie,and be able
to perform fast lookups ?

Sincerely

Dragan Zubac

Em Wednesday 20 February 2008 05:55:07 Dragan Zubac escreveu:
>
> Anybody got any ideas/experiences/links for 'longest prefix match'
> solution in PostgreSQL ?
> Basically,put some telephone prefices in some kind of trie,and be able
> to perform fast lookups ?

Prefix or suffix?

For prefix you can use "SELECT number FROM table WHERE number LIKE '123%'".

For suffix you change the "%" to the beginning of the string, but then loose
the ability to use indices.  (Unfortunately, using suffixes is really
interesting for caller IDs since you don't always receive area code, country
code, etc.)

--
Jorge Godoy      <jgodoy@gmail.com>

On Wed, 20 Feb 2008, Jorge Godoy wrote:

> Em Wednesday 20 February 2008 05:55:07 Dragan Zubac escreveu:
>>
>> Anybody got any ideas/experiences/links for 'longest prefix match'
>> solution in PostgreSQL ?
>> Basically,put some telephone prefices in some kind of trie,and be able
>> to perform fast lookups ?
>
> Prefix or suffix?
>
> For prefix you can use "SELECT number FROM table WHERE number LIKE '123%'".
>
> For suffix you change the "%" to the beginning of the string, but then loose
> the ability to use indices.  (Unfortunately, using suffixes is really
> interesting for caller IDs since you don't always receive area code, country
> code, etc.)

you can maintain an additional index for terms backwards.


>
>

     Regards,
         Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83