Efficient progressive continuous k-nearest neighbor query algorithm for moving objects with a tree-like index

Patent metadata

Field	Value
Publication number	US-10331753-B1
Application number	US-201815945222-A
Country	US
Kind code	B1
Filing date	Apr 4, 2018
Priority date	Apr 4, 2018
Publication date	Jun 25, 2019
Grant date	Jun 25, 2019

Abstract

Methods and systems for computing continuous k nearest neighbor (CkNN) queries in location based services for moving objects, to produce ordered kNN query results in a continuous and progressive manner, are provided. One method comprises receiving a continuous k nearest neighbor query, computing the initial set comprised of the k interest points nearest to the reference point and a set of remaining nodes stored in a distance-priority queue, generating and storing split points in a min-heap, iteratively moving current reference point to the nearest split point, swapping interest points, updating the corresponding split points in the min-heap, and reporting the kNN result progressively until a termination condition is reached.

First claim

What is claimed is:

1. A system for performing a continuous k-nearest neighbor (CkNN) query in location based services for moving objects, the system comprising:
a computer readable medium comprising instructions that when executed causes at least one processor to:
receive a k-nearest neighbor query from a mobile device;
continuously receive a location and trajectory of the mobile device, an initial location of the mobile device being a reference point, the position of the reference point matching the position the mobile device along the trajectory;
access a database containing a plurality of interest points surrounding the location and trajectory of the mobile device;
store and index, in computer memory, the plurality of interest points in a spatial tree index;
construct a first list to store all nodes of the spatial tree index, each node being ordered by its distance to the current location of the reference point, the list comprising a first partition containing the k-nearest interest points and a second partition containing each node that references the k-nearest interest points;
initialize a first min-heap to initially contain split points, computed as follows:
for each node n1 and its subsequent adjacent node n2 in the first list, perform the following procedure, comprising:
given the node n1 and its subsequent adjacent node n2, detect a split point in the mobile device's trajectory, a split point being a point whose position has equal distances from the two nodes n1, n2 respectively;
add the split point nearest to the current position of the reference point to the first heap; and

continuously maintain the split points in the first heap as ordered by their distance to the current location of the reference point and link each split point to the two nodes n1, n2 in first list from which each split point was computed;
continuously query the index to compute k-nearest interest points nearest to the mobile device;
continuously maintain a queue comprising nodes referencing the k-nearest interest points and a hierarchy of minimal bounding rectangles; and
continuously return to the moving device, the k-nearest interest points.

2. The system of claim 1 , the computer readable medium that when executed further causes the at least one processor to:
iteratively perform the following steps until a termination condition is reached:
move the location of the reference point to a split point that is contained in the first heap;
in the first list, retrieve the node n1 and subsequent adjacent node n2 linked to the split point that is contained in the first heap,
the node n1 and the subsequent adjacent node n2 being both in the second partition;
swap the order of the node n1 and the subsequent adjacent node n2;

remove from the first min-heap any split points that are linked to nodes that were swapped; and
generate new splits points.

3. The system of claim 2 , the termination condition comprising one of the following: the reference point becomes a split point or a specified point in the trajectory path, or the first min-heap is empty.

4. The system of claim 1 , the computer readable medium that when executed further causes the at least one processor to:
iteratively perform the following steps until a termination condition is reached:
move the location of the reference point to a split point that is contained in the first heap;
in the first list, retrieve the node n1 and subsequent adjacent node n2 linked to the split point that is contained in the first heap,
the node n1 and the subsequent adjacent node n2 both being leaf nodes and the node n1 is in the first partition;
swap the order of the node n1 and the subsequent adjacent node n2;
remove from the first min-heap any split points that are linked to nodes that were swapped; and

generate new splits points.

5. The system of claim 4 , the computer readable medium that when executed further causes the at least one processor to:
prior to the swap, the subsequent adjacent node n2 being contained in the second partition;
remove the node n1 from the first partition and place the node n1 into the second partition;
recursively collapse for all parent nodes of the node n1 by the following procedure:
for a given node p, if no leaf nodes of node p's sub-branch tree are in the first partition, then all nodes of p's sub-branch tree that are stored in the second partition are removed from second partition;
add p to the first list; and
output the first partition.

6. The system of claim 4 , the termination condition comprising one of the following: the reference point becomes a split point or a specified point in the trajectory path, or the first min-heap is empty.

7. The system of claim 1 , the computer readable medium that when executed further causes the at least one processor to:
iteratively perform the following steps until a termination condition is reached:
move the location of the reference point to a split point that is contained in the first heap;
in the first list, retrieve the node n1 and subsequent adjacent node n2 linked to the split point that is contained in the first heap;
the node n1 being a leaf node in the first partition and the subsequent adjacent node n2 being an internal node in the second partition;
remove the subsequent adjacent node n2 from the first list;
compute each distance of each child node of the subsequent adjacent node n2 from the current location of the reference point;
insert all child nodes of the subsequent adjacent node n2 into the first list,
insertion beginning after the original position of the subsequent adjacent node n2; and
continuously maintaining the order in the first list by re-computing and comparing each child nodes' distance to the current location of the reference point and a current entry node's distance to the current location of the reference point,

each child node being inserted into the first list before an entry node whose distance to the original location of the reference point is greater than or equal to respective child node's distance to the current location of the reference point,
each child node being inserted into the first list after the entry node whose distance to the original location of the reference point is less than the respective child node's distance to the current location of the reference point, and
any child node whose distance to the current location of the reference point is greater than each of the existing entry node's distances to the current location of the reference point being inserted into the end of the first list.

8. The system of claim 1 , the mobile device comprising the computer readable medium.

9. The system of claim 1 , the computer readable medium that when executed further causes the at least one processor to:
compute the position of the node n1 and subsequent adjacent node n2 by solving an equal distance equation,
the two sides of the equation being continuous distance functions that present the current distance between each node and the current location of the reference point.

10. The system of claim 1 , the computer readable medium that when executed further causes the at least one processor to:
compute the position of the node n1 and subsequent adjacent node n2 by solving an equal distance equation,
the two sides of the equation being continuous distance functions using the distance from reference point to the circumscribed circle of a minimum bounding rectangle of each node instead of the original minimum bounding rectangle of each node, to avoid the complexity of piecewise distance function computing for the minimum bounding rectangle.

11. The system of claim 1 , the computer readable medium that

Assignees

• Tong Jing
• The Florida International Univ Board Of Trustees

Inventors

• Zhang Mingjin
• Rishe Naphtali
• Liu Weitong
• Lazarre Jahkell
• Li Tao

Classifications

• G06F16/909 Primary

  using geographical or spatial information, e.g. location (spatiotemporally dependent retrieval from the web G06F16/9537) · CPC title

• G06F16/9537 Primary

  Spatial or temporal dependent retrieval, e.g. spatiotemporal queries · CPC title

• G06F18/23213

  with fixed number of clusters, e.g. K-means clustering · CPC title

• G06F18/24147

  Distances to closest patterns, e.g. nearest neighbour classification · CPC title

• G06F18/231

  Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram · CPC title