C-tree for multi-attribute indexing

Details C-tree for multi-attribute indexing C-tree for multi-attribute indexing

2004-07-15

2010-02-23

Vital, Pierre M (Department: 2156)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

07668845

ABSTRACT:
An abstract indexing structure called a C-tree that it is an access method that exploits search space “containment” is described. The C-tree structure includes objects spaces that overlap, but search spaces that are disjoint. Every part of the search space is indexed by some node. Moreover, every object has a unique location in the index, despite the object space overlap. The C-tree is a tree of pages, typically disk based, like a B-tree, but it handles a greater variety of data, e.g., spatial data, temporal data, etc. In particular, it can handle the indexing of objects that have extents, not merely point data, and hence objects that can overlap. These objects can be indexed without remapping them to a higher dimensional point space. At least one particular aspect of the invention is premised on a notion of an object being contained in some kind of search space.

REFERENCES:
patent: 5446887 (1995-08-01), Berkowitz
patent: 5752243 (1998-05-01), Reiter et al.
patent: 5761652 (1998-06-01), Wu et al.
patent: 5781906 (1998-07-01), Aggarwal et al.
patent: 5799301 (1998-08-01), Castelli et al.
patent: 5806065 (1998-09-01), Lomet
patent: 5968109 (1999-10-01), Israni et al.
patent: 6047280 (2000-04-01), Ashby et al.
patent: 6122628 (2000-09-01), Castelli et al.
patent: 6134541 (2000-10-01), Castelli et al.
patent: 6219662 (2001-04-01), Fuh et al.
patent: 6252605 (2001-06-01), Beesley et al.
patent: 6263334 (2001-07-01), Fayyad et al.
patent: 6282605 (2001-08-01), Moore
patent: 6381605 (2002-04-01), Kothuri et al.
patent: 6470344 (2002-10-01), Kothuri et al.
patent: 6505205 (2003-01-01), Kothuri et al.
patent: 6694323 (2004-02-01), Bumbulis
patent: 7167856 (2007-01-01), Lawder
patent: 2001/0042240 (2001-11-01), Ng et al.
patent: 2003/0187867 (2003-10-01), Smartt
patent: 2005/0198008 (2005-09-01), Adler
David Lomet, Replicated Indexes for Distributed Data, International Conference on Parallel and Distributed Information Systems, 1996, 12 pages.
David Lomet, Simple, Robust, and Highly Concurrent B-trees with Node Deletion, ICDE Conference, Mar. 30-Apr. 2, 2004, pp. 18-28, Boston, MA.
David B. Lomet, MLR: A Recovery Method for Multi-level systems, ACM SIGMOD, Jun. 1992, pp. 185-194, ACM.
David Lomet, et al., Access Method Concurrency with Recovery, ACM SIGMOD, Jun. 1992, pp. 351-360, ACM.
Chengwen Liu, et al., Performance Evaluation of G-tree and Its Application in Fuzzy Databases, CIKM 96, 1996, pp. 235-242, ACM.
Ravi Kanth V Kothuri, et al., Quadtree and R-tree Indexes in Oracle Spatial: A Comparison Using GIS Data, ACM SIGMOD 2002, Jun. 2002, pp. 546-557, ACM.
Christian Bohm, et al., Searching in High-Dimensional Spaces—Index Structure for Improving the Performance of Multimedia Databases, ACM Computing Surveys, Sep. 2001, pp. 322-373. vol. 33, No. 3. ACM.
Volker Gaede, et al., Multidimensional Access Methods, ACM Computing Surveys, Jun. 1998, pp. 170-231, vol. 30, No. 2, ACM.
Michael Freeston, A General Solution of the n-dimensional B-tree Problem, SIGMOD '95, 1995, pp. 80-91, ACM.
David B. Lomet, et al., The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance, ACM Transactions on Database Systems, Dec. 1990, pp. 625-658, vol. 15 No. 4. ACM.
David Lomet, et al., Concurrency and Recovery for Index Trees, The VLDB Journal, 1997, pp. 224-240, vol. 6, Springer-Verlag.
Georgios Evangelidis, et al., The hBΛ(II) -tree: A Multi-attribute Index Supporting Concurrency, Recovery, and Node Consolidation, The VLDB Journal, 1997, pp. 1-25, vol. 6, Springer-Verlag.
R. Bayer, et al., Organization and Maintenance of Large Ordered Indexes, Acta Informatica, 1972, pp. 173-189, vol. 1.
N. Beckmann, et al., The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles, SIGMOD Conference, 1990, pp. 322-331.
A. Guttman, R-trees: A Dynamic Index Structure for Spatial Searching, SIGMOD, 1984, pp. 47-57.
J. Hellerstein, et al., Generalized Search Trees for Database Systems, VLDB, 1995, pp. 562-573.
I. Kamel, et al., Hilbert R-tree: An Improved R-tree Using Fractals, VLDB, 1994, pp. 500-509.
M. Kornacker, et al., Concurrency and Recovery in Generalized Search Trees, SIGMOD, 1997, pp. 62-72.
P. Lehman, et al., Efficient Locking for Concurrent Operations on B-trees, ACM TODS 6, 1981, pp. 650-670, vol. 4.
C. Mohan, et al., ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging, SIGMOD, 1992, pp. 371-380.
F. Ramsak, et al., Integrating the UB-Tree into a Database System Kernel, VLDB, 2000, pp. 263-272.
J. Robinson, The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes, SIGMOD Conference, 1981, pp. 10-18.
T. Sellis, et al., The R+− Tree: A Dynamic Index for Multi-Dimensional Objects, VLDB, 1987, pp. 507-518.
Yehoshua Sagiv, Concurrrent Operationa on B-Tree with Overtaking, 1985, pp. 28-37, ACM.

Affiliated with

Also associated with

Rating

C-tree for multi-attribute indexing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with C-tree for multi-attribute indexing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and C-tree for multi-attribute indexing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4166133