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

2006-11-28

2006-11-28

Corrielus, Jean M. (Department: 2162)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

07143098

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: 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
patent: 6122628 (2000-09-01), Castelli
patent: 6154748 (2000-11-01), Gupta et al.
patent: 6195659 (2001-02-01), Hyatt
patent: 6201884 (2001-03-01), Van Bemmel et al.
patent: 6223182 (2001-04-01), Agarwal 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: 6484179 (2002-11-01), Roccaforte
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: 6732120 (2004-05-01), Du
patent: 6778996 (2004-08-01), Roccaforte
patent: 6915289 (2005-07-01), Malloy et al.
patent: 6922700 (2005-07-01), Aggarwal et al.
patent: 7016911 (2006-03-01), Bousfield 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/0184187 (2002-12-01), Bakalash et al.
patent: 2003/0126143 (2003-07-01), Roussopoulos et al.
patent: 2003/0187867 (2003-10-01), Smartt
patent: 2003/0212689 (2003-11-01), Chen et al.
patent: 2004/0225665 (2004-11-01), Toyama et al.
patent: WO 01/33395 (2000-10-01), None
Adler, D.W., et al. U.S. Appl. No. 10/792,446, filed on 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 on 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 on 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.
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.
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.
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.
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, Humboldt-Universitat, Berlin, Germany.
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.
Mokbel, M.F. & W.G. Aref, “Irregularity in Multi-Dimensional Space-Fllling 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.

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