Managing and querying moving point data

• US 7,010,308 B2
• Filed: 12/12/2001
• Issued: 03/07/2006
• Est. Priority Date: 12/13/2000
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Telcontar
• Inventors: Hendrey, Geoffrey R.
• Primary Examiner(s): Corsaro, Nick
• Application Number:
  US10/012,367
• Publication Number:
  US 20020151315A1
• Time in Patent Office: 1,546 Days
• Field of Search: 455/433, 4554141-4143, 455/456.1, 455/456.3, 455/456.5, 455/41.2, 709216-221
• US Class Current: 455/456.5
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

An improved client locating and user discovery system is disclosed. Methods and systems are described that provide the ability for a telecommunications network to frequently update the location data for telecommunications units within the network, while preventing the performance degradation that is inherent in the prior art. In the patented invention, the most frequently updated data is stored outside the main database in active memory in a tree structure, and is accessed through an API that converts the tree data into a database query language readable format.

Claims

1. A method of indexing a database containing dynamic locations of mobile units (MU) in an N-level tree data structure including a root node, branch nodes, and leaf nodes, wherein the root node corresponds to a coverage area, and each subsequent branch or leaf node corresponds to a sub-area of the previous node'"'"'s coverage area, comprising the steps of:

adding an MU to a leaf node corresponding to a coverage area in which the MU is located; and

recursively recomputing the center of each ancestor node, wherein the center corresponds to a center of all the MUs contained within the coverage area corresponding to that node.

2. The method of claim 1 wherein each node holds the geometric center of mass of all MUs reachable from that node.

3. The method of claim 1, further comprising:

responsive to a determination that the position of the MU has changed, removing the MU from the leaf node; and

adding the MU to a second leaf node corresponding to a second coverage area in which the MU is located.

4. The method of claim 3 wherein the second leaf node is the leaf node.

5. The method of claim 3 further comprising responsive to removing the MU from the leaf node, recentering the leaf node and each of its ancestor nodes.

6. The method of claim 3 further comprising responsive to adding the MU to the second leaf node, recentering the second leaf node and each of its ancestor nodes.

7. The method of claim 1 wherein adding the MU to the leaf node further comprises:

descending from a root node to a leaf node along a path of the tree; and

adding the MU to the leaf node at the end of the path.

8. The method of claim 7 wherein descending from a parent node on the path to a child node on the path occurs responsive to a determination that the MU is closer to the child node'"'"'s center of mass than to the center of mass of any siblings of the child node.

9. The method of claim 7 further comprising:

descending from a first node in the path to a second node in the path by;

determining a center-of-mass for each child of the first node; and

responsive to each determined center-of-mass being farther than a predetermined distance, creating a new child node having a center of mass equal to that of the MU; and

descending to the new child node.

10. The method of claim 9 wherein the predetermined distance is associated with the level of the first node.

11. The method of claim 9 wherein a maximum number of child nodes can be added to a parent, and the new child node is created only if the root node has fewer than the maximum number of child nodes.

12. The method of claim 7 further comprising:

determining that a first node has no children;

crating a new node, the new node being a child of the first node; and

descending to the new node.

13. The method of claim 7 wherein navigating from a parent node on the path to a child node on the path occurs responsive to a determination that the MU is within a polygon enclosing the child node'"'"'s center of mass.

14. The method of claim 13 further comprising:

responsive to a determination that the MU is not within a polygon enclosing any child node'"'"'s center of mass;

creating a new child node and an associated polygon, the MU located inside the associated polygon'"'"'s center of mass; and

descending to the new child node.

15. The method of claim 14 wherein a maximum number of child nodes can be added to a parent, and the new child node is created only if the parent node has fewer than the maximum number of child nodes.

16. A system for indexing a database of dynamic locations of mobile units (MU) comprising:

a mobile positioning center adapted to receive location information from one or more MUs;

a database wherein locations of the MUs are stored;

a computer comprising a memory adapted with computer readable instructions for maintaining a database index in an N-level tree data structure including a root node, branch nodes, and leaf nodes, wherein the root node corresponds to a coverage area, and each subsequent branch or leaf node corresponds to a sub-area of the previous node'"'"'s coverage area;

wherein said index is maintained by;

adding an MU to a leaf node corresponding to a coverage area in which the MU is located; and

recursively recomputing the center of each ancestor node, wherein the center corresponds to a center of all the MUs contained within the coverage area corresponding to that node.