Fast computation of spatial queries in location-based services

• US 7,007,013 B2
• Filed: 07/26/2002
• Issued: 02/28/2006
• Est. Priority Date: 07/26/2002
• Status: Expired due to Term

• Current Assignee: Slingshot IOT LLC
• Original Assignee: International Business Machines Corporation
• Inventors: Davis, John Sidney II, Sow, Daby Mousse
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US10/207,683
• Publication Number:
  US 20040019581A1
• Time in Patent Office: 1,313 Days
• Field of Search: 707 2- 5, 707/100, 707103 R-103 Z, 707/104.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

This invention provides methods, systems and apparatus for performing fast computation of metric queries. To achieve this, in an example embodiment, the present invention segments metric regions into disjoint primitive atomic shapes. It then represents these primitive atomic shapes and then performs off-line computation of their relevant properties. As a result of the off-line computation, the execution of a query requires a minimal number of on-line calculations resulting in a very fast query. Further optimization occurs via storage of query histories and prioritization of queries with respect to the access frequency of a metric space'"'"'s primitive atomic shapes.

Claims

1. A method comprising:

preparing, in anticipation of a query related to a metric space, a representation of a region to be used in forming a response to said query, said method further including the steps of;

obtaining a mathematical format of said region within said metric space;

disaggregating said region into a set of atomic shapes; and

forming the representation of said region by preprocessing and storing at least one property for at least one of said atomic shapes.

2. A method as recited in claim 1, further comprising prioritizing said atomic shapes according to at least one prioritization criterion.

3. A method as recited in claim 2, wherein said at least one criterion includes a hit rate.

4. A method as recited in claim 2, wherein said prioritization criteria is taken from a group of prioritization criteria including hit rate and region complexity.

5. A method as recited in claim 1, wherein said query is a spatial query.

6. A method as recited in claim 1, further comprising transforming said mathematical format into a sequence of vertices.

7. A method as recited in claim 1, further comprising including in the mathematical format a group of numerical relationships between components of said region.

8. A method as recited in claim 1, wherein each of said atomic shapes is a shape included in a group of shapes including:

a circle;

a triangle;

a rectangle;

a cube, a pyramid, a sphere, and any combination of these.

9. A method as recited in claim 1, wherein the step of disaggregating includes employing a Delauney triangulation algorithm.

10. A method as recited in claim 1, wherein the step of preprocessing includes:

establishing and applying at least one reference coordinate system to said atomic shapes;

identifying at least one property of each of said atomic shapes; and

transforming said at least one property into a format consistent with said at least one reference coordinate system.

11. A method as recited in claim 10, wherein the atomic shapes are triangles and the step of preprocessing includes:

calculating an angle of rotation for each side of said triangles with respect to one reference coordinate system from said at least one reference coordinate system; and

transforming endpoints of each side of said triangle into said one reference coordinate system.

12. A method as recited in claim 11, wherein the step of transforming includes creating trigonometric coefficients of the angles of rotation for each side of said triangles with respect to said one reference coordinate system.

13. A method as recited in claim 1, wherein at least one of said atomic shapes is a circle, and the step of preprocessing includes calculating a center and radius of each circle.

14. A method as recited in claim 1, wherein said at least one property includes at least one static property.

15. A method as recited in claim 1, wherein said metric space includes regions with curved boundaries and regions with straight line boundaries, and wherein said atomic shapes include at least one atomic shape with a curved boundary and at least one atomic shape with a straight line boundary.

16. A method as recited in claim 1, further comprising forming a response to said query employing said representation.

17. A method as recited in claim 16, wherein the step of forming a response to said query employing said representation, includes:

computing for each atomic shape a rank;

forming said atomic shapes into an ordered list having a list order based on said rank of said each atomic shape; and

querying atomic shapes in the list order given in said ordered list.

18. A method as recited in claim 17, wherein said rank is based on at least one rank criterion wherein said rank criterion is taken from a group of criteria including:

hit rate, region complexity, and any combination of these.

19. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing representation of a region, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 1.

20. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for representation of a region, said method steps comprising the steps of claim 1.

21. A method comprising:

forming a representation of locations of a plurality of geographical regions disaggregated into atomic components;

preparing a response to a spatial query involving determination of whether a point location intersects one of said geographical regions; and

preparing a response to said spatial query involving determination of whether any of said geographical regions intersect.

22. A method as recited in claim 21, wherein the step of forming a representation of regions disaggregated into atomic components includes segregating computations into off-line and on-line computations.

23. A method as recited in claim 22, further comprising employing said off-line computations in capturing at least one property of said atomic components.

24. A method as recited in claim 23, further comprising forming the atomic components into triangles based on Delaunay triangulation such that orientation of triangular regions with respect to a fixed axis are calculated via off-line computation.

25. A method as recited in claim 24, further comprising storing triangular atomic components as three orientation angles and three line segments.

26. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing provision of a response to a metric query, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 21.

27. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for provision of a response to a metric query, said method steps comprising the steps of claim 21.

28. An apparatus comprising means to perform the steps of claim 21.

29. An apparatus comprising:

means for preparing a representation of a region in anticipation of a query related to a metric space, said representation being used in forming a response to said query;

means for obtaining a mathematical format of a region within said metric space;

means for disaggregating said region into a set of atomic shapes; and

means for forming the representation of said region by preprocessing and storing at least one property for at least one of said atomic shapes.

30. An apparatus as recited in claim 29, further comprising means for prioritizing said atomic shapes according to at least one criterion.

31. An apparatus as recited in claim 29, further comprising means for transforming said mathematical format into a sequence of vertices.

32. An apparatus as recited in claim 29, further comprising means for forming a response to said query employing said representation.

33. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a representation of a region, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 29.