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-01-25

2010-11-16

Woo, Isaac M (Department: 2166)

Data processing: database and file management or data structures

Database design

Data structure types

C707S802000, C707S822000, C707S828000

Reexamination Certificate

active

07836082

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: 6549660 (2003-04-01), Lipson et al.
patent: 6611609 (2003-08-01), Zhu
patent: 6629102 (2003-09-01), Malloy et al.
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: 6922700 (2005-07-01), Aggarwal et al.
patent: 6959304 (2005-10-01), Teig et al.
patent: 7016911 (2006-03-01), Bousfield et al.
patent: 7143098 (2006-11-01), Chen et al.
patent: 7171427 (2007-01-01), Witkowski et al.
patent: 7177882 (2007-02-01), Xie et al.
patent: 7197500 (2007-03-01), Israni et al.
patent: 7379944 (2008-05-01), Adler et al.
patent: 7383275 (2008-06-01), Chen et al.
patent: 7389283 (2008-06-01), Adler
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), Elliott 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: 2005/0198008 (2005-09-01), Adler
patent: 2006/0036628 (2006-02-01), Adler et al.
patent: 2006/0041551 (2006-02-01), Adler et al.
patent: 2006/0106833 (2006-05-01), Chen et al.
patent: 2008/0021893 (2008-01-01), Bakalash et al.
patent: 2008/0052303 (2008-02-01), Adler et al.
patent: 2008/0133469 (2008-06-01), Chen et al.
patent: 2008/0162424 (2008-07-01), Adler
patent: 0133395 (2001-05-01), None
Aboulnaga et al., “Accurate Estimation of the Cost of Spatial Selections”' Proceedings of the IEEE International Conference on Data Engineering, 2000, pp. 123-134.
Acharya et al., “Selectivity Estimation in Spatial Databases”, Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, Jun. 1999, pp. 13-24.
Aref et al., “Efficient Window Block Retriveal in Quadtree-Based Spatial Databases”, Geolnformatica, vol. 1, Iss.1 Apr. 1997, pp. 59-91.
Barrodale Computing Services, Ltd. (BCS), “Storing and Manipulating Gridded Data in Databases”, 2002, 13 pp.
Davis, “IBM's DB2 Spatial Extender: Managing GEO-Spatial Information within the DBMS”, May 1998, 26 pp.
Gaede, “Multidimensional Access Methods”, ACM Computing Surveys (CSUR), vol. 30, Iss. 2, Jun. 1998, pp. 170-231.
Gunther, “Der Zellbaum: Ein Index fur geometrische Datenbanken (The Cell Tree: An Index for Geometric Databases)”, nformatik- Forschung und Entwicklung, vol. 4, 1989, 13 pp.
Harley, “ArcSDE Tuning Tips and Tradeoffs”, (online), (retrieved on Jul. 23, 2003), retrieved from the Internet at <URL:http//gis2.esri.com/library/userconf/proc01/professional/papers/pap869/p869.htm>, 17 pp.
Heidelberger, “Parallel Index Scan Using Fetch-And-Add in Multi-Processing”, Retrieved from the internet at <URL : http://www.ip.com/pubview/IPCOM000057711D.html>. Jun. 1, 1988, 3 pp.
Hutflesz et al. “Twin Grid Files: Space Optimizing Access Schemes”, 1988, 8 pp.
IBM Corporation, “IBM DB2 Spatial Extender User's Guide and Reference”, Version 7, Second Edition, Jun. 2001 373 pp.
Morkbel et al. “Irregularity in Multi-Dimensional Space-Filling Curves with Applications in Multimedia Databases”, Proceedings of the Tenth International Conference on Information and Knowledge Management, Nov. 2001, 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.
Pagel et al., “Towards an Analysis of Range Query Performance in Spatial Data Structures”, Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1993, pp. 214-221.
Raad, “ArcSDE Performance Tips”, Proceedings of the Nineteenth Annual ESRI User Conference, 1999, 58 pp.
Rigaux et al., “Spatial Databases with Application to GIS”, Morgan Kaufmann, 2002, pp. 209-219.
Samet, “Spatial Data Structures”, Modern Database Systems : The Object Model, Interoperability, and Beyond, Addison Wesley/ACM Press, 1995, pp. 361-385.
Shekhar et al. , “Spatial Databases a Tour”, Prentice-Hall, 2003, pp. 96-100.
Shipman, “Moving from a Single User Database to Multi-User ArcSDE and the Geodatabase (Session 1)”, Nineteenth Annual ESRI User Conference, 1999, 42 pp.
Ho, C.T., R. Agrawal, N. Megiddo, and R. Srikant, “Range Queries in OLAP Data Cubes”, vol. 26, No. 2 © Jun. 1997 ACM, pp. 73-88.
Rotem, D. and A. Segev, “Algorithms for Multidimensional Partitioning of Static Files”, IEEE Transactions on Software Engineering, vol. 13, No. 11, Nov. 1988, pp. 1700-1710.
Gaede, V., and O. Gunther, “Multidimensional Access Methods”, Imperial College, London, UK, pp. 1-43 (also published ACM Computing Surveys (CSUR), vol. 30, Iss. 2, Jun. 1998, pp. 170-231).
Gunther, O., “Der Zellbaum: Ein Index für geometrische Datenbanken [The Cell Tree: An Index for Geometric Databases]”, nformatik—Forschung und Entwicklung, vol. 4, 1989, Total 13 pp [ English Abstract on p. 1, col. 1, starting on line 28].

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-4244087