Thread: UB-Tree
Hi, The inventor of the B-Tree algorythm, R. Bayer, published in the past years ('96-'01) several scientific papers where he describes the new UB-Tree algorythm. It is based on ordinary B-Tree implementation but allows >multidimensional< indexing. Apart from the need to update only one index instead of several for each table insert/delete the UB-Tree indexing allows to perform extremly performant lookups for queries that contain constraints for several columns (dimensions) and sort criterias, like: SELECT * FROM EMPLOYEES WHERE ID>10 AND ID<100 AND INCOME>5000 SORTED BY NAME Such a query could profit from an UB-Tree index on the columns (dimensions) ID, INCOME and NAME - all at once, using only one UB-Tree! So the UB-Tree allows you:- to make range queries on all dimensions at once, and- read the result in sorted order (with onlylittle overhead), where- each dimension can be read in sorted or reverse order I guess such an indexing method would please any SQL database. Has anybody of you ever stumbled across the UB-Tree related algorythms? If not, you can download several PDF documents describing the UB-Tree related algorythms from this URL (in english language!): http://mistral.in.tum.de I found no free implementation of the UB-Tree. The team of R. Bayer only released closed source and sell it. kind regards, Robert Schrem
On Fri, 2002-03-08 at 20:48, Robert Schrem wrote: > > If not, you can download several PDF documents describing > the UB-Tree related algorythms from this URL (in english > language!): > > http://mistral.in.tum.de The last one tere seems to be the original explanation of the idea. > I found no free implementation of the UB-Tree. The team > of R. Bayer only released closed source and sell it. This technique seems to be a good candidate for implementing using GiST or perhaps just defined using the <. operator mentioned there. Mappign from ordinary query with several = , < and between may be a little tricky though. They may also have patents on it, so we should move carefully here. ------------- Hannu
----- Original Message ----- From: "Robert Schrem" <robert@schrem.de> To: "Hannu Krosing" <hannu@krosing.net> Cc: "PostgreSQL Hackers List" <pgsql-hackers@postgresql.org> Sent: Monday, March 11, 2002 11:55 AM Subject: Fwd: Re: [HACKERS] UB-Tree > On Friday 08 March 2002 20:37, Hannu Krosing wrote: > > They may also have patents on it, so we should move carefully here. > > I sent a mail asking R. Bayer about any known patent issues. > He said that the UB-Tree is internationally patented. > Sad, because it looked like a briliant idea. Now it looks like > it will be banned from the open source community for some > decades to come... :-( IANAL, but there seem to be some issues : 1. There is no such thing as 'internationally patented' as most countries still don't allow patenting software algorithms. 2. I doubt it is possible to patent a general idea, like replacing multiple one-dimensional indexes with one multi-dimensional index (conceptually they _are_ the same thing, just optimised for different access paterns) So as we can't use UB-Tree, we may well achieve similar result buy using a multi-dimensional/multi-type R-tree and teach our optimiser to use it for resolving multiple where clause restrictions simultaneously. Of course this too may be patented. If it is not, let's hope this e-mail will be archived and can be used as prior art to prevent future patenting attempts :) Another common way of fighting such patent's is patenting all possible future improvements and then haggle with the patent holder . I think this could be something that is effectively doable by open-source community, at least the part of generating the ideas. ------------- Hannu