Patent US5504887A successfully refreshed from Google Patents.
US5504887A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Storage clustering and packing of objects on the basis of query workload ranking
Assignee: International Business Machines Corp
•
Filing: 1993-09-10
•
Granted: 1996-04-02
•
Expires: 2013-09-10
Abstract
Abstract An apparatus and method is disclosed for efficiently clustering program objects on a unit of storage in a secondary memory, e.g., a page of memory on a disc. The objects are clustered so that a set of queries (query set) can access the stored objects with a minimum number of page transfers from secondary storage to main memory. To determine how the objects are clustered together on each memory page, queries in the query set and the objects that they access are identified. The queries are ranked by a number of factors including the query weight, the memory space required to store objects accessed by a query, and the number of objects a query has in common with other queries. The objects accessed by the query set are clustered on secondary memory pages according to the query ranking. Partially packed memory pages can be combined to minimize the cost of the query set accessing the stored objects.
Inventors
- 👤 Ashok Malhotra
- 👤 Kenneth J. Perry
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 13:04
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/35; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/2454; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99956
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
214 words
A method of clustering, on one or more pages of secondary memory of a computer, an object set of a plurality of objects accessed by a query set of a plurality of queries, comprising the steps of: identifying each query in the query set and a subset of objects that each query accesses from the secondary memory; identifying the objects in the object set as being all of the objects contained by all the subsets of objects accessed by all of the queries in the query set; ranking each of the queries in the query set according to a query weight, the query weight being determined by a product of a number of times one application program runs on the computer with a number of times the query occurs in the application program, the product summed over a plurality of application programs capable of running on the computer; selecting a selected query from the query set according to the rank of the selected query; and packing the objects in a selected subset of objects on a page of one or more secondary memory pages if all of the objects in the selected subset of objects fit on the page, the selected subset of object being the subset of objects that the selected query accesses.
Claim 2
Independent Claim
214 words
A method of clustering, on one or more pages of secondary memory of a computer, an object set of a plurality of objects accessed by a query set of a plurality of queries, comprising the steps of: identifying each query in the query set and a subset of objects that each query accesses from the secondary memory; identifying the objects in the object set as being all of the objects contained by all the subsets of objects accessed by all of the queries in the query set; ranking each of the queries in the query set according to a query weight, the query weight being determined by a product of a number of times one application program runs on the computer with a number of times the query occurs in the application program, the product summed over a plurality of application programs capable of running on the computer; selecting a selected query from the query set according to the rank of the selected query; and packing the objects in a selected subset of objects on a page of one or more secondary memory pages if all of the objects in the selected subset of objects fit on the page, the selected subset of object being the subset of objects that the selected query accesses.
Claim 3
Dependent Claim
46 words
A method of clustering objects, as in claim 1, where the queries in the query set are ranked also by a space requirement for the subset of objects accessed by the query, with objects taking less space tending to be clustered before objects taking more space.
Claim 4
Dependent Claim
59 words
A method of clustering objects, as in claim 1, where the queries in the query set are ranked also by the number of objects that a query has in common with other queries in the query set, with objects being accessed by a fewer number of queries being cluster before objects being accessed by a greater number of queries.
Claim 5
Dependent Claim
44 words
A method of clustering objects, as in claim 1, where the queries in the query set are ranked also by a secondary memory page storage space requirement for the objects accessed by a query, and the number of queries that access a common object.
Claim 6
Dependent Claim
44 words
A method of clustering objects, as in claim 1, comprising the additional step of combining a pair of secondary memory pages that are partially filled with objects in order to reduce a query set cost of accessing the objects stored in the secondary memory.
Claim 7
Dependent Claim
32 words
A method of clustering objects, as in claim 5, where the step of combining a pair of partially filled pages is repeated until the query set cost can no longer be reduced.
Claim 8
Dependent Claim
79 words
A method of clustering objects, as in claim 1, where the the queries in the query set are ranked also by an intersection weight, the intersection weight for an intersected query being the sum of one or more pair intersection weights of the intersected query, each pair intersection weight being the query weight of one of the queries that has objects in common with the intersected query, the intersected query being one of the queries in the query set.
Claim 9
Dependent Claim
225 words
A computer apparatus with an object set of a plurality of objects stored on one or more pages of a secondary memory and a query set for querying the stored objects through a user interface, the objects being packed on the pages of memory according to the following method: identifying each query in the query set and a subset of objects that each query accesses from the secondary memory; identifying the objects in the object set as being all of the objects contained by all the subsets of objects accessed by all of the queries in the set; ranking each of the queries in the query set according to a query weight, the query weight being determined by a product of a number of times one application program runs on the computer with a number of times the query occurs in the application program, the product summed over a plurality of application programs capable of running on the computer; selecting a selected query from the query set according to the rank of the selected query; and packing the objects in a selected subset of objects on a page of one or more secondary memory pages if all of the objects in the selected subset of objects fit on the page, the selected subset of object being the subset of objects that the selected query accesses.
Claim 10
Dependent Claim
225 words
A computer apparatus with an object set of a plurality of objects stored on one or more pages of a secondary memory and a query set for querying the stored objects through a user interface, the objects being packed on the pages of memory according to the following method: identifying each query in the query set and a subset of objects that each query accesses from the secondary memory; identifying the objects in the object set as being all of the objects contained by all the subsets of objects accessed by all of the queries in the set; ranking each of the queries in the query set according to a query weight, the query weight being determined by a product of a number of times one application program runs on the computer with a number of times the query occurs in the application program, the product summed over a plurality of application programs capable of running on the computer; selecting a selected query from the query set according to the rank of the selected query; and packing the objects in a selected subset of objects on a page of one or more secondary memory pages if all of the objects in the selected subset of objects fit on the page, the selected subset of object being the subset of objects that the selected query accesses.
References Cited (Backward Citations)
US4774657A
Cited
US4935876A
Cited
US4965743A
Cited
US4989132A
Cited
US5263159A
Cited
US5157765A
Cited
US5181162A
Cited
US5276867A
Cited
US5075845A
Cited
US5075842A
Cited
US5103498A
Cited
US5321833A
Cited
US5313631A
Cited
US5379422A
Cited
US5404510A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-04-02 | 1999-10-02 | 2000-04-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-04-02 | 2003-10-02 | 2004-04-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-04-02 | 2007-10-02 | 2008-04-02 | $7700.00 | Window Closed / Lapsed |