公开(公告)号：US10412544B1

公开(公告)日：2019-09-10

申请号：US16266479

申请日：2019-02-04

申请人： Jing Tong

发明人： Mingjin Zhang ,  Naphtali Rishe ,  Weitong Liu ,  Jahkell Lazarre ,  Tao Li

IPC分类号： H04W24/00 ,  H04W4/021 ,  H04W4/029 ,  H04W4/02

摘要： Devices and methods for providing Voronoi diagram-based progressive continuous range query (CRQ) computation for location-based services are provided. A method can include indexing all interest points using a Voronoi R-tree data structure in a server-side computing device. When a client mobile device sends a CRQ request, the server-side device receives a path of travel and builds a list to store interest points and a min-heap to store split points, iteratively retrieving split points from the min-heap, and reporting the CRQ result progressively until a termination condition is reached.

公开(公告)号：US10346477B1

公开(公告)日：2019-07-09

申请号：US15945255

申请日：2018-04-04

申请人： Mingjin Zhang ,  Naphtali Rishe ,  Jahkell Lazarre ,  Jing Tong

发明人： Mingjin Zhang ,  Naphtali Rishe ,  Jahkell Lazarre ,  Tao Li

IPC分类号： G06F16/901 ,  G06F16/9038 ,  G06N20/00

摘要： Systems and methods for performing a mobile range query are provided. A system can include a first computer readable medium configured to iteratively transmit a mobile range query, as well as a second computer readable medium configured to: receive a mobile range query; compute a range query result; build two min-heaps that contain in-border interest points and out-border intersect points respectively; construct an initial candidate safe region by popping top elements in the two min-heaps while they are not empty; computing the intersections of the domain region of the top elements and the candidate safe region and redefining the candidate safe region using the intersections; and return the mobile range query results to the first medium.

公开(公告)号：US10331753B1

公开(公告)日：2019-06-25

申请号：US15945222

申请日：2018-04-04

申请人： Jing Tong

发明人： Mingjin Zhang ,  Naphtali Rishe ,  Weitong Liu ,  Jahkell Lazarre ,  Tao Li

IPC分类号： G06F16/9537 ,  G06F16/29 ,  G06K9/62 ,  H04W4/02

摘要： 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.