Compression scheme for improving cache behavior in database...

Details Compression scheme for improving cache behavior in database... Compression scheme for improving cache behavior in database...

2007-10-16

2007-10-16

Wong, Don (Department: 2163)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

10087360

ABSTRACT:
A cache-conscious version of the R-tree, called the CR-tree, is disclosed. To pack more entries in a node, the CR-tree compresses MBR keys, which occupy substantial part of the index data. It first represents the coordinates of an MBR key relatively to the lower left corner of its parent MBR to eliminate the leading 0's from the relative coordinate representation. Then, it quantizes the relative coordinates with a fixed number of bits to further cut off the trailing less significant bits. Consequently, the CR-tree becomes significantly wider and smaller than the ordinary R-tree. The experimental and analytical results show that the two-dimensional CR-tree performs search faster than the ordinary R-tree while maintaining similar update performance and consuming less memory space.

REFERENCES:
patent: 6134541 (2000-10-01), Castelli et al.
patent: 6252605 (2001-06-01), Beesley et al.
patent: 6470344 (2002-10-01), Kothuri et al.
patent: 6601062 (2003-07-01), Deshpande et al.
patent: 6654760 (2003-11-01), Baskins et al.
patent: 6671694 (2003-12-01), Baskins et al.
patent: 6868410 (2005-03-01), Fortin et al.
patent: 7072891 (2006-07-01), Lee et al.
patent: 7080065 (2006-07-01), Kothuri et al.
patent: 2004/0119611 (2004-06-01), Oh et al.
“Compacting Discriminator Information for Spatial Trees” by Inga Sitzmann and Peter J. Stuckey, Copyright 2001, Australian Computer Society, Inc.

Affiliated with

Also associated with

Rating

Compression scheme for improving cache behavior in database... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Compression scheme for improving cache behavior in database..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression scheme for improving cache behavior in database... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3884347