Granted Patent B2

US 12,659,689 · App. 18/061,112 · Granted Jun 16, 2026

Inventors: Tae-Sun Chung (Seongnam-si, KR); Aavash Bhandari (Suwon-si, KR)

Assignee: Ajou University Industry-Academic Cooperation Foundation

H04W4/021G06F16/29G06F16/9027G06F16/909G06F16/9537G06Q30/0205H04W4/029

Abstract

Claims (38)

1 . A method of providing a location-based service (LBS), the method comprising:

according to an LBS request signal received from a plurality of user terminals, generating query objects based on location information of the plurality of user terminals; searching for at least one data object located within a threshold radius of one of the plurality of user terminals;

generating a cluster including the query objects corresponding to a node sequence, wherein the query objects are defined into two classes:

boundary query objects, each of which is located at a boundary, and

an inner query object, which is located between the boundary query objects;

determining first data objects, among the at least one data object, for the boundary query objects based on a nearest neighbor (NN) algorithm;

determining a second data object for the inner query object, the second data object being assigned as one of the first data objects whose corresponding boundary query object is nearest to the inner query object;

calculating a first distance from the inner query object to the assigned second data

object, the first distance being calculated by adding a second distance and a first length for a first condition, wherein the second distance is the shortest-path distance between the second data object and the corresponding boundary query object, and wherein the first length is a distance of a line segment connecting the corresponding boundary query object and the inner query object, wherein the first condition is defined such that the assigned second data object is a member of a set of data objects closest to one of the boundary query objects; and

transmitting the first data objects, the second data object and the first distance to respective user terminals,

wherein determining the second data object comprises:

identifying a number of query objects included in the query object cluster;

when the identified query object includes a plurality of query objects, calculating partial join result sets for each of the plurality of query objects; and performing a union on the calculated partial join result sets to calculate the nearest neighbor, and

wherein generating the query objects comprises:

acquiring a snapshot of a road network within a threshold radius based on a location of one of the plurality of user terminals according to the LBS request signal.

2 . The method of claim 1 , wherein generating the cluster comprises:

searching a road network of a road on which one of the plurality of user terminals is located; and

generating one or more node clusters based on an intermediate node other than an intersection node or an end node according to a result of searching the road network.

3 . The method of claim 2 , wherein generating the cluster further comprises:

grouping the query objects located in the same node cluster among the node clusters, to generate a query object cluster.

4 . The method of claim 1 , wherein each of the first data objects and the second data object corresponds to a vehicle terminal.

5 . An apparatus for providing a location-based service (LBS), the apparatus comprising:

a communication unit configured to receive an LBS request signal from a plurality of user terminals; and

a control unit configured to:

generate query objects based on location information of the plurality of user terminals, search for at least one data object located within a threshold radius of one of the plurality of user terminals,

generate a cluster including the query objects corresponding to a node sequence, wherein the query objects are defined into two classes:

boundary query objects, each of which is located at a boundary, and

an inner query object, which is located between the boundary query objects, determine first data objects, among the at least one data object, for the boundary query objects based on a nearest neighbor (NN) algorithm,

determine a second data object for the inner query object, the second data object being assigned as one of the first data objects whose corresponding boundary query object is nearest to the inner query object,

calculate a first distance from the inner query object to the assigned second data object, the first distance being calculated by adding a second distance and a first length for a first condition, wherein the second distance is the shortest-path distance between the second data object and the corresponding boundary query object, and wherein the first length is a distance of a line segment connecting the corresponding boundary query object and the inner query object wherein the first condition is defined such that the assigned second data object is a member of a set of data objects closest to one of the boundary query objects, and

transmit, through the communication unit, the first data objects, the second data object and the first distance to respective user terminals, wherein the control unit is further configured to,

identify a number of query objects included in the query object cluster,

when the identified query object includes a plurality of query objects, calculate partial join result sets for each of the plurality of query objects; and

perform a union on the calculated partial join result sets to calculate the nearest neighbor, and

wherein the control unit is further configured to acquire a snapshot of a road network within a threshold radius based on a location of one of the plurality of user terminals according to the LBS request signal.

6 . The apparatus of claim 5 , wherein the control unit is further configured to search a road network of a road on which one of the plurality of user terminals is located, and to generate one or more node clusters based on an intermediate node other than an intersection node or an end node.

7 . The apparatus of claim 6 , wherein the control unit is further configured to group the query objects located in the same node cluster among the node clusters, and to generate a query object cluster.

8 . The apparatus of claim 5 , wherein each of the first data objects and the second data object corresponds to a vehicle terminal.

Assignments (1)

Priority Claims (1)

Continuity (1)

References Cited (37)