Re: Finding matching ranges

Mikito Harakiri <nospam_at_newsranger.com> wrote in message news:
> As far as the original question is conserned, assuming that your problem has an
> indexing solution, it would be also applicable to spatial/temporary domain. The
> fact that spatial doesn't have widely recognised indexing mechanism (compared to
> B-tree) sound like an indicator that your problem is hard.

   As this has become less a product question, and more a general DBMS    question, I feel qualified to answer. Range predicate queries is a    pretty well understood problems that has been solved in some DBMS products.

1. The general consensus (based on the number of papers written and products sold that use the various techniques) is that for data values with "range" properties, such as temporal periods, or spatial shapes, Guttman's R-Tree does the trick.

      http://citeseer.nj.nec.com/context/46230/0

      Contains a list of places in which the original paper is cited. This is
      about double the number for any of the the other techniques. At least
      two commercial products have implemented R-Trees, and Oracle's
      been promising them for some time too.

      http://www.iiug.org/software/index_ORDBMS.html

      This page contains pointers to an implementation of temporal
      range types using R-tree indexing. (Note: I work for IFMX, now IBM, 
      which is why I wrote this code.)

      Other approaches have been proposed. I suggest googling RI-Trees
      and 'interval-trees' for details.

   2. For point indexing, and the problems of "highly-dimensional" indexing
      in general, there is no consensus about what is best, or even if the
      problem is tractable. R-Trees work OK (just OK) for d < 3, say, but
      space-decomposing techniques (like Gridfiles, of kd-b trees, or their
      variants) just might be better.

      http://citeseer.nj.nec.com/context/32207/0

      Grid file paper and its citations.

      Note that no one takes 'space filling curves' very seriously, except as
      a means to improve clustering or marketing.

   3. Given this range of index alternatives, each with its own area of 
      specialty, there is a reasonable argument that the "right way to go" is
      to do a more abstracted indexing interface and make the indexing behavior
      specific to the domain/type, rather than trying to find a "silver
      bullet". The GiST idea is a step in that direction;

      http://gist.cs.berkeley.edu/

      For details.

      Hope this helps.

      KR

                 Pb