 |
|
|
|
|
|
 Title: |
US6408300:
Multidimensional indexing structure for use with linear optimization queries
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Bergman, Lawrence David; Mount Kisco, NY
Castelli, Vittorio; Croton on Hudson, NY
Chang, Yuan-Chi; White Plains, NY
Li, Chung-Sheng; Ossining, NY
Smith, John Richard; New Hyde Park, NY
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
2002-06-18
/ 1999-07-23
|
| Application Number: |
US1999000360366
|
| IPC Code: |
Advanced:
G06F 17/30;
Core:
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06F17/30S2P7;
|
| U.S. Class: |
707/101;
707/004;
707/100;
709/202;
|
| Field of Search: |
707/001,2,3,4,100,102,101,5,7,10,501,533,202
709/202
|
| Government Interest: |
This invention was made with U.S. Government support under contract no. NCC5-305 awarded by the National Aeronautic and Space Administration (NASA). The U.S. Government may have certain rights in this invention.
|
| Priority Number: |
| 1999-07-23 |
US1999000360366 |
|
| Abstract: |
Linear optimization queries, which usually arise in various decision support and resource planning applications, are queries that retrieve top N data records (where N is an integer greater than zero) which satisfy a specific optimization criterion. The optimization criterion is to either maximize or minimize a linear equation. The coefficients of the linear equation are given at query time. Methods and apparatus are disclosed for constructing, maintaining and utilizing a multidimensional indexing structure of database records to improve the execution speed of linear optimization queries. Database records with numerical attributes are organized into a number of layers and each layer represents a geometric structure called convex hull. Such linear optimization queries are processed by searching from the outer-most layer of this multi-layer indexing structure inwards. At least one record per layer will satisfy the query criterion and the number of layers needed to be searched depends on the spatial distribution of records, the query-issued linear coefficients, and N, the number of records to be returned. When N is small compared to the total size of the database, answering the query typically requires searching only a small fraction of all relevant records, resulting in a tremendous speedup as compared to linearly scanning the entire dataset.
|
| Attorney, Agent or Firm: |
Tassinari, Jr., Robert P.Ryan, Mason & Lewis, LLP ;
|
| Primary / Asst. Examiners: |
Corrielus, Jean M.;
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Family: |
Show 5 known family members
|
First Claim:
Show all 15 claims |
What is claimed is:
1. A method of constructing an indexing structure for N input records associated with a database system, the method comprising the steps of:
- forming a first convex hull of the N input records, the first convex hull having vertices represented by M records wherein the M records are assigned to a first layer of the indexing structure; and
- forming a second convex hull of remaining N minus M records, the second convex hull having vertices represented by P records wherein the P records are assigned to a second layer of the indexing structure, wherein at least a portion of one of the layers is geometrically inside of another of the layers; and
- adding a new record to the existing index structure, wherein the adding step comprises the steps of:
- forming a first new convex hull of the records of the first layer and the new record;
- if the new record represents a vertex of the first new convex hull, updating the second layer by forming a second new convex hull of the remaining records; and
- if the new record does not represent a vertex of the first new convex hull, forming a third new convex hull of the records of the second layer and the new record.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 9 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G2001-356916
|
| Other References: |
P. K. Agarwal, L. Arge, J. Erickson, P. G. Franciosa, and J. S. Vitter, "Efficient Searching with Linear Constraints," Proceedings of ACM PODS, pp. 169-177, 1998.
J. Goldstein, R. Ramakrishnan, U. Shaft, and J. Yu, "Processing Queries by Linear Constraints," Proceedings of ACM PODS, pp. 257-267, 1997.
T. M. Chan, "Fixed-dimensional Linear Programming Queries Made Easy," Proceedings of the 12th ACM Symposium on Computational Geometry, pp. 284-290, 1996.
J. Matousek and O. Schwarzkopf, "Linear Optimization Queries," Proceedings of the 8th ACM Symposium on Computational Geometry, pp. 16-25, 1992.
R. Seidel, "Linear Programming and Convex Hulls Made Easy," Proceedings of the 6th ACM Symposium on Computational Geometry, pp. 211-215, 1990.
G. B. Dantzig, "The Geometry of Linear Programs," Chapter 7, Linear Programming and Extensions, Princeton University Press, Princeton, NJ, pp. 147-157, 1963.
S.C. Fang and S. Puthenpura, "Linear Optimization and Extensions: Theory and Algorithms," Prentice-Hall, Inc., Englewood Cliffs, NJ, pp. 14-25, 1993.
F.P. Preparata and M.I. Shamos, "Computational Geometry: An Introduction," Springer-Verlag, pp. 125-134, 1985.
Johns Hopkins University, A. Das, S. R. Lele, G. E. Glass, T. Shields, and J. A. Patz, "Spatial modeling of vector abundance using generalized linear mixed models: application to Lyme disease, pp. 1-30".
|
| Continuity Data: |
| Application Number | Filed | Notes |
|---|
|
|
US2002000047129 | 2002-01-15 | is a
division of |
|
>US1999000360366<
| 1999-07-23 |
(pending)
[presumed granted]
|
| |
US6408300 issued 2002-06-18 Multidimensional indexing structure for use with linear optimization queries
|
|
|
|
 Nominate this for the Gallery...
|
|
