Method and apparatus for populating an index table

• US 7,991,779 B1
• Filed: 04/25/2005
• Issued: 08/02/2011
• Est. Priority Date: 04/25/2005
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Drory, Tal, Peleg, Nitzan, Bar-Or, Amir
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): SMITH, GARRETT A
• Application Number:
  US11/114,681
• Time in Patent Office: 2,290 Days
• Field of Search: None
• US Class Current: 707/743
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A disclosed embodiment relates to a system for populating an index table. The system comprises a component that decomposes a spatial object into a set of object pairs, a component that employs a value associated with the object pairs to sort the set of object pairs into a sequence of object pairs, a component that uses a sliding border analysis to create a subset of the sequence of object pairs depending upon a position of the object pair in the sequence of object pairs, and a component that populates the index table with the subset of object pairs.

Claims

1. A system for populating an index table, comprising:

a memory;

a computer;

a component executable on the computer that decomposes a spatial object into a set of object pairs;

a component executable on the computer that employs values associated with the object pairs to sort the set of object pairs into a sequence of object pairs;

a component executable on the computer that uses a sliding border analysis to create a subset of the sequence of object pairs depending upon positions of the object pairs in the sequence relative to a sliding border defined by the sliding border analysis, wherein the object pairs in the subset are associated with positions on a first side of the sliding border, and wherein the sliding border analysis is to process the sequence of object pairs and to adjust a position of the sliding border according to the processing of the sequence of object pairs;

a component executable on the computer that stores, in the memory, object pairs associated with positions on a second, different side of the sliding border, and that removes, from the memory, object pairs associated with positions on the first side of the sliding border, wherein as the sliding border is adjusted additional object pairs are removed from the memory; and

a component executable on the computer that populates the index table with the subset of object pairs, wherein as the sliding border is adjusted according to the processing of the sequence of object pairs, additional object pairs are to be added to the subset that populates the index table.

2. The system set forth in claim 1, wherein the index table comprises a spatial index table.

3. The system set forth in claim 1, wherein the spatial object is decomposed using a given decomposition level.

4. The system set forth in claim 3, wherein the decomposition level comprises a mean level of a polygon map region (PMR) quadtree.

5. The system set forth in claim 1, wherein the set of object pairs is represented as a quadtree, wherein the sliding border divides the quadtree into a first part and a second part, wherein the subset of object pairs is in the first part of the quadtree, and wherein as the sliding border is adjusted according to processing of the sequence of object pairs, the first part of the quadtree is to grow in size.

6. The system set forth in claim 5, wherein the quadtree comprises a polygon map region (PMR) quadtree.

7. The system set forth in claim 1, wherein the set of object pairs is represented as a tile structure.

8. The system set forth in claim 7, wherein the tile structure comprises a sub-tile.

9. The system set forth in claim 5, wherein the system is configured to use a bounded portion of the memory to store the index table, wherein the bounded portion of the memory is for use to store the object pairs in the second part, and wherein the object pairs in the first part are to be removed from the memory for storing into the index table.

10. The system set forth in claim 1, wherein each object pair comprises a Zvalue and an object identification field.

11. The system set forth in claim 1, wherein the spatial object is derived from a base table.

12. A method of populating an index table, comprising:

decomposing, by a computer, at least one spatial object into a set of object pairs;

sorting, by the computer, the set of object pairs into a sequence of object pairs using values associated with the object pairs;

employing, by the computer, a sliding border algorithm to extract a subset of object pairs from the sequence of object pairs depending upon positions of the object pairs in the sequence relative to a sliding border defined by the sliding border algorithm;

receiving, by the computer, new object pairs of the sequence of object pairs;

moving, by the computer, the sliding border as the new object pairs of the sequence of object pairs are received, wherein as the sliding border is moved, additional object pairs associated with positions on a first side of the sliding border are added to the subset;

storing, in a memory, object pairs associated with positions on a second, different side of the sliding border, and removing, from the memory, object pairs associated with positions on the first side of the sliding border; and

populating, by the computer, the index table with the subset of object pairs, wherein the subset is defined by a current position of the sliding border.

13. The method set forth in claim 12, wherein the index table comprises a spatial index table.

14. The method set forth in claim 12, wherein the spatial object is decomposed relative to a decomposition level.

15. The method set forth in claim 14, wherein the decomposition level comprises a mean level of a polygon map region (PMR) quadtree.

16. The method of claim 12,

wherein as the sliding border is moved, additional object pairs are removed from the memory.

17. The method set forth in claim 16, wherein the set of object pairs is represented as a quadtree, wherein the sliding border divides the quadtree into a first part and a second part, wherein the first part includes the object pairs on the first side of the sliding border, and the second part includes the object pairs on the second side of the sliding border, and wherein as the sliding border moves, the first part of the quadtree grows in size.

18. The method set forth in claim 17, wherein the quadtree comprises a polygon map region (PMR) quadtree.

19. The method of claim 16, further comprising:

storing the object pairs removed from the memory into a persistent storage.

20. The method set forth in claim 12, wherein each of the object pairs comprises a Zvalue and an object identification field.

21. The method set forth in claim 12, wherein the recited acts are performed in the recited order.

22. A database system comprising a non-transitory computer-readable storage medium containing instructions that are executable by a computer, the instructions upon execution causing the computer to:

decompose a spatial object into a set of object pairs;

sort the set of object pairs into a sequence of object pairs using values associated with the object pairs;

create a subset of the sequence of object pairs via a sliding border algorithm depending upon positions of the object pairs in the sequence relative to a sliding border defined by the sliding border algorithm, wherein the sliding border algorithm processes the sequence of object pairs and adjusts a position of the sliding border according to the processing of the sequence of object pairs;

populate the index table with the subset of the sequence of object pairs, wherein as the sliding border is adjusted according to the processing of the sequence of object pairs, additional object pairs are added to the subset that populates the index table, wherein the index table is populated with the subset of object pairs associated with positions on a first side of the sliding border; and

store, in a memory, object pairs associated with positions on a second, different side of the sliding border, wherein the object pairs associated with positions on the first side of the sliding border are removed from the memory.

23. A system for populating a spatial index table, comprising:

a memory;

a computer;

a base table that contains a plurality of spatial objects;

a component executable by the computer that compares the plurality of spatial objects to a decomposition level to produce a comparison result for each of the plurality of spatial objects;

a component executable by the computer that employs the comparison result to decompose each of the plurality of spatial objects into an object pair that comprises a Zvalue and an object identification value;

a component executable by the computer that sorts the plurality of object pairs into a sequence using the Zvalue associated with the object pair and places each of the plurality of object pairs in a polygon map region (PMR) quadtree;

a component executable by the computer that uses a sliding border algorithm to analyze the PMR quadtree and create a subset of the plurality of object pairs depending upon a position in the PMR quadtree of each of the plurality of object pairs in relation to a sliding border of the sliding border algorithm, wherein the object pairs in the subset are associated with positions on a first side of the sliding border, and wherein the sliding border is to be moved by the sliding border algorithm according to processing of the sequence of object pairs;

a component executable by the computer that stores, in the memory, object pairs associated with positions on a second, different side of the sliding border, and that removes, from the memory, object pairs associated with positions on the first side of the sliding border, wherein as the sliding border is adjusted additional object pairs are removed from the memory; and

a component executable by the computer that populates the spatial index table with the subset of the plurality of object pairs, wherein as the sliding border is moved according to the processing of the sequence of object pairs, additional object pairs are to be added to the subset that populates the spatial index table.

24. The system set forth in claim 23, wherein the decomposition level comprises a mean level of the PMR quadtree.

25. The system set forth in claim 23, comprising a component that is executable to create a list of the subset of the plurality of object pairs prior to populating the spatial index table.

26. A non-transitory computer-usable medium storing instructions, which when executed by a computer, effect populating an index table, comprising:

decomposing at least one spatial object into a set of object pairs;

sorting the set of object pairs into a sequence of object pairs using values associated with the object pairs;

using a sliding border analysis to create a subset of the sequence of object pairs depending upon positions of the object pairs in the sequence relative to a sliding border defined by the sliding border analysis;

receiving new object pairs of the sequence;

moving the sliding border as the new object pairs of the sequence of object pairs are received, wherein as the sliding border is moved, additional object pairs are added to the subset;

populating the index table with the subset of the sequence of object pairs, wherein the subset is defined by a current position of the sliding border, wherein populating the index table with the subset of the sequence of object pairs comprises populating the index table with the subset of the sequence of object pairs associated with positions on a first side of the sliding border;

storing, in a memory, object pairs associated with positions on a second, different side of the sliding border; and

removing, from the memory, object pairs associated with positions on the first side of the sliding border, wherein as the sliding border is moved, additional object pairs are removed from the memory.