Source: http://www.google.com/patents/US20040019581?dq=6629163
Timestamp: 2014-12-25 17:24:43
Document Index: 610584291

Matched Legal Cases: ['arts 105', 'arts 205', 'arts 205', 'arts 305', 'arts 405', 'arts 605']

Patent US20040019581 - Fast computation of spatial queries in location-based services - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsThis 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...http://www.google.com/patents/US20040019581?utm_source=gb-gplus-sharePatent US20040019581 - Fast computation of spatial queries in location-based servicesAdvanced Patent SearchPublication numberUS20040019581 A1Publication typeApplicationApplication numberUS 10/207,683Publication dateJan 29, 2004Filing dateJul 26, 2002Priority dateJul 26, 2002Also published asUS7007013Publication number10207683, 207683, US 2004/0019581 A1, US 2004/019581 A1, US 20040019581 A1, US 20040019581A1, US 2004019581 A1, US 2004019581A1, US-A1-20040019581, US-A1-2004019581, US2004/0019581A1, US2004/019581A1, US20040019581 A1, US20040019581A1, US2004019581 A1, US2004019581A1InventorsJohn Davis, Daby SowOriginal AssigneeInternational Business Machines CorporationExport CitationBiBTeX, EndNote, RefManReferenced by (16), Classifications (11), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetFast computation of spatial queries in location-based servicesUS 20040019581 A1Abstract 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. Images(9) Claims(33)
DESCRIPTION OF THE INVENTION [0032] The present invention provides methods, systems and apparatus for fast computation of metric queries. Metric queries are generally computationally complex. This is due in part to irregularly shaped geographical regions. Consider a spatial query about Westchester County, New York. Even a poor approximation of the Westchester County boundaries requires a complex polygonal representation. Asking the �what is there?� question requires a system to compare the coordinates of an object with each boundary segment of the geographical region. Such comparisons can be very time consuming in a heavily used system. Just as it is important that web page requests occur quickly, a successful ubiquitous computing system will require minimal latency for metric queries. [0033] To reduce the latency of metric queries the associated computational steps are partitioned into two groups: off-line computations and on-line computations. Metric query latency is due only to on-line computation time as off-line computation occurs prior to the occurrence of a metric query. Our overall approach performs as much computation as possible off-line. The result is that the remaining on-line computation is minimized. To reduce latency further embodiments are described employing techniques for optimizing the on-line computation. [0034] An example embodiment of a method which achieves this, includes the following steps: [0035] 1. Segmentation of metric regions into disjoint primitive atomic shapes. [0036] 2. Representation and off-line computation of the relevant properties of each primitive atomic shape. [0037] 3. On-line computation of metric queries based on query history, by starting from the most queried atomic shapes. [0038] 4. Update of the query history for each atomic shape. [0039] As a result of this approach, metric query latency is due to on-line computation time as off-line computation occurs prior to the occurrence of a metric query. Our overall approach performs as much computation as possible off-line in steps 1 and 2. The result is that the remaining on-line computation is minimized. To reduce latency further, we store and use query history to order the queries performed on each atomic shape, as described in step 3 and 4. [0040] An example of an off-line computation algorithm is shown in FIG. 1. This algorithm starts 105 by receiving 110 an atomic shape that is to be processed as a container region. For a given set of atomic shapes, the algorithm selects 115 a single reference 2D coordinate system. It then transforms 120 the atomic shape's coordinates into equivalent coordinates in the reference 2D coordinate system. The algorithm then determines 125 the transformation equation with respect to the reference 2D coordinate system for determining if a point is included in the atomic shape. [0041] An example embodiment of an off-line computation in which atomic shapes are triangular shapes is shown in FIGS. 2 and 2a. This algorithm starts 205 by receiving 210 the triangular atomic shape that will be processed as the container region. The system gets 215 the reference 2D coordinate system and calculates 220 the length of each side of the triangular atomic shape. The algorithm determines 225 a side of the triangle that is less than or equal in length to the other two sides and labels this side the �shortest side.� The next step tests 230 if there are any unpicked sides of the triangular atomic shape. Unpicked sides are sides of the triangle for which a translation and rotation equation have not been generated. If there are unpicked sides left, the procedure picks 235 one such side from the triangle. The algorithm then creates 240 a local 2D coordinate system so that the X-axis aligns with the side and one end point of the origin. The algorithm then places 245 the Y-axis of the local coordinate system such that the local 2D coordinate the positive region intersects the interior of the triangle (see FIG. 2a for a further explanation of the step associated with 245). The algorithm then determines 250 the translation and rotation equations between this local coordinate system and the reference coordinate system. The algorithm then defines 255 the two interval comparison equations for this side. Once there are no unpicked sides the algorithm completes 260. [0042]FIG. 2a gives an algorithm for determining how to orient a local 2D coordinate system. The algorithm starts 205 a by receiving 210 a the side being processed, and the length of the shortest side of the triangle. The algorithm then arbitrarily picks 215 a one of the endpoints of the side being processed and designates this point the �origin point.� The next step designates 220 a the other endpoint of the side being processed as the �ray point.� The algorithm then designates 225 a the X-Axis of the local coordinate system so that it intersects the origin point and the ray point. The algorithm then orients 230 a the X-Axis such that the origin of the X-Axis is the origin point and such that the ray point falls in the positive region of the X-Axis. Next the algorithm designates 235 a the Y-Axis of the local coordinate system so that it intersects the origin point. The algorithm then considers the side of the triangle that is not being processed and that intersects the ray point and designates 240 a this side the �positive side.� Starting at the ray point, the algorithm measures 245 a a distance equal to the length of the shortest side along the positive side and designates the point at this measured length the �positive point.� Next the algorithm orients 250 a the Y-Axis such that the positive quadrant of the local coordinate system includes the positive point after which the algorithm is complete 255 a. [0043] An example of an on-line computation algorithm is shown in FIG. 3. This algorithm starts 305 by reading 310 a point X to be located in the atomic shapes obtained from the off-line algorithm described in FIG. 1. For all primitive shapes, the algorithm resets 315 the hit rate h and computes 320 their region complexity c. It then orders primitive shapes in a list L based on a metric that could depend on h and c. For example, a metric could place atomic shapes in L in a descending order of hit rate h. Another metric could place atomic shapes in L in a descending order of product he. The algorithm then checks 330 if the list L is empty or not. If L is not empty, it picks 340 the shape S on top of L and remove it from L. It tests 345 if the point X is in S by invoking the procedure described in FIG. 4. The steps in this procedure are described below. If X is in S, the algorithm updates 350 the hit rate h associated to S and then outputs 355 �X is in primitive shape S� with a description of S. It then ends the computation. If the procedure described in FIG. 4 replies that X is not in S, the algorithm goes back to step 330 where it tests whether L is empty or not. If L is not empty, it repeats steps 340 and 345. If L is empty, the algorithm outputs 335 �X is not in any primitive shape� before ending 360 its computation. [0044] As mentioned above, FIG. 4 describes a procedure that tests whether a given point X is inside a given primitive shape S for triangular primitive shapes. It starts 405 by reading 410 the coordinates of the point X. From the off-line process described in FIGS. 1 and 2, it receives 415 a complete description of the primitive shape S to query. It then sets 420 two counters �rcounter� and �scounter� to 1. The next step tests 425 if there are any unpicked sides of S. Unpicked sides are simply sides that the procedure has not used yet to generate a response to the query �Is X in S?�. If there are unpicked sides left, the procedure picks 430 a side and labels it �i_rcounter�, rcounter being the current value of the counter rcounter. It then finds 435 the square Q_rcounter corresponding to the picked side and tests 435 whether X is in Q_rcounter. The Boolean result of this tests is stored in E_rcounter. Testing whether X is in Q_rcounter involves a rotation and a translation. The off-line computation simplifies the translation and rotation because the properties (sine and cosine) of the angle involved in the rotation have already been computed ahead of time and expressed in the translation and rotation equation obtained in step 250, as described in FIG. 2. If i_rcounter is the longest side 440 of the triangle, the procedure re-labels 450 the results of the evaluation E_rcounter with E_longest and increments rcounter. If i_rcounter is not the longest side of the triangle, the algorithm re-labels 445 E_rcounter with E_scounter and increments both rcounter and scounter. From step 450 and 445, the algorithm goes back to step 425 where it checks if there are any unpicked sides left. If there are more unpicked sides left, it repeats steps 430, 435 and 440. If the test in step 425 indicates that there are no more unpicked sides left, the algorithm proceeds to step 455 where it evaluates the following Boolean formula: (E�1 AND E_longest) OR (E�2 AND E_longest). If this evaluation is true, the procedures returns true: X is in S. If the evaluation is false, the procedure returns false: X is not in S. FIG. 5 describes the rationality behind the proposed Boolean formula. It clearly shows that for a point X to be inside a primitive shape S 505, the proposed Boolean formula must return true. Furthermore, it will return true only for points X inside S. [0045] A further example embodiment of the present invention is shown in FIG. 6. The system starts 605 by receiving 610 coordinates of a container region prior to a metric query. The system then performs 615 off-line computations on the container region and stores the results. The system is then ready to receive 620 a metric query about a particular containee region with respect to the container region. The system then performs 625 on-line computations on the metric query using the corresponding stored off-line computation results. After the on-line computation is complete the system returns 630 the metric query results and the system execution completes 635 for that particular metric query. [0046] Thus an example embodiment of the invention includes a method for preparing a representation of a region in anticipation of a query related to a metric space The representation is used to form a response to a received query. The method further includes the steps of: obtaining a mathematical format of a region within the metric space, disaggregating the region into a set of atomic shapes, and forming the representation of the region by preprocessing and storing at least one property for at least one of the atomic shapes. [0047] In some realizations, the method may include transforming the mathematical representation of the atomic shapes into a sequence of vertices. The method may also include the formation of a response to the query employing the mathematical representation. The method may also include prioritizing the atomic shapes according to a prioritization criterion where prioritization criteria include such criterion as hit rate and region complexity. [0048] In some embodiments, the query could be a spatial query. The mathematical format can include a group of numerical relationships between the components of the spatial regions related to the query. The atomic shapes could include circles, triangles, rectangles, cubes, pyramids, spheres or any combination of these or other shapes. [0049] For example, to disaggregate the spatial region into atomic shapes, the Delauney triangulation algorithm can be used. In this case, atomic shapes are all triangles and the preprocessing steps include the definition of a reference coordinate system and also the definition of local coordinate systems for each atomic shape. An angle of rotation for each side of the triangles with respect to the defined reference coordinate system is then computed. The end points of each sides of these triangles are then transformed into the reference coordinate system. This transformation is a rotation that is defined by a matrix with elements that are computed ahead of time using trigonometry and the computed angles of rotation. When the atomic shapes are circles, the preprocessing steps include the computation of the center and radius of each circle. [0050] To form a response to queries, some embodiments compute a rank for each atomic shape, order these shapes based on this rank, and query each atomic shape according to that order. The rank used here could be based on criteria including, the region complexity of the atomic shape, the hit rate of the shape, any combination of these or other ranking criterion. [0051] An-other example-embodiment for this invention includes a method for preparing and/or providing a response to an anticipated or received spatial query using the following steps: forming an efficient representation of locations of a plurality of geographical regions decomposed into atomic shapes, preparing and/or providing a response to the anticipated or received spatial query by determining whether a point location intersects at least one of the geographical regions and finding the intersection of these geographical regions. [0052] In some embodiments of this method, the step of forming efficient representation of regions disaggregated into atomic components includes segregating computations into an off-line and on-line computations. Sometimes, the off-line computations are employed to capture at least one property of the atomic component. Furthermore, sometimes the atomic components are formed into triangles based on Delaunay triangulation such that orientation of triangular regions with respect to a fixed axis are efficiently calculated via off-line computation. Sometimes, the triangular atomic components are stored as three orientation angles and three line segments. [0053] In some embodiments, the invention is provided as 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 the article of manufacture comprising computer readable program code means for causing a computer to effect the steps of the methods of the invention. [0054] In some embodiments, the invention is provided as 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, such that the method steps comprise the steps of any method of the present invention. [0055] A still further example embodiment, the invention includes an apparatus having means for preparing a representation of a region in anticipation of a query related to a metric space. The representation is used in forming a response to the metric space query. The apparatus also includes means for obtaining a mathematical format of a region within the metric space, means for disaggregating the region into a set of atomic shapes and means for forming the representation of the region by preprocessing and storing at least one property for at least one of the atomic shapes. [0056] In some cases the apparatus includes means for transforming the mathematical representation of the atomic shapes into a sequence of vertices. The apparatus may also include means for the formation of a response to the query employing the mathematical representation. The apparatus may also include means for prioritizing the atomic shapes according to a prioritization criterion where prioritization criteria include such criterion as hit rate and region complexity. [0057] An example of an apparatus that implements the method described herein is shown in FIG. 7. The disaggregator 700 receives mathematical representations of regions from an external map server 730 and performs off-line computation by disaggregating the region into atomic shapes and associating static properties with each atomic shape as well as initialized prioritization criteria. The atomic shapes and their static properties are stored in the region repository 705. Clients 720-721 send metric queries to the query module 715. The query module 715 performs on-line computation on the metric queries by accessing disaggregated regions from the region repository 705 and then sends a response to the clients 720-721. The prioritized criteria can be updated by the metric update module 710 before placing the disaggregated region back into the region repository 705. [0058] The present invention can be realized in hardware, software, or a combination of hardware and software. A visualization tool according to the present invention can be realized in a centralized fashion in one computer system, or in a distributed fashion where different elements are spread across several interconnected computer systems. Any kind of computer system�or other apparatus adapted for carrying out the methods and/or functions described herein�is suitable. A typical combination of hardware and software could be a general purpose computer system with a computer program that, when being loaded and executed, controls the computer system such that it carries out the methods described herein. The present invention can also be embedded in a computer program product, which comprises all the features enabling the implementation of the methods described herein, and which�when loaded in a computer system�is able to carry out these methods. [0059] Computer program means or computer program in the present context include any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after conversion to another language, code or notation, and/or reproduction in a different material form. [0060] Thus the invention includes an article of manufacture which comprises a computer usable medium having computer readable program code means embodied therein for causing a function described above. The computer readable program code means in the article of manufacture comprises computer readable program code means for causing a computer to effect the steps of a method of this invention. Similarly, the present invention may be implemented as a computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a a function described above. The computer readable program code means in the computer program product comprising computer readable program code means for causing a computer to effect one or more functions of this invention. Furthermore, the present invention may be implemented as a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for causing one or more functions of this invention. [0061] It is noted that the foregoing has outlined some of the more pertinent objects and embodiments of the present invention. This invention may be used for many applications. Thus, although the description is made for particular arrangements and methods, the intent and concept of the invention is suitable and applicable to other arrangements and applications. It will be clear to those skilled in the art that modifications to the disclosed embodiments can be effected without departing from the spirit and scope of the invention. Thus, the invention may be implemented by an apparatus including means for performing the steps and/or functions of any of the methods used for carrying out the concepts of the present invention, in ways described herein and/or known by those familiar with the art. The described embodiments ought to be construed to be merely illustrative of some of the more prominent features and applications of the invention. Other beneficial results can be realized by applying the disclosed invention in a different manner or modifying the invention in ways known to those familiar with the art. Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7373353May 10, 2002May 13, 2008International Business Machines CorporationReducing index size for multi-level grid indexesUS7379944Oct 20, 2005May 27, 2008International Business Machines CorporationReducing index size for multi-level grid indexesUS7383275May 10, 2002Jun 3, 2008International Business Machines CorporationMethods to improve indexing of multidimensional databasesUS7389283Dec 7, 2004Jun 17, 2008International Business Machines CorporationMethod for determining an optimal grid index specification for multidimensional dataUS7437372Oct 20, 2005Oct 14, 2008International Business Machines CorporationSystems, methods, and computer program products to reduce computer processing in grid cell size determination for indexing of multidimensional databasesUS7739264 *Nov 15, 2006Jun 15, 2010Yahoo! Inc.System and method for generating substitutable queries on the basis of one or more featuresUS7761350 *Aug 16, 2006Jul 20, 2010Aol Inc.Biasing of search result clustering to ensure more effective point of interest (POI) targetingUS7769733Jan 28, 2008Aug 3, 2010International Business Machines CorporationSystem and computer program products to improve indexing of multidimensional databasesUS7779038Oct 31, 2007Aug 17, 2010International Business Machines CorporationReducing index size for multi-level grid indexesUS7836082Jan 25, 2008Nov 16, 2010International Business Machines CorporationReducing index size for multi-level grid indexesUS7860891Oct 20, 2005Dec 28, 2010International Business Machines CorporationReducing index size for multi-level grid indexesUS8155672Sep 16, 2008Apr 10, 2012Avaya Inc.Scalable geo-location event processingUS8229955 *Dec 5, 2006Jul 24, 2012International Business Machines CorporationDatabase query optimizer that takes network choice into considerationUS8521731Jul 9, 2008Aug 27, 2013Yahoo! Inc.Systems and methods for query expansion in sponsored searchUS8645235 *Jul 9, 2010Feb 4, 2014Aol Inc.Biasing of search result clustering to ensure more effective point of interest (POI) targetingUS20110166957 *Jul 9, 2010Jul 7, 2011Aol Inc.Biasing of search result clustering to ensure more effective point of interest (poi) targeting* Cited by examinerClassifications U.S. Classification1/1, 707/E17.018, 707/E17.024, 707/999.001International ClassificationG06F7/00, G06F17/30Cooperative ClassificationY10S707/99933, G06F17/30241, G06F17/30259European ClassificationG06F17/30L, G06F17/30M1SLegal EventsDateCodeEventDescriptionJan 30, 2014FPAYFee paymentYear of fee payment: 8Jan 30, 2014SULPSurcharge for late paymentYear of fee payment: 7Oct 11, 2013REMIMaintenance fee reminder mailedJul 17, 2009FPAYFee paymentYear of fee payment: 4Jul 26, 2002ASAssignmentOwner name: INTERNATIONAL BUSINESS MACHINES CORPORATION, NEW YFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:DAVIS, JOHN SIDNEY II;SOW, DABY MOUSSE;REEL/FRAME:013160/0095Effective date: 20020726RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google