Systems, methods, and computer program products to reduce...

Details Systems, methods, and computer program products to reduce... Systems, methods, and computer program products to reduce...

2005-10-20

2008-10-14

Fleurantin, Jean Bolte (Department: 2162)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

07437372

ABSTRACT:
Systems, methods, and computer products that improve the techniques used to search multidimensional databases over techniques of the past. The preferred embodiment of the present invention advantageously improves the technique of determining a grid index that is used to locate a geometric shape in a spatial database. More particularly, the preferred embodiment of the present invention improves the technique of sampling data for defining the grid cell size in a grid for a given data set, thereby improving the grid indexing process that locates a particular minimum-bounding rectangle and the associated geometric shape.

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: 6922700 (2005-07-01), Aggarwal 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), 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: 2003/0212650 (2003-11-01), Adler et al.
patent: 2003/0212689 (2003-11-01), Chen et al.
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/0129529 (2006-06-01), Adler
patent: 01/33395 (2001-05-01), None
“Algorithms for multidimensional partitioning of static files” Rotem, D. and Segev, A.—Software Engineering, IEEE Transactions on, vol. 14, Issue 11, Nov. 1998, pp. 1700-1710.
“Range queries in OLAP data cubes” Ching-Tien Ho, Rakesh Agrawal, Nimrod Megiddo and Ramakrishnan Srikant—ACM SIGMOD Record—vol. 26, Issue 2, Jun. 1997, pp. 73-88.
H. Samet,Spatial Data Structures, Modern Database Systems: The Object Model, Interoperability, and Beyond, W. Kim, ed., Addison Wesley/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.
Judith R. Davis,IBM's DB2 Spatial Extender: Managing Geo-Spatial Information within the DBMS, May 1998, pp. 1-23.
Gunther, O., “The Cell Tree, An Index for Geometric Databases,” Informatik Forschung und Entwicklung, vol. 4, No. 1, pp. 1-13, 1989, Abstract.
Philip S Yu, et al, “System and Method for Similarity Indexing and Searching in High Dimensional Space” U.S. Appl. No. 09/571,471, filed May 16, 2000, 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.
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 May 10, 2002. Assignee International Business Machines Corporation.
Adler, D., et al. U.S. Appl. No. 10/141,919 entitled “Reducing Index Size for Multi-Level Grid Indexes,” filed May 10, 2002. 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.
Mokbel, M.F. & W.G. Aref, “Irregularity in Multi-Dimensional Space-Filling Curves with Applications in Multimedia Databases”,Proceedings of the Tenth International Conference on Information and Knowledge Management, 2001, pp. 512-519.
Nievergelt, J., H. Hinterberger, & K.C. Sevcik, “The Grid File: An Adaptable, Symmetric Multikey File Structure”,ACM Transactions on Database Systems, vol. 9, No. 1, Mar. 1984, pp. 38-71.
Aboulnaga, A., and J.F. Naughton, “Accurate Estimation of the Cost of Spatial Selections”, Proceedings of the IEEE International Conference on Data Engineering, 2000, pp. 123-134.
Acharya S., V. Poosala, and S. Ramaswamy, “Selectivity Estimation in Spatial Databases”, Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, Jun. 1999, pp. 13-24.
Aref, W.G., and H. Samet, “Efficient Window Block Retrieval in Quadtree-Based Spatial Databases”, GeoInformatica, 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, J.R., “IBM's DB2 Spatial Extender: Managing Geo-Spatial Information Within the DBMS”, May 1998, 26 pp.
Gaede, V., and O. Gunther, “Multidimensional Access Methods”, 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, 13 pp.
Harley, M., “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, P., A. Nigam, and J.T. Robinson, “Parallel Index Scan Using Fetch-And-Add in Multi-Processing”, IBM TDB 06-88, Jun. 1, 1988, 3 pp.
Hutflesz, A., H. Six, and P. Widmayer, “Twin Grid Files: Space Optimizing Access Schemes”

Affiliated with

Also associated with

Rating

Systems, methods, and computer program products to reduce... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Systems, methods, and computer program products to reduce..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems, methods, and computer program products to reduce... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4014089