Re: Data structure for indexing on multiple keys.

From: Mikito Harakiri (mikharakiri_at_iahu.com)
Date: 09/09/04 

Date: Thu, 9 Sep 2004 14:42:38 -0700

"Jose Juan Mendoza Rodriguez" <me@privacy.net> wrote in message
news:hj5qhc.ga.ln@ID-112571.user.uni-berlin.de...
>
> > Please note that this is not about composite keys but supporting
> >multiple keys for searching. Thanks in advance for inputs!
> >
> >Regards,
> >Shankar
>
> Hello,
>
> it is ironic that you are posting from news.oracle.com and asking this.
> There is an awful lot of these structures, each one intended for
> different applications (for example, in-memory or filesystem-based?).
> There is a somewhat old survey paper published in ACM Computing Surveys,
>
> Volker Gaede, Oliver Günther
> Multidimensional Access Methods
> ACM Computing Surveys, Vol. 30, No. 2, June 1998
>
> If you do not have access to this paper, try searching the web for the
> following keywords. For main memory:
>
> k-d Tree (Bentley)
> BSP Tree (Fuchs)
> BD Tree (Ohsawa and Sakauchi)
> Quadtree
>
> For secondary storage:
>
> k-d-B Tree (Robinson)
> LSD Tree (Henrich)
> Buddy Tree (Seeger and Kriegel)
> BANG File (Freeston)
> hB Tree (Lomet and Salzberg)
> BV Tree (Freeston)
> R-Tree (Guttman)
> R* Tree (Beckmann)
> P-Tree (Jagadish)
> P-Tree (Schiwietz)
> SKD Tree (Ooi)
> GBD Tree (Ohsawa and Sakauchi)
> PLOP Hashing (Kriegel and Seeger)
> Extended k-d Tree (Matsuyama)
> R+ Tree (Stonebraker)
> Cell Tree (Günther)
> Multilayer Grid File (Six and Widmayer)
> R-File (Hutflesz)
>
> I think that k-d trees and k-d-B trees are the easiest to understand,
> the latter being a blend of the former and B-trees.
>
> Regards.
>
> José Juan Mendoza Rodríguez
>
> let me=josejuanmr in
> let privacy=lycos in
> let net=es in
> me@privacy.net

First, it is unclear what kind of queries did OP have in mind. But, anyhow,
I fail to see how multidimensional methods can be relevant to his problem.
Multidimensional query in its simplistic form is finding a list of intervals
that cover a given point

select x,y from intervals where x < 5 and 5 < y

OP, however, has a relation with each column from different domain (e.g.
name, age, ...). Am I missing something?

Relevant Pages

  • Re: Locality of allocations
    ... of more cpu cycles to avoid paging. ... do some simple data compression on these (are they mostly ... Is this tree used for searching? ...
    (comp.os.linux.development.apps)
  • Re: How long would it take a computer to completely "solve" chess?
    ... >> a rook against a king, search one ply farther to rule out stalemate ... >> and stop searching that branch. ... the tree will get to the same position (with same ... A position that has a known algorithm for winning. ...
    (sci.math)
  • Re: Data structure for indexing on multiple keys.
    ... >> Please note that this is not about composite keys but supporting ... >>multiple keys for searching. ... > k-d Tree ... > P-Tree ...
    (comp.programming)
  • Re: Data structure for indexing on multiple keys.
    ... >> Please note that this is not about composite keys but supporting ... >>multiple keys for searching. ... > k-d Tree ... > P-Tree ...
    (comp.theory)
  • Searching a treeview control
    ... My problem is in searching the tree. ... hChild = TreeView_GetChild(hWnd, hCurrent); ... returnPtr = FindTreeNode(winDlg, idCtl, hChild, nodeText); ...
    (microsoft.public.win32.programmer.ui)