Reducing index size for multi-level grid indexes

Details Reducing index size for multi-level grid indexes Reducing index size for multi-level grid indexes

2008-05-27

2008-05-27

Woo, Isaac (Department: 2166)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

07379944

ABSTRACT:
The number of index entries in a grid index for indexing geometric shapes is reduced by establishing a pool storage area for geometric shapes, selecting a threshold number of grid cells which a geometric shape may overlap, storing the shape in the grid index if a geometric shape overlaps a number of grid cells not exceeding the threshold number, and storing the shape in the pool storage area if the geometric shape overlaps a number of grid cells which exceeds the threshold number.

REFERENCES:
patent: 5745899 (1998-04-01), Burrows
patent: 5781899 (1998-07-01), Hirata
patent: 5832475 (1998-11-01), Agrawal et al.
patent: 5845277 (1998-12-01), Pfeil et al.
patent: 5895467 (1999-04-01), Ubell et al.
patent: 5963956 (1999-10-01), Smartt
patent: 6014614 (2000-01-01), Herring et al.
patent: 6021409 (2000-02-01), Burrows
patent: 6038258 (2000-03-01), Chun et al.
patent: 6101492 (2000-08-01), Jacquemin et al.
patent: 6122628 (2000-09-01), Castelli et al.
patent: 6134541 (2000-10-01), Castelli et al.
patent: 6154748 (2000-11-01), Gupta et al.
patent: 6195659 (2001-02-01), Hyatt
patent: 6201884 (2001-03-01), Van Bemmel et al.
patent: 6219662 (2001-04-01), Fuh et al.
patent: 6223182 (2001-04-01), Agarwal et al.
patent: 6233571 (2001-05-01), Egger et al.
patent: 6253196 (2001-06-01), Fuh et al.
patent: 6266663 (2001-07-01), Fuh et al.
patent: 6308177 (2001-10-01), Israni et al.
patent: 6338056 (2002-01-01), Dessloch et al.
patent: 6353832 (2002-03-01), Acharya et al.
patent: 6439783 (2002-08-01), Antoshenkov
patent: 6460026 (2002-10-01), Pasumansky
patent: 6484179 (2002-11-01), Roccaforte
patent: 6505205 (2003-01-01), Kothuri et al.
patent: 6510435 (2003-01-01), Bayer
patent: 6611609 (2003-08-01), Zhu
patent: 6636849 (2003-10-01), Tang et al.
patent: 6636870 (2003-10-01), Roccaforte
patent: 6687701 (2004-02-01), Karamanolis et al.
patent: 6700574 (2004-03-01), Song
patent: 6711563 (2004-03-01), Koskas
patent: 6732120 (2004-05-01), Du
patent: 6778996 (2004-08-01), Roccaforte
patent: 6831668 (2004-12-01), Cras et al.
patent: 6915289 (2005-07-01), Malloy et al.
patent: 6959304 (2005-10-01), Teig et al.
patent: 7016911 (2006-03-01), Bousfield et al.
patent: 7197500 (2007-03-01), Israni et al.
patent: 2002/0035432 (2002-03-01), Kubica et al.
patent: 2002/0095421 (2002-07-01), Koskas
patent: 2002/0129032 (2002-09-01), Bakalash et al.
patent: 2002/0156779 (2002-10-01), Elliot et al.
patent: 2002/0184187 (2002-12-01), Bakalash et al.
patent: 2002/0188581 (2002-12-01), Fortin et al.
patent: 2003/0126143 (2003-07-01), Roussopoulos et al.
patent: 2003/0187867 (2003-10-01), Smartt
patent: 2004/0019581 (2004-01-01), Davis, II et al.
patent: 2004/0036688 (2004-02-01), Cutlip
patent: 2004/0117358 (2004-06-01), von Kaenel et al.
patent: 2004/0225665 (2004-11-01), Toyama et al.
patent: 2005/0137994 (2005-06-01), Fortin et al.
patent: 2006/0129529 (2006-06-01), Adler
patent: WO 01/33395 (2000-10-01), None
Chen, Y., et al. U.S. Appl. No. 10/144,058 entitled “Systems, Methods and Computer Program Products to Improve Indexing of Multidimensional Databases,” filed on May 10, 2002. Assignee International Business Machines Corporation.
Chen, Y., et al. U.S. Appl. No. 10/144,389, filed May 10, 2002, entitledSystems, Methods, and Computer Program Products to Reduce Computer Processing in Grid Cell Size Determination for Indexing of Multidimensional Databases. Assignee International Business Machines Corporation.
Adler, D.W., et al. U.S. Appl. No. 10/792,446, filed Mar. 21, 2004, entitled “Index Exploitation for Spatial Data.” Assignee International Business Machines Corporation.
Aref, W., et al. Geoinformatica.Efficient Window Block Retrieval in Quadtree-Based Spatial Databases, Apr. 1997, pp. 1-37.
Shekhar, S. and S. Chawla.Spatial Databases. A Tour(Cover Page, Copyright Page, Table of Contents and pp. 96-100). New Jersey:Pearson Education, Inc., 2003.
Rigaux, P., et al.Spatial Databases with Application to GIS(Cover Page, Copyright page, Table of Contents and pp. 209-219). San Diego,CA:Academic Press, 2002.
IBM, Corp. “IBM® DB2®Spatial Extender. User's Guide and Reference, Version 7,” Second Edition, (Jun. 2001), 373 pages.
Gunther, O., “The Cell Tree, An Index for Geometric Databases,” Informatik Forschung und Entwicklung, vol. 4, No. 1, pp. 1-13, 1989, Abstract.
H. Samet,Spatial Data Structures, Modern Database Systems: The Object Model, Interoperability, and Beyond, W. Kim, ed., AddisonWesley/ACM Press, Reading, MA, 1995, 361-385.Computer Science Department and Institute of Advanced Computer Studies and Center for Automation Research, University of Maryland, College Park, MD 20742.
S. Acharya et al.,Selectivity Estimation in Spatial Databases, Proceedings of ACM SIGMOD Conference, Philadelphia, Jun. 1999, Information Sciences Research Center Bell Laboratories, Lucent Technologies, 600 Mountain Ave, Murray Hill, NJ, USA, 12 pages.
A. Aboulnaga, et al.,Accurate Estimation of the Cost of Spatial Selections, Computer Sciences Department University of Wisconsin—Madison.
B. Pagel, et al,Towards an Analysis of Range Query Performance in Spatial Data Structures, 8 pages.
V. Gaede,Multidimensional Access Methods, Volker Gaede Imperial College, London, UK and Oliver Gunther, Hunboldt-Universitat, Berlin, Germany.
Judith R. Davis,IBM's DB2 Spatial Extender: Managing Geo-Spatial Information within the DBMS, May 1998, pp. 1-23.
Philip S Yu, et al, “System and Method for Similarity Indexing and Searching in High Dimensional Space” US Patent Application, filed May 16, 2000, Assignee International Business Machines Corporation.
Storing and Manipulating Gridded Data in Databases, Barrodale Computing Services Ltd. (BCS), Victoria BC Canada V8W 3W2, http://www.barrodale.com/grid—Demo/gridInfo.pdf.
Sharing Geographic Knowledge,Moving from a single user database to multi-user ArcSDE and the Geodatabase, Session 1, ESRI 19thAnnual User Conference, http://www.esri.com/devsupport/devconn/sde/presentations/tw501.pdf.
Sharing Geographic Knowledge,ArcSDE Performance Tips, ESRI 19thAnnual User Conference, http://www.esri.com/devsupport/devconn/sde/presentations/tw502.pdf.
Harley, Mark,ArcSDE Tuning —Tips and Tradeoffs, http://gis.esri.com/library/userconf/proc01/professional/papers/pap869/p869.htm.
Mokbel, et al., “Irregularity in Multi-Dimensional Space-Filling Curves with Applications in Multimediia Databases,” CIKM '01, Nov. 5-10, 2001, Atlanta, GA; pp. 512-519.
Nievergelt, et al., “The Grid File: An Adaptable, Symmetric Multikey File Structure,” ACM Transactions on Database Systems, vol. 9, No. 1, Mar. 1984, pp. 38-71.
Adler, D., U.S. Appl. No. 10/792,446, filed Mar. 2, 2004; 52 pp. (KRV ref.: 56.23).
Hutflesz, A., H. Six, and P. Widmayer, “Twin Grid Files: Space Optimizing Access Schemes”, ACM SIGMOD Record, vol. 17, Iss. 3, 1988, pp. 183-190.

Affiliated with

Also associated with

Rating

Reducing index size for multi-level grid indexes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reducing index size for multi-level grid indexes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reducing index size for multi-level grid indexes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2769450