Progressive continuous range query for moving objects with a tree-like index

• US 10,095,724 B1
• Filed: 08/09/2017
• Issued: 10/09/2018
• Est. Priority Date: 08/09/2017
• Status: Active Grant

• Current Assignee: The Florida International University Board of Trustees (State University System of Florida)
• Original Assignee: The Florida International University Board of Trustees (State University System of Florida)
• Inventors: Zhang, Mingjin, Rishe, Naphtali, Liu, Weitong, Li, Tao
• Primary Examiner(s): KUDDUS, DANIEL A
• Application Number:
  US15/672,884
• Time in Patent Office: 426 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries

Abstract

Methods for progressive continuous range query (PCRQ) are provided. A method can include using branch-and-bound to index interest points with a tree-index and generating a nearest enter split-point for a root node in the tree-index and adding to min-heap. Next, whether min-heap has more elements and whether a next split-point in min-heap is closer than a destination can be determined. Whether a query point has reached a split-point can be investigated followed by retrieving an entry that has generated the split-point. The split-point can be then be removed from min-heap.

Claims

1. A progressive continuous range query (PCRQ) method, the method being performed by a system comprising a processor and a computer-readable medium having instructions stored thereon that perform the method when executed by the processor, the method comprising:

using branch-and-bound to index interest points with a tree-index;

generating a nearest enter split point for a root node in the tree-index and adding to min-heap;

generating a next nearest enter split point for the root node, a domain region of a node being a region that is generated by expanding a boundary of the root node by a specified range;

inserting the generated split point into min-heap;

when the obtained node is an internal node, collapsing the internal node by removing the internal node'"'"'s children from a temporary buffer of nodes, and adding the internal node to the temporary buffer; and

when the obtained node is a leaf node, removing the leaf node from the list of points of interest, and reporting the list as a result;

determining whether min-heap has more elements and whether a next split point in min-heap is closer than a destination;

receiving a geographical location of a moving object;

generating a query point representing the geographical location of the moving object;

determining whether the query point has reached a split point;

retrieving an entry that has generated the split point;

removing the split point from min-heap;

determining whether the split point is an enter split point; and

determining again whether min-heap has more elements and whether a next split point in min-heap is closer than the destination.

2. The method of claim 1, further comprising, after determining that the split point is an enter split point, generating an exit split point and adding the exit split point to min-heap.

3. The method of claim 2, further comprising, after determining that the enter split point is a node, expanding the node by generating children entries'"'"' nearest enter split points and adding the nearest enter split points to min-heap.

4. The method of claim 1, further comprising, after determining that the enter split point is not a node, adding the enter split point to a result.

5. The method of claim 4, further comprising, after determining that the split point is not an enter split point, generating the entry'"'"'s nearest enter split point and adding the entry'"'"'s nearest enter split point to min-heap.

6. The method of claim 4, further comprising, after determining that the entry is a node, determining whether the entry has an enter split point in min-heap.

7. The method of claim 6, further comprising, after determining that the entry does not have an enter split point in S-heap, collapsing the entry by removing the entry'"'"'s children from a waiting-list and adding the entry to the waiting list.

8. The method of claim 4, further comprising, after determining that the entry is not a node, removing the entry from the result.

9. A progressive continuous range query (PCRQ) method, the method being performed by a system comprising a processor and a computer-readable medium having instructions stored thereon that perform the method when executed by the processor, the method comprising:

(a) applying a branch-and-bound algorithm to determine points of interest within a query point'"'"'s range as an initial result set, receiving a geographical location of a moving object, and generating a query point representing the geographical location of the moving object;

(b) generating a next nearest enter split point for a root node;

calculating a first intersection between a domain region of the root node and a query trajectory, the domain region of a node being a region that is generated by expanding a boundary of the root node by a specified range; and

inserting the generated split point into a min-heap of split points;

(c) obtaining a next split point in the S-heap when a distance between the query point and the split point is below a threshold;

(d) retrieving the node that generated the split point before removing the split point from the S-heap,

(e) when the split point is an enter split point, generating the node'"'"'s exit split point;

inserting the generated exit split point into the S-heap and, when the node is an internal node, expanding the internal node, and generating the next nearest enter split points for each of the internal node'"'"'s children, and inserting the generated split points into the S-heap; and

, when the node is a leaf node, adding the node to a list of points of interest, and reporting the list as a result to a user;

(f) when the split point is an exit split point as the node'"'"'s domain region intersects with the query trajectory at least once, determining a next nearest enter split point or exit split point, and adding the next nearest enter split point or exit split point to the S-heap; and

, when the obtained node is an internal node, collapsing the internal node by removing the internal node'"'"'s children from a temporary buffer of nodes, and adding the internal node to the temporary buffer; and

, when the node is a leaf node, removing the leaf node from the list of points of interest, and reporting the list as a result; and

(g) repeating steps (c) through (f) until the S-heap is empty or the distance between the query point and next split point in the min-heap exceeds a distance between the query point and an end of the query trajectory,

the result being continually predicted and maintained considering the query range as a measurement in one or more of the following metrics;

time, direct distance, distance of polylines traversable by the query point, and a top-k list of results in which each result entry in a list is one of the top-k incoming interest points.

10. The method of claim 9, the query trajectory not being limited to reporting said range query per segment in the query trajectory.

11. The method of claim 9, the query trajectory being any shape, including, but not limited to, a line segment, a polyline, a curve, and an ellipse.

12. The method claim 9, further comprising collapsing node in the tree-like index that the query point passes.

13. A progressive continuous range query (PCRQ) method, the method being performed by a system comprising a processor and a computer-readable medium having instructions stored thereon that perform the method when executed by the processor, the method comprising:

using branch-and-bound to index interest points with a tree-index;

generating a nearest enter split point for a root node in the tree-index and adding to min-heap;

generating a next nearest enter split point for the root node, the domain region of a node being a region that is generated by expanding a boundary of the root node by a specified range;

inserting the generated split point into min-heap;

when the obtained node is an internal node, collapsing the internal node by removing the internal node'"'"'s children from a temporary buffer of nodes, and adding the internal node to the temporary buffer; and

when the obtained node is a leaf node, removing the leaf node from the list of points of interest, and reporting the list as a result;

determining whether min-heap has more elements and whether a next split point in min-heap is closer than a destination;

receiving a geographical location of a moving object;

generating a query point representing the geographical location of the moving object;

determining whether the query point has reached a split point;

retrieving an entry that has generated the split point;

removing the split point from min-heap;

determining whether the split point is an enter split point and, when the split point is an enter split point, generating an exit split point that is added to min-heap;

determining whether the enter split point is a node and, when the enter split point is a node, expanding the node by generating children entries'"'"' nearest enter split points and adding the nearest enter split points to min-heap; and

determining again whether min-heap has more elements and whether a next split point in min-heap is closer than the destination.