DRONE MANAGEMENT DATA STRUCTURE

• US 20170263134A1
• Filed: 03/08/2016
• Published: 09/14/2017
• Est. Priority Date: 03/08/2016
• Status: Active Grant

• Current Assignee: DoorDash, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Blomberg, Jeanette L., Butler, Eric K., Chandra, Anca A., Chowdhary, Pawan R., Griffin, Thomas D., Jadav, Divyesh, Moore, Robert J., Strong, JR., Hovey R.
• Granted Patent: US 10,417,917 B2
• Time in Patent Office: Days
• CPC Class Codes: G08G 5/0013 with a ground station
• CPC Class Codes: G08G 5/0026 located on the ground
• CPC Class Codes: G08G 5/0039 Modification of a flight plan
• CPC Class Codes: G08G 5/0056 in an emergency situation, e.g. hijacking
• CPC Class Codes: G08G 5/0069 specially adapted for an unmanned aircraft
• CPC Class Codes: G08G 5/0082 for monitoring traffic from a ground station radar or analogous systems specially adapted for traffic control G01S13/91

Abstract

One embodiment provides a method comprising maintaining a multi-dimensional data structure partitioned into cells utilizing a tree data structure (“tree”) comprising intervals for each dimension of a multi-dimensional space. To partition an interval for a node of the tree into multiple subintervals, multiple leaf nodes (“leaves”) are generated, each leaf descending from the node. To merge multiple intervals for multiple nodes of the tree, a parent node (“parent”) and multiple leaves descending from the parent are generated, the parent and the leaves are time constrained, and the leaves are scheduled for a merger. When transient data in cells included in a list that corresponds to a leaf scheduled for merger expires, each cell in the list is converted into a cell for inclusion in a different list corresponding to a parent of the leaf, each leaf of the parent removed, and the parent turned into a leaf.

Claims

1. A method, comprising:

maintaining a multi-dimensional data structure partitioned into cells utilizing a tree data structure comprising intervals for each dimension of a multi-dimensional space, wherein some nodes of the tree data structure are associated with lists of cells, and the cells are configured to maintain sparse and transient data;

in response to a request to partition an interval for a node of the tree data structure into multiple subintervals, generating multiple leaf nodes corresponding to the multiple subintervals, wherein each leaf node descends from the node;

in response to a request to merge multiple intervals corresponding to multiple nodes of the tree data structure, generating a parent node and multiple leaf nodes descending from the parent node, wherein the parent node and the multiple leaf nodes are time constrained, and the multiple leaf nodes are scheduled for a merger; and

in response to an expiration of transient data in cells included in a list that correspond to all but one leaf node scheduled for merger, converting each cell in the list for the one remaining leaf node with unexpired data, if any, into a cell for inclusion in a different list corresponding to the parent node of the leaf node, removing each leaf node of the parent node, and turning the parent node into a leaf node.

2. The method of claim 1, wherein each cell implicitly points to a hash table of transient data, and a hash function is applied when concatenating one or more representations of intervals corresponding to dimensions of the cell during a merger.

3. The method of claim 1, wherein a merger of multiple intervals is determined based on a measure of the activity associated with cells corresponding to the multiple intervals.

4. The method of claim 1, wherein a partition of an interval is determined based on a measure of the activity associated with cells corresponding to the interval.

5. The method of claim 2, wherein a time constraint associated with a leaf node or a parent of a leaf node indicates whether a specific piece of information should be associated with a parent node or a leaf node based on the time or times associated with the information.

6. A system comprising a computer processor, a computer-readable hardware storage medium, and program code embodied with the computer-readable hardware storage medium for execution by the computer processor to implement a method comprising:

maintaining a multi-dimensional data structure partitioned into cells utilizing a tree data structure comprising intervals for each dimension of a multi-dimensional space, wherein some nodes of the tree data structure are associated with lists of cells, and the cells are configured to maintain sparse and transient data;

in response to a request to partition an interval for a node of the tree data structure into multiple subintervals, generating multiple leaf nodes corresponding to the multiple subintervals, wherein each leaf node descends from the node;

in response to a request to merge multiple intervals corresponding to multiple nodes of the tree data structure, generating a parent node and multiple leaf nodes descending from the parent node, wherein the parent node and the multiple leaf nodes are time constrained, and the multiple leaf nodes are scheduled for a merger; and

in response to an expiration of transient data in cells included in a list that correspond to all but one leaf node scheduled for merger, converting each cell in the list for the one remaining leaf node with unexpired data, if any, into a cell for inclusion in a different list corresponding to the parent node of the leaf node, removing each leaf node of the parent node, and turning the parent node into a leaf node.

7. The system of claim 6, wherein each cell implicitly points to a hash table of transient data, and a hash function is applied when concatenating one or more representations of intervals corresponding to dimensions of the cell during a merger.

8. The system of claim 6, wherein a merger of multiple intervals is determined based on a measure of the activity associated with cells corresponding to the multiple intervals.

9. The system of claim 6, wherein a partition of an interval is determined based on a measure of the activity associated with cells corresponding to the interval.

10. The system of claim 7, wherein a time constraint associated with a leaf node or a parent of a leaf node indicates whether a specific piece of information should be associated with a parent node or a leaf node based on the time or times associated with the information.

11. A computer program product comprising a computer-readable hardware storage device having program code embodied therewith, the program code being executable by a computer to implement a method comprising:

maintaining a multi-dimensional data structure partitioned into cells utilizing a tree data structure comprising intervals for each dimension of a multi-dimensional space, wherein some nodes of the tree data structure are associated with lists of cells, and the cells are configured to maintain sparse and transient data;

in response to a request to partition an interval for a node of the tree data structure into multiple subintervals, generating multiple leaf nodes corresponding to the multiple subintervals, wherein each leaf node descends from the node;

in response to a request to merge multiple intervals corresponding to multiple nodes of the tree data structure, generating a parent node and multiple leaf nodes descending from the parent node, wherein the parent node and the multiple leaf nodes are time constrained, and the multiple leaf nodes are scheduled for a merger; and

in response to an expiration of transient data in cells included in a list that correspond to all but one leaf node scheduled for merger, converting each cell in the list for the one remaining leaf node with unexpired data, if any, into a cell for inclusion in a different list corresponding to the parent node of the leaf node, removing each leaf node of the parent node, and turning the parent node into a leaf node.

12. The computer program product of claim 11, wherein each cell implicitly points to a hash table of transient data, and a hash function is applied when concatenating one or more representations of intervals corresponding to dimensions of the cell during a merger.

13. The computer program product of claim 11, wherein a merger of multiple intervals is determined based on a measure of the activity associated with cells corresponding to the multiple intervals.

14. The computer program product of claim 11, wherein a partition of an interval is determined based on a measure of the activity associated with cells corresponding to the interval.

15. The computer program product of claim 12, wherein a time constraint associated with a leaf node or a parent of a leaf node indicates whether a specific piece of information should be associated with a parent node or a leaf node based on the time or times associated with the information.