Index exploitation for spatial data

• US 20050198008A1
• Filed: 03/02/2004
• Published: 09/08/2005
• Est. Priority Date: 03/02/2004
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Adler, David W.
• Application Number:
  US10/792,446
• Publication Number:
  US 20050198008A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries

Abstract

Provided is a technique for index exploitation. A spatial region query referencing a spatial region is received. The spatial region is divided into intervals. Search ranges are generated for each interval. An index scan is performed for each interval.

Claims

1. A method for index exploitation, comprising:

receiving a spatial region query referencing a spatial region;

dividing the spatial region into intervals;

generating search ranges for each interval; and

performing an index scan for each interval.

2. The method of claim 1, wherein a range-producer module is invoked one or more times to obtain a search range for each interval until the range-producer module returns a done indication.

3. The method of claim 2, wherein the range-producer module divides the spatial region into a number of intervals a first time that the range-producer module is invoked for the spatial region.

4. The method of claim 1, further comprising:

receiving the spatial region query at an index exploitation module; and

invoking, with the index exploitation module, a range-producer module, wherein the invocation identifies the spatial region, wherein the range-producer module is invoked one or more times until the range-producer module returns a done indication to generate the search ranges for each interval.

5. The method of claim 1, wherein each search range comprises values that define a rectangular region.

6. The method of claim 1, wherein the index scan is a B-tree index scan.

7. The method of claim 1, further comprising:

performing the index scan for each interval in parallel.

8. The method of claim 1, further comprising:

determining a number of intervals that the spatial region is to be divided into.

9. The method of claim 8, further comprising:

when the determined number of intervals exceeds a threshold,

generating a single search range for the spatial region; and

performing a single index scan for the spatial region using the search range.

10. The method of claim 1, wherein the spatial region query comprises a window query.

12. The article of manufacture of claim 11, wherein a range-producer module is invoked one or more times to obtain a search range for each interval until the range-producer module returns a done indication.

13. The article of manufacture of claim 12, wherein the range-producer module divides the spatial region into a number of intervals a first time that the range-producer module is invoked for the spatial region.

11. An article of manufacture including a program for index exploitation, wherein the program causes operations to be performed, the operations comprising:

receiving a spatial region query referencing a spatial region;

dividing the spatial region into intervals;

generating search ranges for each interval; and

performing an index scan for each interval.

14. The article of manufacture of claim 11, wherein the operations further comprise:

receiving the spatial region query at an index exploitation module; and

invoking, with the index exploitation module, a range-producer module, wherein the invocation identifies the spatial region, wherein the range-producer module is invoked one or more times until the range-producer module returns a done indication to generate the search ranges for each interval.

15. The article of manufacture of claim 11, wherein each search range comprises values that define a rectangular region.

16. The article of manufacture of claim 11, wherein the index scan is a B-tree index scan.

17. The article of manufacture of claim 11, wherein the operations further comprise:

performing the index scan for each interval in parallel.

18. The article of manufacture of claim 11, wherein the operations further comprise:

determining a number of intervals that the spatial region is to be divided into.

19. The article of manufacture of claim 18, wherein the operations further comprise:

when the determined number of intervals exceeds a threshold,

generating a single search range for the spatial region; and

performing a single index scan for the spatial region using the search range.

20. The computer system of claim 11, wherein the spatial region query comprises a window query.

21. A computer system having at least one program for index exploitation, comprising:

receiving a spatial region query referencing a spatial region;

dividing the spatial region into intervals;

generating search ranges for each interval; and

performing an index scan for each interval.

22. The computer system of claim 21, wherein a range-producer module is invoked one or more times to obtain a search range for each interval until the range-producer module returns a done indication.

23. The computer system of claim 22, wherein the range-producer module divides the spatial region into a number of intervals a first time that the range-producer module is invoked for the spatial region.

24. The computer system of claim 21, further comprising:

receiving the spatial region query at an index exploitation module; and

invoking, with the index exploitation module, a range-producer module, wherein the invocation identifies the spatial region, wherein the range-producer module is invoked one or more times until the range-producer module returns a done indication to generate the search ranges for each interval.

25. The computer system of claim 21, wherein each search range comprises values that define a rectangular region.

26. The computer system of claim 21, wherein the index scan is a B-tree index scan.

27. The computer system of claim 21, further comprising:

performing the index scan for each interval in parallel.

28. The computer system of claim 21, further comprising:

determining a number of intervals that the spatial region is to be divided into.

29. The computer system of claim 28, further comprising:

when the determined number of intervals exceeds a threshold,

generating a single search range for the spatial region; and

performing a single index scan for the spatial region using the search range.

30. The computer system of claim 21, wherein the spatial region query comprises a window query.