 |
|
|
|
|
|
 Title: |
US6529916:
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: |
2003-03-04
/ 2002-01-15
|
| Application Number: |
US2002000047129
|
| IPC Code: |
Advanced:
G06F 17/30;
Core:
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06F17/30S2P7;
|
| U.S. Class: |
Current:
707/104.1;
707/004;
707/100;
707/101;
Original:
707/104;
707/100;
707/101;
707/004;
|
| Field of Search: |
707/100,101,4,3,2,104,1
709/202
|
| Priority Number: |
|
| 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: |
Taisa, TanekazuRyan, Mason & Lewis, LLP ;
|
| Primary / Asst. Examiners: |
Corrielus, Jean M.;
|
| INPADOC Legal Status: |
None
Family Legal Status Report
|
|
|
|
|
|
|
| Parent Case: |
CROSS REFERENCE TO RELATED APPLICATION
This application is a division of pending U.S. application Ser. No. 09/360,366, now U.S. Pat. No. 6,408,306, filed Jul. 23, 1999, which is hereby incorporated herein by reference.
|
| 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 the 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.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 3 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G2001-356916
|
| Other References: |
Lee et al, "Mire: A multidimensional information retrieval engine for structure data and text", IEEE, 2002, pp. 1-6.*
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".
P. K. Agarwal, L. Arge, J. Erickson, P. G. Franciosa, and J. S. Vitter, "Efficient Searching with Linear Constraints," Proceeedings 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 ofLinear 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.
|
| 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...
|
|
