Method for merging multiple ranked lists with bounded memory

• US 20060190425A1
• Filed: 02/24/2005
• Published: 08/24/2006
• Est. Priority Date: 02/24/2005
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Natsev, Apostol Ivanov, Padmanabhan, Sriram K., Chang, Yuan-Chi, Wang, Min, Lang, Christian Alexander, Stanoi, Ioana Roxana
• Application Number:
  US11/064,605
• Publication Number:
  US 20060190425A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: G06F 16/5838 using colour

Abstract

Systems and methods for conducting attribute-based queries over a plurality of objects using bounded memory locations and minimizing costly input and output operations are provided. A plurality of attributes are associated with each object, and a plurality of data groups, one each for the identified attributes are created. The objects associated with the attributes are placed into the appropriate data groups, and the objects contained within each data group are sorted into blocks such that each block within a given attribute contains that objects having the same attribute value. Results to the query are created by loading blocks into a primary memory location in a middleware system and combining the loaded blocks to create the desire query results. Block combinations are created based upon the fit of the given block combination to the query as expressed in an aggregation function. A second dedicated memory location can also be provided to hold multiple block combinations to optimize the order in which blocks are loaded and combined. Empty block buffers and external storage devices can also be provided to further enhance the generation of query results.

Claims

1. A method for conducting an attribute-based query over objects, the method comprising:

identifying a plurality of objects, each object having one or more associated attributes;

creating a data group for each attribute, each data group comprising a list of objects;

sorting the objects in each data group into a plurality of blocks, each block within a given data group comprising objects having a same value for that attribute; and

using the blocks to generate results to an attribute-based query over the plurality of objects.

2. The method of claim 1, wherein the step of creating data groups comprises creating at least one data group for each attribute.

3. The method of claim 1, wherein the attribute-based query comprises an identification of desired attribute values and the step of using the blocks to generate results comprises:

defining a plurality of combinations of blocks, each combination yielding a plurality of resulting objects;

ranking each combination in accordance with a variance between the desired attribute values and attributes associated with the resulting objects such that the lower the variance the higher the rank; and

selecting a highest ranked combination.

4. The method of claim 3, further comprising:

placing blocks associated with the selected highest ranked combination in a primary memory location of pre-determined size; and

joining the associated blocks placed in the primary memory location in accordance with the selected combination to yield the resulting objects.

5. The method of claim 4, wherein the step of placing the blocks in the memory location comprises loading blocks into the primary memory location from the data groups, swapping blocks from the primary memory location to an external memory device, moving blocks to an empty block buffer, discarding blocks from the memory location or combinations thereof.

6. The method of claim 3, wherein the step of selecting the highest ranked combination further comprises:

identifying a plurality of potential combinations having an equivalent highest rank; and

selecting one of the plurality of potential combinations such that the number of input and output operations required to yield the resulting objects are minimized.

7. The method of claim 6, wherein the step of identifying a plurality of potential combinations comprises identifying a pre-determined number of combinations.

8. The method of claim 7, further comprising maintaining blocks associated with the pre-determined number of potential combinations in a secondary dedicated memory location.

9. The method of claim 4, wherein the step of placing blocks in the primary memory location comprises for each block placing an identification of a current block in the selected combination and an identification of blocks in each attribute that have not yet been accessed.

10. The method of claim 6, further comprising identifying subcombinations of blocks common to two or more combinations in the plurality of potential combinations and placing the subcombinations in the primary memory location.

11. The method of claim 3, further comprising providing complete attribute ordering information with the query.

12. A computer readable medium containing a computer executable code that when read by a computer causes the computer to perform a method for conducting an attribute-based query over objects, the method comprising:

identifying a plurality of objects, each object having one or more associated attributes;

creating a data group for each attribute, each data group comprising a list of objects;

sorting the objects in each data group into a plurality of blocks, each block within a given data group comprising objects having a same value for that attribute; and

using the blocks to generate results to an attribute-based query over the plurality of objects.

13. The computer readable medium of claim 12, wherein the step of creating data groups comprises creating at least one data group for each attribute.

14. The computer readable medium of claim 12, wherein the attribute-based query comprises an identification of desired attribute values and the step of using the blocks to generate results comprises:

defining a plurality of combinations of blocks, each combination yielding a plurality of resulting objects;

ranking each combination in accordance with a variance between the desired attribute values and attributes associated with the resulting objects such that the lower the variance the higher the rank; and

selecting a highest ranked combination.

15. The computer readable medium of claim 14, further comprising:

placing blocks associated with the selected highest ranked combination in a primary memory location of pre-determined size; and

joining the associated blocks placed in the primary memory location in accordance with the selected combination to yield the resulting objects.

16. The computer readable medium of claim 15, wherein the step of placing the blocks in the memory location comprises loading blocks into the primary memory location from the data groups, swapping blocks from the primary memory location to an external memory device, moving blocks to an empty block buffer, discarding blocks from the memory location or combinations thereof.

17. The computer readable medium of claim 14, wherein the step of selecting the highest ranked combination further comprises:

identifying a plurality of potential combinations having an equivalent highest rank; and

selecting one of the plurality of potential combinations such that the number of input and output operations required to yield the resulting objects are minimized.

18. The computer readable medium of claim 17, wherein the step of identifying a plurality of potential combinations comprises identifying a pre-determined number of combinations.

19. The computer readable medium of claim 18, further comprising maintaining the blocks associated with the pre-determined number of potential combinations in a secondary dedicated memory location.

20. The computer readable medium of claim 15, wherein the step of placing blocks in the primary memory location comprises for each block placing an identification of a current block in the selected combination and an identification of blocks in each attribute that have not yet been accessed