Managing and querying moving point data

• US 20020151315A1
• Filed: 12/12/2001
• Published: 10/17/2002
• Est. Priority Date: 12/13/2000
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Gravitate, Inc. (Uber Technologies, Inc.)
• Inventors: Hendrey, Geoffrey R.
• Granted Patent: US 7,010,308 B2
• Time in Patent Office: Days
• US Class Current: 455/466
• 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 computer architecture for storing moving point data, comprising:

a moving point server for managing moving point data;

a database server for storing data related to said moving point data,

wherein said database server and said moving point server communicate using a reliable connection.

2. The computer architecture of claim 1, wherein the moving point data is stored in active memory.

3. The computer architecture of claim 2, wherein at least some of the moving point data is stored in a tree structure.

4. The computer architecture of claim 3, wherein the tree structure is a quad-tree.

5. The computer architecture of claim 3, wherein the tree structure contains nodes with a first value coordinate representing a latitudinal location and a second value coordinate representing a longitudinal location.

6. The computer architecture of claim 5, wherein a node in the tree structure stores a set of location coordinates.

7. The computer architecture of claim 6, wherein the tree structure is traversed by comparing a desired set of location coordinates to the set of location coordinates stored in node in the tree structure.

8. The computer architecture of claim 3, further comprising an object handler for indexing object descriptor records stored on the moving point server.

9. The computer architecture of claim 8, further comprising a linked list of the object descriptor records, wherein the object descriptor records share identical location coordinates.

10. The computer architecture of claim 9, wherein one or more of the object descriptor records contains a first pointer to the tree structure.

11. The computer architecture of claim 10, further comprising a data structure located within a leaf node of the tree structure, wherein the data structure contains a second pointer to one or more of the object descriptor records.

12. The computer architecture of claim 1, wherein the database server has a virtual table interface.

13. The computer architecture of claim 1, wherein the data related to said moving point data shares with the moving point data a common object identifier record.

15. The method of claim 14, wherein at least some of the moving point data is stored in a tree structure.

16. The method of claim 15, wherein the tree structure is a quad-tree.

17. The method of claim 15, wherein the tree structure is an oct-tree.

18. The method of claim 15, wherein the tree structure is a KD-tree.

19. The method of claim 15, wherein the tree structure is a B-tree.

20. The method of claim 14 further comprising step of:

prior to storing the moving point data, creating an object handler for indexing the moving point data.

21. The method of claim 15, wherein the tree structure has a leaf node and within said leaf node a data structure having a pointer to an object descriptor record.

22. The method of claim 14, wherein the stored instructions are on a virtual table interface.

23. The method of claim 14, wherein the moving point data is stored on a moving point server, and said moving point server is linked to said stored instructions by way of a reliable connection.

25. The method of claim 24, further comprising the step of:

converting the retrieved data set into a database query language readable format.

26. The method of claim 24, wherein a moving point server receives the location of the first telecommunications unit.

27. The method of claim 26, further comprising the step of:

storing the location of the first telecommunications unit in an object descriptor record,

wherein the object descriptor record is related to the first telecommunications unit by an object identifier.

28. The method of claim 27, wherein the leaf node contains a first pointer to the object descriptor record.

29. The method of claim 28, wherein the leaf node contains a second pointer to a second object descriptor record related to a second telecommunications unit by a second object identifier.

30. The method of claim 26, wherein the tree data structure is traversed by comparing a desired coordinate pair to a stored coordinate pair found in non-leaf nodes of the tree structure, said stored coordinate pair representing location coordinates already stored in the moving point server.

31. The method of claim 24, wherein the first telecommunications unit is a mobile telecommunications unit.

14. A method of managing moving point data, said method comprising the steps of:

storing the moving point data in a tree data structure in memory;

accessing the moving point data using stored instructions; and

converting the moving point data to a format readable by a database query language.

24. A method for determining the proximity of telecommunications units in a telecommunications network comprising steps of:

receiving a location of a first telecommunications unit;

locating in a tree data structure a leaf-node that encompasses the location of the first telecommunications unit;

retrieving from a data structure within the leaf node a data set representing telecommunications units located within a physical proximity to the first telecommunications unit; and

outputting the retrieved data set.

32. A memory for storing moving point data, comprising:

an object handler data structure for storing an identifying characteristic of a plurality of moving point data objects;

an object descriptor data structure for storing records corresponding to object descriptors located near to each other, wherein an object handler record points to at least one object descriptor record; and

a location data structure for organizing and storing geographic locations at which object descriptors associated with mobile units may be found.

33. A method of indexing a database containing dynamic locations of mobile units 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 a mobile unit to a leaf node corresponding to a coverage area in which the MU is located; and

recursively recomputing the center of each linear parent node, wherein the center corresponds to a geometric mean of all the mobile units contained within the coverage area corresponding to that node.

34. 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 linear parent node, wherein the center corresponds to a geometric mean of all the MUs contained within the coverage area corresponding to that node.

35. 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 linear parent node, wherein the center corresponds to a geometric mean of all the MUs contained within the coverage area corresponding to that node.