Voronoi diagram-based algorithm for efficient progressive continuous k-nearest neighbor query for moving objects

• US 10,200,814 B1
• Filed: 04/24/2018
• Issued: 02/05/2019
• Est. Priority Date: 04/24/2018
• 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, Lazarre, Jahkell, Li, Tao
• Primary Examiner(s): Dang, Thanh-Ha
• Application Number:
  US15/960,797
• Time in Patent Office: 287 Days
• Field of Search: 707713
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/90348 by searching ordered data, e.g. alpha-numerically ordered data
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences

Abstract

Methods and apparatuses for providing a k-nearest neighbor for location based services are provided. A method can include querying a database to detect a plurality of interest points within a predetermined distance of the user device using a kNN algorithm, organizing the interest points within a Voronoi tree, and continuously return a position specific result of relevant interest points.

Claims

1. A method for performing a continuous computer-based k-nearest neighbors (kNN) query in location based services for moving objects, which outputs ordered query results in a continuous and progressive manner, comprising:

providing a query computing device comprising a computer readable medium comprising instructions that when executed causes at least one processor to;

receive, by a receiving device, a continuous k-nearest neighbor (kNN) query from a querying device;

detect, by a detecting device, an initial position, a current position, and a trajectory path of the querying device, the initial position being considered a reference point;

continuously detect a set of interest points surrounding the querying device along the trajectory path;

continuously map the set of interest points into a Voronoi diagram;

store and index the set of interest points using a Voronoi R-tree (VoR-tree);

continuously compute a set of k-nearest interest points to the querying device;

construct a list of the k-nearest interest points, the list being ordered on each interest point'"'"'s distance from the querying device;

partition the ordered list, a first partition containing the k-nearest interest points, and a second partition containing all adjacent neighbors of the k-nearest interest points;

initialize a min-heap data structure to contain a plurality of split points, a split point being computed by computing a perpendicular bisector for each interest point and subsequent interest point in the ordered list and then detecting each point of intersection of each perpendicular bisector and the trajectory path, each point of intersection being a split point;

insert each split point into the min-heap data structure in ordered pairs, a second interest point of a pair being the first interest point in a directly subsequent pair;

maintain an order of the min-heap data structure based upon each point of intersection'"'"'s distance from the querying device;

link each split point with its pair of interest point and subsequent interest point;

perform steps a)-e) until a termination condition is reached;

a) detect the querying device traversing a split point;

b) move the position of the reference point from the initial position to a position of the traversed split point;

c) in the list swap the position of the interest point and subsequent adjacent interest point (s 1, s2) linked to the traversed split point thereby causing the list to be ordered by the distance to the position of the traversed split point;

d) remove from the min-heap data structure, each split point being computed using pairs (s0, s1), (s1, s2) and (s2, s3); and

e) for each of pairs (s0, s2), (s2, s1), and (s1, s3), add to the min-heap data structure a nearest (to the reference point) intersection point of the trajectory and the perpendicular bisector of each respective pair; and

continuously transmit the k-nearest interest points to the mobile device.

2. The method of claim 1, prior to the swap interest point s1 being in the first partition and interest point s2 being in the second partition, the processor being further configured to:

identify and remove each of interest point s1'"'"'s adjacent neighbors that are not adjacent neighbors of any interest points in the first partition, as defined in the Voronoi Diagram, from the list;

remove from the min-heap data structure each split points linked to the removed s1'"'"'s adjacent neighbors in the ordered list;

identify and add s2'"'"'s adjacent neighbors that are not in the second partition, as defined in the Voronoi Diagram, to the ordered list; and

for each new pair formed as the result of adding s2'"'"'s adjacent neighbors to the ordered list, add to the min-heap data structure the nearest (to the reference point) intersection point of the trajectory path and the perpendicular bisector of the new pair.

3. The method of claim 2, the processor being further configured to:

optimize identification of interest point s1'"'"'s adjacent neighbors that are not adjacent neighbors of the k-nearest interest points by utilizing a graph which contains mappings between each interest point sk in the ordered list and each interest point that sk is referencing and each interest point that is referencing sk in the list; and

optimize identification of interest point s2'"'"'s adjacent neighbors that are not in the second partition by utilizing a graph which contains mappings between each interest point sk in the ordered list and each interest point that sk is referencing and each interest point that is referencing sk in the list.

4. The method of claim 3, the graph being implemented by using a reference pointer in the memory of a computer readable medium, the reference pointer being stored in one element in the ordered list and point to another element in list to represent the relationship in the Voronoi diagram of two interest points in the ordered list.

5. The method of claim 1, when interest points s1 and s2 are not in the second partition, the processor being further configured to:

continuously transmit the first partition to the querying device.

6. The method of claim 1, the query computing device being the same as the querying device.

7. The method of claim 1, the processor further being configured to:

use pointers in the memory of the computer readable medium to maintain the linking between each split point in the min-heap data structure and each corresponding two interest points in the ordered list used to generate each respective split point.

8. The method of claim 1, the termination condition comprising one of the following situations:

the reference point becomes a split point or a specified point in the trajectory path;

or the min-heap data structure is empty.

9. The method of claim 1, an interest point being at least one hospital, medical office, restaurant, gas station, landmark, hotel, structure, service provider, vendor, retailer, store, or any combination thereof.

10. The method of claim 1, The method of claim 1, the query computing device being an external device communication with the querying device through a communications network.

11. A system for performing computer-based continuous k-nearest neighbors (kNN) query in location based services for moving objects, which outputs ordered query results in a continuous and progressive manner, the system comprising:

a querying device;

a database containing geo-locations of at least one hospital, medical office, restaurant, gas station, landmark, hotel, structure, service provider, vendor, retailer, store, or any combination thereof;

a communication network connecting the query device and database, and

a query computing device in communication with the database and querying device through the communication network and comprising a computer readable medium comprising instructions that when executed causes at least one processor to;

receive a continuous k-nearest neighbor (kNN) query from a querying device;

detect an initial position, a current position, and a trajectory path of the querying device, the initial position being considered a reference point;

continuously detect a set of interest points surrounding the querying device along the trajectory path;

continuously map the set of interest points into a Voronoi diagram;

store and index the set of interest points using a Voronoi R-tree (VoR-tree);

continuously compute a set of k-nearest interest points to the querying device;

construct a list of the k-nearest interest points, the list being ordered on each interest point'"'"'s distance from the querying device;

partition the ordered list, a first partition containing the k-nearest interest points, and a second partition containing all adjacent neighbors of the k-nearest interest points;

initialize a min-heap data structure to contain a plurality of split points, a split point being computed by computing a perpendicular bisector for each interest point and subsequent interest point in the ordered list and then detecting each point of intersection of each perpendicular bisector and the trajectory path, each point of intersection being a split point;

insert each split point into the min-heap data structure in ordered pairs, a second interest point of a pair being the first interest point in a directly subsequent pair;

maintain an order of the min-heap data structure based upon each point of intersection'"'"'s distance from the reference point;

link each split point with its pair of interest point and subsequent interest point; and

perform steps a)-e) until a termination condition is reached;

a) detect the querying device traversing a split point;

b) move the position of the reference point from the initial position to a position of the traversed split point;

c) in the list swap the position of the interest point and subsequent adjacent interest point (s1, s2) linked to the traversed split point thereby causing the list to be ordered by the distance to the position of the traversed split point;

d) remove from the min-heap data structure, each split point being computed using pairs (s0, s1), (s1, s2) and (s2, s3); and

e) for each of pairs (s0, s2), (s2, s1), and (s1, s3), add to the min-heap data structure a nearest (to the reference point) intersection point of the trajectory and the perpendicular bisector of each respective pair; and

continuously transmit the k-nearest interest points to the mobile device.

12. A system for performing computer-based continuous k-nearest neighbors (kNN) query in location based services for moving objects, which outputs ordered query results in a continuous and progressive manner, the system comprising:

a querying device; and

a query computing device in communication with the querying device and comprising a computer readable medium comprising instructions that when executed causes at least one processor to;

receive a continuous k-nearest neighbor (kNN) query from a querying device;

detect an initial position, a current position, and a trajectory path of the querying device, the initial position being considered a reference point;

continuously detect a set of interest points surrounding the querying device along the trajectory path;

continuously map the set of interest points into a Voronoi diagram;

store and index the set of interest points using a Voronoi R-tree (VoR-tree);

continuously compute a set of k-nearest interest points to the querying device;

construct a list of the k-nearest interest points, the list being ordered on each interest point'"'"'s distance from the reference point;

partition the ordered list, a first partition containing the k-nearest interest points, and a second partition containing all adjacent neighbors of the k-nearest interest points;

initialize a min-heap data structure to contain a plurality of split points, a split point being computed by computing a perpendicular bisector for each interest point and subsequent interest point in the ordered list and then detecting each point of intersection of each perpendicular bisector and the trajectory path, each point of intersection being a split point;

insert each split point into the min-heap data structure in ordered pairs, a second interest point of a pair being the first interest point in a directly subsequent pair;

maintain an order of the min-heap data structure based upon each point of intersection'"'"'s distance from the reference point;

link each split point with its pair of interest point and subsequent interest point;

perform steps a)-e) until a termination condition is reached;

a) detect the querying device traversing a split point;

b) move the position of the reference point from the initial position to a position of the traversed split point;

c) in the list swap the position of the interest point and subsequent adjacent interest point (s1, s2) linked to the traversed split point thereby causing the list to be ordered by the distance to the position of the traversed split point;

d) remove from the min-heap data structure, each split point being computed using pairs (s0, s1), (s1, s2) and (s2, s3); and

e) for each of pairs (s0, s2), (s2, s1), and (s1, s3), add to the min-heap data structure a nearest (to the reference point) intersection point of the trajectory and the perpendicular bisector of each respective pair; and

transmit the k-nearest interest points to the mobile device.

13. The system of claim 12, prior to the swap interest point s1 being in the first partition and interest point s2 being in the second partition, the processor being further configured to:

identify and remove each of interest point s1'"'"'s adjacent neighbors that are not adjacent neighbors of any interest points in the first partition, as defined in the Voronoi Diagram, from the list;

remove from the min-heap data structure each split points linked to the removed s1'"'"'s adjacent neighbors in the ordered list;

identify and add s2'"'"'s adjacent neighbors that are not in the second partition, as defined in the Voronoi Diagram, to the ordered list; and

for each new pair formed as the result of adding s2'"'"'s adjacent neighbors to the ordered list, add to the min-heap data structure the nearest (to the reference point) intersection point of the trajectory path and the perpendicular bisector of the new pair.

14. The system of claim 13, the processor being further configured to:

optimize identification of interest point s1'"'"'s adjacent neighbors that are not adjacent neighbors of the k-nearest interest points by utilizing a graph which contains mappings between each interest point sk in the ordered list and each interest point that sk is referencing and each interest point that is referencing sk in the list; and

optimize identification of interest point s2'"'"'s adjacent neighbors that are not in the second partition by utilizing a graph which contains mappings between each interest point sk in the ordered list and each interest point that sk is referencing and each interest point that is referencing sk in the list.

15. The system of claim 14, the graph being implemented by using a reference pointer in the memory of a computer readable medium, the reference pointer being stored in one element in the ordered list and point to another element in list to represent the relationship in the Voronoi diagram of two interest points in the ordered list.

16. The system of claim 12, when interest points s1 and s2 are not in the second partition, the processor being further configured to:

transmit the first partition to the querying device.

17. The system of claim 12, the query computing device being the same as the querying device.

18. The system of claim 12, the processor further configured to:

use pointers in the memory of the computer readable medium to maintain the linking between each split point in the min-heap data structure and each corresponding two interest points in the ordered list used to generate each respective split point.

19. The system of claim 12, the termination condition comprising one of the following situations:

the reference point becomes a split point or a specified point in the trajectory path;

or the min-heap data structure is empty.

20. The system of claim 12, an interest point being at least one of a hospital, medical office, restaurant, gas station, landmark, hotel, structure, service provider, vendor, retailer, store, or any combination thereof.