CN103365983B - Obtain level partition method and the system of the most farthest single neighbours on road network - Google Patents

Abstract

The present invention provides a hierarchical partition tree method and system for acquiring single reverse farthest neighbors on the road network, comprising: pushing all partitions of the hierarchical partition tree into a traversal queue, and popping up each partition or sub-partition in turn from the traversal queue SG _i , judge whether each sub-partition SG _i makes If so, then the nodes in SG _i Exclude this sub-section from the queue, if not, push the sub-section SG _i of the unexcluded sub-section or the sub-section without sub-section itself into the traversal queue, and pop up the traversal queue of each sub-section in turn from the traversal queue sub-partition SG _i , and repeat the above judgment until only sub-partitions or sub-partitions without sub-partitions are left in the traversal queue, and check whether the farthest neighbor of node d∈P in each non-excluded partition is q , if yes, determine d to be p, p∈MRFN(q,P). The invention can quickly search for the single-reverse neighbors of the query point on the road network.

Description

Hierarchical partition method and system for obtaining single reverse farthest neighbors on road network

technical field

The invention relates to a hierarchical partitioning method and system for obtaining single-reverse farthest neighbors on a road network.

Background technique

A spatial database (spatial database) refers to a database that provides spatial data types (spatial databasetype, SDT) and corresponding implementation support (see literature 1: Güting R H. An introduction to spatial database systems [J]. The VLDB Journal, 1994, 3 (4):357-399). With the increasing development of mobile computing and cloud computing, the application of spatial correlation algorithms is increasing. Proximity query includes Nearest Neighbor query, Reverse Nearest Neighbor query, Reverse Furthest Neighbor query, etc. It is one of the most common types of spatial database queries . The present invention focuses on the reverse furthest neighbor (RFN) query on the road network database, that is, given a set of data sets P and query sets Q on the road network, we hope to obtain all the Q is farther away than q. According to whether P and Q are the same, the problem can be divided into single reverse farthest neighbor problem and multiple reverse farthest neighbor problem. This problem has great practical significance, for example, when opening a new store, we want to know the point that is least affected by a certain competitor. If we represent the degree of influence between different locations as weighted edges, this problem is equivalent to the single-reverse farthest neighbor problem on the road network with the existing merchant location as the query point. Furthermore, finding a point that is relatively least affected by all existing competitors can be transformed into a problem of maximizing the number of complex reverse farthest neighbors of the target point on this road network with the competitor's location as the query set Q.

As far as we know, the only solution to the single reverse furthest neighbor problem on the road network is Tran et al.’s research on the reverse furthest neighbor on the road network. The process establishes a Voronoi partition, and then traverses the partition using the adjacency property of the partition to enumerate the possible reverse furthest neighbors of the query point. However, when the number of interest points in the road network is large, this method will not be substantially different from the brute force algorithm. However, there is no solution to the complex inverse furthest neighbor problem.

In terms of other related research, the most notable one is the nearest neighbor problem (see Document 2, Document 3: Hjaltason GR, Samet H. Distance browsing in spatial databases [J]. ACM Transactions on Database Systems (TODS) ,1999,24(2):265-318, Literature 4: Berchtold S, C, Keim DA, etc. A cost model for nearest neighbor search inhigh-dimensional data space [A]. In Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems [C], 1997:78-86, Document 5, Document 6: Jagadish H, Ooi BC, Tan KL, etc. iDistance: An adaptive B+-tree based indexing method for nearest neighbor search [J]. ACM Transactions on DatabaseSystems (TODS), 2005,30(2):364 -397, Literature 7: Tao Y, Papadias D, Shen Q.Continuous nearest neighbor search[A].In Proceedings of the 28th international conference on Very Large Data Bases[C],2002:287-29) and reverse nearest neighbor (see Literature 8: Korn F, Muthukrishnan S. Influence sets based on reverse nearest neighbors[J]. ACM SIGMOD Record, 2000, 29(2): 201-212, Literature 9: Singh A, FerhatosmanogluH, Tosun A High dimensional reverse nearest neighbor queries[A].InProceedings of the twelfth international conference on Information and knowledge management[C],2003:91-98, Literature 10:Tao Y,Papadias D,Lian X.Reverse kNNsearch in arbitrary dimensionality[A] .In Proceedings of the Thirtiethinternational conference on Very large data bases-Volume 30[C],2004:744-755, Literature 11: Achtert E, C, P,etc.Efficient reverse k-nearest neighborsearch in arbitrary metric spaces[A].In Proceedings of the 2006ACM SIGMOD international conference on Management of data[C],2006:515-526, Literature 12: Sankaranarayanan J, Samet H.Distance oracles for spatial networks[A].In DataEngineering,2009.ICDE'09.IEEE 25th International Conference on[C],2009:652-663) problem. Depth based on R-Tree (see literature 13: Guttman AR-trees: a dynamic index structure for spatial searching [M]. ACM, 1984) (see literature 2: Roussopoulos N, Kelley S, Vincent F.Nearest neighbor queries[ A].In 1995:71-79) and breadth (see literature 5: Cui B,Ooi BC,Su J,etc.Contorting high dimensional data for efficient main memoryKNN processing[A].In Proceedings of the 2003ACM SIGMOD international conference on Management of data[C],2003:479-490) priority search, incremental Euclidean Restriction (Incremental Euclidean Restriction), incremental network expansion (Invremental Network Expansion, see literature 14: Papadias D, Zhang J, Mamoulis N, etc.Query processing inspatial network databases[A].In 2003:802-813) technology related to Voronoi diagram (refer to literature 8~12) is widely used to solve the corresponding problems of Euclidean space (Euclidean space) and road network, but due to the reverse The farthest neighbor problem does not have the local characteristics of the nearest neighbor problem, and these solutions are difficult to apply to the problem solved by the present invention.

The furthest neighbor problem in Euclidean space is described by Yao et al. (see literature 15: Yao B, Li F, Kumar P. Reverse furthest neighbors in spatial databases [A]. In 2009: 664-675). They proposed a progressive furthest cell (PFC) algorithm and a convex hull furthest cell algorithm to deal with this problem. The above algorithms are all based on the concept of the farthest Voronoi go to determine whether a point is the reverse farthest neighbor of the query point q. Given a certain query point q, its farthest Voronoi region fvc(q,Q) with respect to a certain data set Q is a polygonal region, and all points in this region are the reverse farthest neighbors of q. The PFC algorithm uses the R-Tree index to continuously take data points to build a vertical bisector to explain space segmentation and take the far side to find this area. The CHFC algorithm uses the nature of the convex hull to prune this algorithm: if q is in the convex hull of the query set Q, the problem must be unsolvable, otherwise the search range can be limited to the convex hull of Q and the query point q within. Liu et al. improved this algorithm using pivot points and indexes (see literature 16: Liu J, Chen H, Furuse K, etc. An efficient algorithm for reverse furthest neighbors query with metric index[A].InDatabase and Expert Systems Applications[C], 2010:437-451, Literature 17: JianquanL. Efficient query processing for distance-based similarity search[J].2012). However, since the points on the road network have no direct relationship with the R-Tree index, and there is no strictly defined convex hull, these methods cannot be directly applied to the problems solved by the present invention.

Other relevant references include:

Literature 18: Goldberg A V, Harrelson C. Computing the shortest path: A searchmeets graph theory [A]. In Proceedings of the sixteenth annual ACM-SIAMsymposium on Discrete algorithms [C], 2005:156-165;

Literature 19: Jing N, Huang Y-W, Rundensteiner E A. Hierarchical encoded pathviews for path query processing: An optimal model and its performance evaluation [J]. Knowledge and Data Engineering, IEEE Transactions on, 1998, 10(3): 409-432 ;

Literature 20: Erwig M, Hagen F. The graph Voronoi diagram with applications [J]. Networks, 2000, 36(3): 156-163;

Document 21: Jung S, Pramanik S. An efficient path computation model for hierarchically structured topographical road maps [J]. Knowledge and Data Engineering, IEEE Transactions on, 2002, 14(5): 1029-1046;

Document 22: Aurenhammer F.Voronoi diagrams—a survey of a fundamentalgeometric data structure[J].ACM Computing Surveys(CSUR),1991,23(3):345-405.

Contents of the invention

The purpose of the present invention is to provide a hierarchical partitioning method and system for obtaining single-reverse farthest neighbors on the road network, which can quickly search for the single-reverse neighbors of the query point on the road network.

In order to solve the above-mentioned problems, the present invention provides a hierarchical partitioning method for obtaining the single reverse farthest neighbor on the road network, including:

Step 1: For a given node p on the road network G and all nodes V _G on the road network G, if there is a node q on the road network G, the road network distance between q and p ||qp|| is not less than the distance ||p′-p|| from p to any point p’ in V _G , then define q as the furthest neighbor of p relative to V _G , denoted as fn(p, V _G );

Step 2: For all nodes V _G on a given road network G, define the single-reverse farthest neighbor of q to be the set of q as the farthest neighbor point in V _G , that is, MRFN(q, V _G )={p| p∈V _G , fn(p,V _G ∪{q})=q};

Step 3: Use the top-down method to construct the hierarchical partition tree of the road network G. The nodes in the road network G are divided into m partitions SG _i , and each partition is recursively divided into several sub-partitions SG _i until Reach the required number of partitions and layers;

Step 4: Define the boundary nodes of each subdivision or subdivision SG _i on the road network G as Where edge(d,d') represents the edge between d and d', Represents all nodes of the partition SG _i ;

Step 5: Define the upper and lower bounds from a node q to a partition or sub-partition SG _i as q to The maximum and minimum distances of any node in , denoted as and The diameter of a partition or subpartition SG _i is defined as Similarly, the upper and lower bounds from node q to node d are defined as and

Step 6: Define the farthest upper bound and farthest lower bound of a partition or sub-partition SG _i as arbitrary The maximum and minimum distances to its furthest neighbors on the road network G are denoted as and Similarly define the distance from a node u to its furthest neighbor on the road network G as fub _u and flb _u ;

Step 7: Pre-calculate the distance between the border nodes of the sub-partition SG _i in a certain partition SG _i , and pre-calculate the respective farthest neighbors f of all border nodes on the road network G and the respective partitions and sub-partitions of all border nodes the furthest neighbor within SG _i ;

Step 8: select a plurality of nodes L of the road network as landmarks, and use the Dijkstra algorithm to pre-calculate the distance from each node L to the remaining sub-divisions or all nodes on the sub-divisions;

Step 9: Estimate the lower bound of the distance from node d in each partition or sub-partition SG _i to its furthest neighbor on the road network G, for $\∀d\∈V_{{\mathrm{SG}}_i},\∀b\∈{\mathrm{bd}}_{{\mathrm{SG}}_i},\∀f\∈V_G,$ Have $\left|\right|b-f\left|\right|-{\mathrm{ub}}_{{\mathrm{SG}}_i}^b\≤\left|\right|d-f\mathrm{no}(d,V_G)\left|\right|,$ in Calculate the maximum value of g(b, f) in each partition or subpartition SG _i as the value of the partition or subpartition SG _i

Step 10: Push all the partitions of the hierarchical partition tree into a traversal queue, pop up each partition or sub-partition SG _i from the traversal queue in turn, and judge whether each sub-partition SG _i makes If so, then the nodes in SG _i Exclude this subdivision from the road network G, if not, push the subdivision SG _i of the unexcluded subdivision or the subdivision without subdivision itself into the traversal queue, pop each subdivision sequentially from the traversal queue Sub-partition SG _i of the partition, and repeat the above judgment until there are only partitions or sub-partitions without sub-partitions left in the traversal queue, wherein, the calculation The steps are as follows, when and when when , since any path from q to SG _i must pass through the border nodes of SG _i Use q to to estimate the upper bound of but in, is estimated using the triangle inequality, The definition is the same as is obtained from the distances of all the boundary nodes in the pre-calculation and the farthest neighbors in the respective partitions and sub-partitions SG _i ;

Step 11: For each sub-partition or node d on the sub-partition, use the triangle inequality to check whether the distance ||d-q|| must be less than the distance from d to the farthest landmark from d ||d-f ||, if there are landmarks u and f in the node L, so that ||d-u||+||u-q||<||d-f||, then q must not be the farthest neighbor of d, so d must not be the opposite of q To the farthest neighbor, exclude the node d from the remaining partitions or subpartitions without subpartitions;

Step 12: Check whether the furthest neighbor of each unexcluded d∈V _G is q, if yes, determine d to be p, p∈MRFN(q, V _G ), if not, exclude d.

Further, in the above method, in step eight, the selected landmarks are evenly distributed on the road network G.

Further, in the above method, in the step of recursively dividing each partition into several sub-partitions SG _i in step 3, each partition is recursively divided into several sub-partitions SG _i using the Erwig and Hagen algorithm.

Further, in the above method, said step 12 includes:

Step twelve one: define the upper bound and the lower bound of a certain node d to a certain partition or sub-partition SG _i as d to The maximum and minimum distances of any node in , denoted as and The diameter of a partition or subpartition SG _i is defined as Similarly, the upper and lower bounds from node d to node d′ are defined as and

Step twelve two: when and when when , since any path from d to SG _i must pass through the border nodes of SG _i use d to to estimate the upper bound of but in, can be estimated using the triangle inequality, while is obtained from the farthest neighbors of all the pre-calculated boundary nodes in their respective partitions and sub-partitions SG _i , The definition is the same as

Step 123: Establish a partition SG _i and node d' and A priority queue stored in descending order, and all partitioned push into the queue;

Step 124: each time the first one is popped up from the priority queue or If the popup is Then go to step 126, if the pop-up is if Then the farthest neighbor of d cannot be in SG _{i ,} and exclude this partition SG _i from the road network G _; Partitioned Push back the priority queue in descending order, if none, then call step 12;

Step twelve five: calculate each The distance from all nodes d′ to d in the corresponding partition or subpartition SG _i and put all Push back the priority queue in descending order, and call step 126;

Step twelve six: Pop the first few from the priority queue put the first few The corresponding d' is determined as q, q∈fn(p, V _G ).

Further, in the above method, each The distance from all nodes d′ to d in the corresponding partition or subpartition SG _i The steps include:

like Perform a Dijkstra algorithm with d as the source point to obtain the distance from d to all nodes d' in the partition or subpartition SG _i

like due to anything from d to All paths must pass through the boundary nodes of the partition or subpartition SG _i Construct a retaining d and The shortcut subgraph G' of the distance between them, and the distance calculation is performed on the shortcut subgraph G' to obtain the distance from d to all nodes d' in the partition or subpartition SG _i

Further, in the above method, construct a reserved d and In the step of the short-cut subgraph G′ of the distance between two steps, HEPV and HiTi technologies are used.

Further, in the above method, construct a reserved d and boundary nodes In the step of the short-cut subgraph G′ of the inter-distance, all boundary nodes are pre-saved Use the partition SG _i where d is located and the pre-saved distance between the two partition boundary nodes to construct a shortcut subgraph G′.

According to another aspect of the present invention, there is provided a hierarchical partitioning system for acquiring single reverse farthest neighbors on a road network, including:

The first definition module is used for a given node p on the road network G and all nodes V _G on the road network G, if there is a node q on the road network G, the road network distance between q and p| |qp||is not less than the distance from p to any point p' in V _G ||p′-p||, then define q as the furthest neighbor of p relative to V _G , and denote it as fn(p, V _G );

The second definition module, for all nodes V _G on the given road network G, the single-reverse farthest neighbor of q is defined as the set of q as the farthest neighbor point in V _G , that is, MRFN(q, V _G )={ p|p∈V _G , fn(p,V _G ∪{q})=q};

The hierarchical partition module is used to construct a hierarchical partition tree of the road network G using a top-down method. The nodes in the road network G are divided into m partitions SG _i , and each partition is recursively divided into several sub-partitions SG _i , until the required number of partitions and layers is reached;

The boundary node module is used to define the boundary node of each subdivision or subdivision SGi on the road network G as Where edge(d,d') represents the edge between d and d', Represents all nodes of the partition SG _i ;

The first upper and lower bound module is used to define the upper bound and lower bound from a certain node q to a certain partition or sub-partition SG _i as q to The maximum and minimum distances of any node in , denoted as and The diameter of a partition or subpartition SG _i is defined as Similarly, the upper and lower bounds from node q to node d are defined as and

The second upper and lower bound module is used to define the farthest upper bound and the farthest lower bound of a partition or sub-partition SG _i as arbitrary The maximum and minimum distances to its furthest neighbors on the road network G are denoted as and Similarly define the distance from a node u to its furthest neighbor on the road network G as fub _u and flb _u ;

The pre-calculation module is used to pre-calculate the distance between the boundary nodes of the sub-division SG _i in a certain sub-division SG _i , and pre-calculate the respective farthest neighbors f of all boundary nodes on the road network G and the respective locations of all boundary nodes the furthest neighbors within the partition and subpartition SG _i ;

The distance module is used to select a plurality of nodes L on the road network as landmarks, and uses the Dijkstra algorithm to pre-calculate the distance from each node L to the remaining partitions without sub-regions or all nodes on the sub-regions;

The estimation module is used to estimate the lower bound of the distance from node d in each partition or sub-partition SG _i to its furthest neighbor on the road network G, for $\&ForAll;d\&Element;V_{{\mathrm{SG}}_i},\&ForAll;b\&Element;{\mathrm{bd}}_{{\mathrm{SG}}_i},\&ForAll;f\&Element;V_G,$ Have $\left|\right|b-f\left|\right|-{\mathrm{ub}}_{{\mathrm{SG}}_i}^b\&le;\left|\right|d-f\mathrm{no}(d,V_G)\left|\right|,$ in Calculate the maximum value of g(b, f) in each partition or subpartition SG _i as the value of the partition or subpartition SG _i

The queue module pushes all partitions of the hierarchical partition tree into a traversal queue, pops up each partition or sub-partition SG _i from the traversal queue in turn, and judges whether each sub-partition SG _i makes If so, then the nodes in SG _i Exclude this subdivision from the road network G, if not, push the subdivision SG _i of the unexcluded subdivision or the subdivision without subdivision itself into the traversal queue, pop each subdivision sequentially from the traversal queue Sub-partition SG _i of the partition, and repeat the above judgment until there are only partitions or sub-partitions without sub-partitions left in the traversal queue, wherein, the calculation The steps are as follows, when and when when , since any path from q to SG _i must pass through the border nodes of SG _i Use q to to estimate the upper bound of but in, is estimated using the triangle inequality, The definition is the same as is obtained from the distances of all the boundary nodes in the pre-calculation and the farthest neighbors in the respective partitions and sub-partitions SG _i ;

The node exclusion module is used to check whether the distance ||d-q|| must be less than the distance from d to the farthest landmark from d for each of the remaining partitions without sub-partitions or node d on the sub-partition. ||d-f||, if there are landmarks u and f in the node L, so that ||d-u||+||u-q||<||d-f||, then q must not be the farthest neighbor of d, so d must not The reverse farthest neighbor of q excludes the node d from the remaining partition or subpartition without subpartitions;

The checking module is used to check whether the furthest neighbor of each unexcluded d ∈ V _G is q, if yes, then determine d to be p, p ∈ MRFN(q, V _G ), if not, then d is excluded .

Further, in the above system, the landmarks selected by the distance module are evenly distributed on the road network G.

Further, in the above system, the hierarchical partitioning module uses the Erwig and Hagen algorithm to recursively divide each partition into several sub-partitions SG _i .

Further, in the above system, the inspection module includes:

The first upper and lower bound unit is used to define the upper bound and lower bound from a certain node d to a certain partition or sub-partition SG _i as d to The maximum and minimum distances of any node in , denoted as and The diameter of a partition or subpartition SG _i is defined as Similarly, the upper and lower bounds from node d to node d′ are defined as and

Estimation unit, used when and when when , since any path from d to SG _i must pass through the border nodes of SG _i use d to to estimate the upper bound of but in, can be estimated using the triangle inequality, while is obtained from the farthest neighbors of all the pre-calculated boundary nodes in their respective partitions and sub-partitions SG _i , The definition is the same as

Queue unit, used to establish a partition SG _i and node d' and A priority queue stored in descending order, and all partitioned push into the queue;

The partition exclusion unit is used to pop the first one from the priority queue each time or If the popup is Then call the farthest neighbor unit, if the pop-up is if Then the farthest neighbor of d cannot be in SG _{i ,} and exclude this partition SG _i from the road network G _; Partitioned Push back the priority queue in descending order, if none, call the computing unit;

Computing unit for computing each The distance from all nodes d′ to d in the corresponding partition or subpartition SG _i and put all Depress the priority queue in descending order and call the furthest neighbor unit;

furthest neighbor unit for popping the first few from the priority queue from put the first few The corresponding d' is determined as q, q∈fn(p, V _G ).

Further, in the above system, the computing unit is used for:

like Perform a Dijkstra algorithm with d as the source point to obtain the distance from d to all nodes d' in the partition or subpartition SG _i

like due to anything from d to All paths must pass through the boundary nodes of the partition or subpartition SG _i Construct a retaining d and The shortcut subgraph G' of the distance between them, and the distance calculation is performed on the shortcut subgraph G' to obtain the distance from d to all nodes d' in the partition or subpartition SG _i

Further, in the above system, the calculation unit uses HEPV and HiTi technology to construct a reserved d and The short-cut subgraph G′ of the distance between

Further, in the above system, the calculation unit pre-saves all boundary nodes Use the partition SG _i where d is located and the pre-saved distance between the two partition boundary nodes to construct a shortcut subgraph G′.

Compared with the prior art, the present invention pre-calculates the distance between the boundary nodes of the sub-region SG _i in a certain sub-region SG _i , and simultaneously pre-calculates the respective farthest neighbors f and all boundary nodes of all boundary nodes on the road network G The furthest neighbors of each point in the partition and sub-partition SG _i ; estimate the lower bound of the distance from node d in each partition or sub-partition SG _i to its furthest neighbor on the road network G, for Have $\left|\right|b-f\left|\right|-{\mathrm{ub}}_{{\mathrm{SG}}_i}^b\&le;\left|\right|d-\mathrm{fn}(d,V_G)\left|\right|,$ in $g(b,f)=\left|\right|b-f\left|\right|-{\mathrm{ub}}_{{\mathrm{SG}}_i}^b,$ Calculate the maximum value of g(b,f) in each partition or subpartition SGi as the value of the partition or subpartition _SGi Push all the partitions of the hierarchical partition tree into a traversal queue, pop up each partition or sub-partition SG _i from the traversal queue in turn, and judge whether each sub-partition SG _i makes If so, then the nodes in SG _i Exclude this subdivision from the road network G, if not, push the subdivision SG _i of the unexcluded subdivision or the subdivision without subdivision itself into the traversal queue, pop each subdivision sequentially from the traversal queue Sub-partition SG _i of the partition, and repeat the above judgment until there are only partitions or sub-partitions without sub-partitions left in the traversal queue, wherein, the calculation The steps are as follows, when and when when , since any path from q to SG _i must pass through the border nodes of SG _i Use q to to estimate the upper bound of but in, is estimated using the triangle inequality, The definition is the same as is obtained from the distances of all the pre-calculated boundary nodes and the farthest neighbors in the respective partitions and sub-partitions SGi; Use the triangle inequality to check whether the distance ||dq|| must be less than the distance from d to the farthest landmark ||df||, if there are landmarks u and f in the node L, so that ||du||+||uq| |<||df||, then q must not be the farthest neighbor of d, so d must not be the reverse farthest neighbor of q, and the node d is excluded from the remaining sub-partition or sub-partition ; Check whether the furthest neighbor of each unexcluded d∈V _G is q, if yes, determine d to be p, p∈MRFN(q, V _G ), if not, exclude d The single reverse neighbor of the query point can be quickly searched online.

Description of drawings

Fig. 1 is a single reverse farthest neighbor problem MRFN example diagram of an embodiment of the present invention;

Fig. 2 is the division example of the HP tree of an embodiment of the present invention;

Fig. 3 is the HP tree structure corresponding to Fig. 3 of an embodiment of the present invention;

Fig. 4 is the performance of the HP algorithm on the CA database of an embodiment of the present invention;

Fig. 5 is the performance of the HP algorithm on the SF database according to an embodiment of the present invention.

detailed description

In order to make the above objects, features and advantages of the present invention more comprehensible, the present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

Embodiment one

The present invention provides a hierarchical partition (Hierarchical Partition, HP) method for acquiring single reverse farthest neighbors on a road network, including step 1 to step 12.

Step 1: For a given node p on the road network G and all nodes VG on the road network G, if there is a node q on the road network G, the road network distance between q and p ||qp|| is less than the distance ||p′-p|| from p to any point p’ in V _G , then define q as the furthest neighbor of p relative to V _G , denoted as fn(p, V _G );

Step 2: For all nodes VG on the given road network G, define the single-reverse farthest neighbor of q as the set of q as the farthest neighbor point in VG, that is, MRFN(q, V _G )={p|p∈ V _G ,fn(p,V _G ∪{q})=q}; Specifically, as shown in Figure 1, p ₁ is the farthest neighbor of p ₇ , so p ₇ is one of the reverse farthest neighbors of p ₁ one. This problem has great practical significance, for example, when opening a new store, we want to know the point that is least affected by a certain competitor. If we represent the degree of influence between different locations as weighted edges, this problem is equivalent to finding the reverse farthest neighbor problem on the road network with the existing merchant location as the query point. Furthermore, finding a point that is relatively least affected by all existing competitors can be transformed into a problem of maximizing the number of complex reverse farthest neighbors of the target point on this road network with the competitor's location as the interest set Q. The present invention aims to effectively calculate the reverse furthest neighbor (Reverse Farthest Neighbor) problem on the road network by using the relevant technology.

Step 3: Use the top-down method to construct the hierarchical partition tree of the road network G, that is, the HP tree. The nodes in the road network G are divided into m partitions SG _i , and each partition is recursively divided into several sub-partitions SG _i , until the required number of partitions and layers is reached;

Preferably, in the step of recursively dividing each partition into several sub-partitions SG _i in step 3, each partition is recursively divided into several sub-partitions SG _i using the Erwig and Hagen algorithm.

Step 4: Define the boundary nodes of each subdivision or subdivision SG _i on the road network G as Where edge(d,d') represents the edge between d and d', Represents all nodes of the partition SG _i ;

Step 5: Define the upper and lower bounds from a node q to a partition or sub-partition SG _i as q to The maximum and minimum distances of any node in , denoted as and The diameter of a partition or subpartition SG _i is defined as Similarly, the upper and lower bounds from node q to node d are defined as and

Step 6: Define the farthest upper bound and farthest lower bound of a partition or sub-partition SG _i as arbitrary The maximum and minimum distances to its furthest neighbors on the road network G are denoted as and Similarly define the distance from a node u to its furthest neighbor on the road network G as fub _u and flb _u ;

Step 7: Pre-calculate the distance between the border nodes of the sub-partition SG _i in a certain partition SG _i , and pre-calculate the respective farthest neighbors f of all border nodes on the road network G and the respective partitions and sub-partitions of all border nodes the furthest neighbor within SG _i ;

Step 8: select a plurality of nodes L on the road network as landmarks, and use the Dijkstra algorithm to pre-calculate the distances from each node L to the remaining sub-divisions or sub-divisions;

Preferably, in step eight, the selected landmarks are evenly distributed on the road network G.

Step 9: Estimate the lower bound of the distance from node d in each partition or sub-partition SG _i to its furthest neighbor on the road network G, for $\&ForAll;d\&Element;V_{{\mathrm{SG}}_i},\&ForAll;b\&Element;{\mathrm{bd}}_{{\mathrm{SG}}_i},\&ForAll;f\&Element;V_G,$ Have $\left|\right|b-f\left|\right|-{\mathrm{ub}}_{{\mathrm{SG}}_i}^b\&le;\left|\right|d-f\mathrm{no}(d,V_G)\left|\right|,$ in Calculate the maximum value of g(b, f) in each partition or subpartition SG _i as the value of the partition or subpartition SG _i

Step 10: Push all the partitions of the hierarchical partition tree into a traversal queue, pop up each partition or sub-partition SG _i from the traversal queue in turn, and judge whether each sub-partition SG _i makes If so, then the nodes in SG _i Exclude this subdivision from the road network G, if not, push the subdivision SG _i of the unexcluded subdivision or the subdivision without subdivision itself into the traversal queue, pop each subdivision sequentially from the traversal queue Sub-partition SG _i of the partition, and repeat the above judgment until there are only partitions or sub-partitions without sub-partitions left in the traversal queue, wherein, the calculation The steps are as follows, when and when when , since any path from q to SG _i must pass through the border nodes of SG _i Use q to to estimate the upper bound of but in, is estimated using the triangle inequality, The definition is the same as is obtained from the distances of all the boundary nodes in the pre-calculation and the farthest neighbors in the respective partitions and sub-partitions SG _i ;

Step 11: For each sub-partition or node d on the sub-partition, use the triangle inequality to check whether the distance ||d-q|| must be less than the distance from d to the farthest landmark from d ||d-f ||, if there are landmarks u and f in the node L, so that ||d-u||+||u-q||<||d-f||, then q must not be the farthest neighbor of d, so d must not be the opposite of q To the farthest neighbor, exclude the node d from the remaining partitions or subpartitions without subpartitions;

Step 12: Check whether the furthest neighbor of each unexcluded d∈V _G is q, if yes, determine d to be p, p∈MRFN(q, V _G ), if not, exclude d.

Preferably, said step 12 includes:

Step twelve one: define the upper bound and the lower bound of a certain node d to a certain partition or sub-partition SG _i as d to The maximum and minimum distances of any node in , denoted as and The diameter of a partition or subpartition SG _i is defined as Similarly, the upper and lower bounds from node d to node d′ are defined as and

Step twelve two: when and when when , since any path from d to SG _i must pass through the border nodes of SG _i use d to to estimate the upper bound of but in, can be estimated using the triangle inequality, while is obtained from the farthest neighbors of all the pre-calculated boundary nodes in their respective partitions and sub-partitions SG _i , The definition is the same as

Step 123: Establish a partition SG _i and node d' and A priority queue stored in descending order, and all partitioned push into the queue;

Step 124: each time the first one is popped up from the priority queue or If the popup is Then go to step 126, if the pop-up is if Then the farthest neighbor of d cannot be in SG _{i ,} and exclude this partition SG _i from the road network G _; Partitioned Push back the priority queue in descending order, if none, then call step 12;

Step twelve five: calculate each The distance from all nodes d′ to d in the corresponding partition or subpartition SG _i and put all Push back the priority queue in descending order, and call step 126;

Step twelve six: Pop the first few from the priority queue put the first few The corresponding d' is determined as q, q∈fn(p, V _G ).

Preferably, in step twelve five, calculate each The distance from all nodes d′ to d in the corresponding partition or subpartition SG _i The steps include:

like Perform a Dijkstra algorithm with d as the source point to obtain the distance from d to all nodes d' in the partition or subpartition SG _i Specifically, as a representative shortest path algorithm, the Dijkstra algorithm was proposed by EW Dijkstra in 1959. The algorithm uses the marking method to start from the source point, and each time expands the point closest to the marked set, so as to obtain the shortest path of the known point ( See document 1);

like due to anything from d to All paths must pass through the boundary nodes of the partition or subpartition SG _i Construct a retaining d and The shortcut subgraph G' of the distance between them, and the distance calculation is performed on the shortcut subgraph G' to obtain the distance from d to all nodes d' in the partition or subpartition SG _i

Preferably, construct a reserved d and In the step of the short-cut subgraph G′ of the distance between two steps, HEPV and HiTi technologies are used.

Preferably, construct a retaining d and boundary nodes In the step of the short-cut subgraph G′ of the inter-distance, all boundary nodes are pre-saved Use the partition SG _i where d is located and the pre-saved distance between the two partition boundary nodes to construct a shortcut subgraph G′.

In detail, the access pattern of the MRFN query has strong locality, so the MRFN query can be efficiently processed through the partition method. Graph partitioning techniques have been widely studied in different fields since the 1970s. Most partitioning techniques can be used to process MRFN queries.

For the convenience of discussion, the following definitions are introduced:

Definition 4 We define the boundary nodes of a partition SG _i as

Where edge(p,p') represents the edge between p and p', R represents the road network, Represents the node set of partition SG _i .

Definition 5 The upper bound (lower bound) from a node p to a partition SG _i is defined as p to The maximum (minimum) distance of any node within . recorded as The radius of a certain partition SG _i is defined as We similarly define the upper bound (lower bound) from point p to point q as

Definition 6 The farthest upper bound (farthest lower bound) of a partition SG _i is defined as any The maximum (minimum) value of the distance to its furthest neighbor on the road network, denoted as Similarly, we define the distance from a node to its furthest neighbor on the road network as fub _p (flb _p ).

According to the above definition, the following lemma is introduced:

Lemma 1 If there is node q partition SG _i node make Then p cannot be the MRFN of q.

Prove that if p is the reverse farthest neighbor of q, since Have This is against the conditions.

Next, we discuss how to efficiently construct HP trees. Our construction method is based on HEPV technology [19] and network Voronoi diagram (graph voronoi diagram, see literature 20).

HP trees can be constructed using a top-down approach. We divide the nodes in the road network into m partitions, and recursively divide each partition into m sub-partitions until we reach the required number of partitions and layers. We use the Erwig and Hagen algorithm to divide a certain partition SG _i into m subpartitions (see reference 20). An example of an HP tree is shown in Figure 2 and Figure 3.

In order to perform the query we also need some auxiliary information. We pre-calculate the distance between the boundary nodes of the sub-partitions in a certain partition SG _i . These boundary nodes and the shortcuts between them form a subgraph, which is called the hypergraph of the partition SG _i . At the same time, we calculate the distances of all the boundary nodes The furthest neighbors and the furthest neighbors within the partition they are in.

Below we describe how to compute the relevant upper and lower bounds mentioned in Lemma 1.

From Definition 5, we know that is the upper bound of the distance from a node to a partition SG _i . to calculate We first look for the furthest neighbors of p within SG _i . when and when we have And when When , since any path from p to SG _i must pass through the border nodes of SG _i , we can use p to to estimate the upper bound of

${\mathrm{<span\; class="notranslate">\; ub</span>}}_{{\mathrm{<span\; class="notranslate">\; SG</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}^{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; max</span>}}_{\mathrm{<span\; class="notranslate">\; b</span>}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; bd</span>}}_{{\mathrm{<span\; class="notranslate">\; SG</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; ub</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}^{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; ub</span>}}_{{\mathrm{<span\; class="notranslate">\; SG</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}^{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; )</span>$

in can be estimated using the triangle inequality, while It is the precomputed information when building the HP tree.

to calculate We need to estimate a lower bound on the distances of nodes in SG _i to their furthest neighbors, and we introduce the following lemma:

Lemma 2 for $\&ForAll;p\&Element;V_{{\mathrm{SG}}_i},\&ForAll;b\&Element;{\mathrm{bd}}_{{\mathrm{SG}}_i},\&ForAll;f\&Element;V_G,$ Have

$<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; b</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; ub</span>}}_{{\mathrm{<span\; class="notranslate">\; SG</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}^{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; \&le;</span><span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; f</span>}\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>$

Proof: From the triangle inequality, we have ||bf||-||pb||≤||pf||. Meanwhile, from definition 5, if $b\&Element;V_{{\mathrm{SG}}_i},{\mathrm{ub}}_{{\mathrm{SG}}_i}^b\&Greater\; Equal;\left|\left|p-b\right|\right|,$ In summary, we have

$\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; b</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; b</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; ub</span>}}_{{\mathrm{<span\; class="notranslate">\; SG</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}^{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; \&le;</span><span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; b</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; b</span>}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span><span\; class="notranslate">\; \&le;</span><span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span><span\; class="notranslate">\; \&le;</span><span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; f</span>}\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>$

In order to obtain a larger We select a set of border nodes of SG _i and any node in G, and compute the maximum value of g(b,f). because Regardless of the query q, we can pre-compute all partitions when building the tree

Table 1

As shown in Table 1, this embodiment traverses the HP tree in breadth-first order, and for each visited partition SG _i , the algorithm tries to use Lemma 1 to perform pruning. If SG _i cannot be pruned, we push all subpartitions into the traversal queue For leaf partitions, we use the LM (Landmark) algorithm for processing.

Lemma 3 for if Have

p cannot be the furthest neighbor of u

Proof: by The definition of is easy to prove.

Table 2

As shown in Table 2, we compute f(q, G) and check whether p is in fn(q, G). Overall, we take descending order to traverse the partitions in the HP tree and use the aforementioned properties for pruning. If we reach the leaf partition of the HP tree, we calculate the distance from q to all nodes in the partition using the method described below, once the exact distance from a node to q is calculated beyond all remaining We can label this node as fn(q,G).

We use a priority queue that holds both nodes and partitions to implement the above algorithm. The element e in the queue starts with are stored in descending order. At each step we pop The first element in . If it is a part with subpartitions, we use Lemma 3 to prune and push back unpruned partitions when When the pop-up element is the leaf partition SG _i of the HP tree, we use the following method to calculate the distance from all nodes in the partition to the query q:

for We only need to perform Dijkstra's algorithm once with q as the source point to obtain the distance from q to all points. and for In the case of , due to any change from q to All paths must go through the partition of SG _i We can construct a preserving q and The "shortcut subgraph"G' of the distance between the two, and the distance calculation is performed on this smaller graph.

The method of constructing G' varies according to our strategy for building the HP tree. In the HP tree we described above, this task can be accomplished using both HEPV technology (see Ref. 19) and HiTi (Ref. 21) technology. In order to further speed up, we can pre-save the distance between all boundary points when _building a tree, so that we only need to use The desired result can be obtained by performing a Dijkstra operation on q as the source point.

After getting q to After the exact distance of , we combine all nodes' Set to the calculated result just obtained and re-press middle. When a node is accessed from We know that the distance from this node to q is greater than or equal to all other nodes, we only need to add all nodes with the same distance to fn(q, G), and terminate the algorithm. Checking whether p is in the obtained fn(q,G), we can return the result of isFN(p,q).

Can use C++ language based on a widely used, disk-based spatial index library (see: www.research.att.com/~marioh/spatialindex/index.html) to achieve all the steps of this embodiment, and use Intel Experiments were run in a Linux environment with a Xeon 2GHz processor and 4GB of memory. By default, 1000 calculations are run for each experiment and the average is reported. In terms of experimental data, this embodiment can use the real road network of California (California, CA) and San Francisco (San Francisco, SF) provided by Digital Chart of the World Server to conduct experiments. These data are available online (see http://www.cs.utah.edu/~lifeifei/SpatialDataset.htm). The CA database contains 21047 nodes and 21692 edges; the SF database contains 174955 nodes and 223000 edges. The CA and SF databases are used to test the performance of the MRFN algorithm on the road network. The query points are randomly selected from the road network, and 64 landmarks can be evenly selected on the map. In one embodiment, the performance performance of the HP tree under the configuration of 2 layers and 20 sub-partitions in each partition (441 sub-partitions in total) may be reported by default.

Two parameters may affect the performance of the HP algorithm: the number of total partitions (denoted as |HP|) and the depth of the HP tree. We show in Figures 4 and 5 the performance impact of these parameters on two different road networks, the CA and SF databases, respectively.

In theory, more partitions will provide better performance. This trend can be observed in Figures 4 and 5: when |HP|=420, the execution time of the algorithm is only one-tenth of |HP|=40. But when |HP| is large, it is difficult to further prune the newly added partitions, so further increasing |HP| is not effective.

In Figures 4 and 5, we can also compare the performance of HP trees with different layers. From the experimental data, we can see that when |HP| is small, HP trees with fewer layers perform better. However, trees with higher levels scale better as |HP| grows. This is mainly because when the number of layers is small, the leaf-level partitions are smaller, which can provide better performance when |HP| is small. When the number of layers is large, it is more likely to cut more partitions at one time, and it provides better performance when |HP| is larger: when |HP| is small, the parameters of one layer perform better. When |HP| is large, multi-layered trees perform better.

Embodiment two

The present invention also provides another hierarchical partitioning system for obtaining the single reverse farthest neighbor on the road network, including:

The first definition module is used for a given node p on the road network G and all nodes V _G on the road network G, if there is a node q on the road network G, the road network distance between q and p| |qp||is not less than the distance from p to any point p' in V _G ||p′-p||, then define q as the furthest neighbor of p relative to V _G , and denote it as fn(p, V _G );

The second definition module, for all nodes V _G on the given road network G, the single-reverse farthest neighbor of q is defined as the set of q as the farthest neighbor point in V _G , that is, MRFN(q, V _G )={ p|p∈V _G , fn(p,V _G ∪{q})=q};

The hierarchical partition module is used to construct a hierarchical partition tree of the road network G using a top-down method. The nodes in the road network G are divided into m partitions SG _i , and each partition is recursively divided into several sub-partitions SG _i , until the required number of partitions and layers is reached;

The boundary node module is used to define the boundary node of each subdivision or subdivision SG _i on the road network G as Where edge(d,d') represents the edge between d and d', Represents all nodes of the partition SG _i ;

The first upper and lower bound module is used to define the upper bound and lower bound from a certain node q to a certain partition or sub-partition SG _i as q to The maximum and minimum distances of any node in , denoted as and The diameter of a partition or subpartition SG _i is defined as Similarly, the upper and lower bounds from node q to node d are defined as and

The second upper and lower bound module is used to define the farthest upper bound and the farthest lower bound of a partition or sub-partition SG _i as arbitrary The maximum and minimum distances to its furthest neighbors on the road network G are denoted as and Similarly define the distance from a node u to its furthest neighbor on the road network G as fub _u and flb _u ;

The pre-calculation module is used to pre-calculate the distance between the boundary nodes of the sub-division SG _i in a certain sub-division SG _i , and pre-calculate the respective farthest neighbors f of all boundary nodes on the road network G and the respective locations of all boundary nodes the furthest neighbors within the partition and subpartition SG _i ;

The distance module is used to select a plurality of nodes L on the road network as landmarks, and use the Dijkstra algorithm to pre-calculate the distance from each node L to the remaining partitions without sub-regions or all nodes on the sub-regions;

The estimation module is used to estimate the lower bound of the distance from node d in each partition or sub-partition SG _i to its furthest neighbor on the road network G, for $\&ForAll;d\&Element;V_{{\mathrm{SG}}_i},\&ForAll;b\&Element;{\mathrm{bd}}_{{\mathrm{SG}}_i},\&ForAll;f\&Element;V_G,$ Have $\left|\right|b-f\left|\right|-{\mathrm{ub}}_{{\mathrm{SG}}_i}^b\&le;\left|\right|d-f\mathrm{no}(d,V_G)\left|\right|,$ in Calculate the maximum value of g(b, f) in each partition or subpartition SG _i as the value of the partition or subpartition SG _i

The queue module is used to push all the partitions of the hierarchical partition tree into a traversal queue, pop up each partition or sub-partition SG _i in turn from the traversal queue, and judge whether each sub-partition SG _i makes If so, then the nodes in SG _i Exclude this subdivision from the road network G, if not, push the subdivision SG _i of the unexcluded subdivision or the subdivision without subdivision itself into the traversal queue, pop each subdivision sequentially from the traversal queue Sub-partition SG _i of the partition, and repeat the above judgment until there are only partitions or sub-partitions without sub-partitions left in the traversal queue, wherein, the calculation The steps are as follows, when and when when , since any path from q to SG _i must pass through the border nodes of SG _i Use q to to estimate the upper bound of but in, is estimated using the triangle inequality, The definition is the same as is obtained from the distances of all the boundary nodes in the pre-calculation and the farthest neighbors in the respective partitions and sub-partitions SG _i ;

The node exclusion module is used to check whether the distance ||d-q|| must be less than the distance from d to the farthest landmark from d for each of the remaining partitions without sub-partitions or node d on the sub-partition. ||d-f||, if there are landmarks u and f in the node L, so that ||d-u||+||u-q||<||d-f||, then q must not be the farthest neighbor of d, so d must not The reverse farthest neighbor of q excludes the node d from the remaining partition or subpartition without subpartitions;

The checking module is used to check whether the furthest neighbor of each unexcluded d ∈ V _G is q, if yes, then determine d to be p, p ∈ MRFN(q, V _G ), if not, then d is excluded .

Preferably, the landmarks selected by the distance module are evenly distributed on the road network G.

Preferably, the hierarchical partitioning module uses Erwig and Hagen algorithm to recursively divide each partition into several sub-partitions SG _i .

Preferably, the inspection module includes:

The first upper and lower bound unit is used to define the upper bound and lower bound from a certain node d to a certain partition or sub-partition SG _i as d to The maximum and minimum distances of any node in , denoted as and The diameter of a partition or subpartition SG _i is defined as Similarly, the upper and lower bounds from node d to node d′ are defined as and

Estimation unit, used when and when when , since any path from d to SG _i must pass through the border nodes of SG _i use d to to estimate the upper bound of but in, can be estimated using the triangle inequality, while is obtained from the farthest neighbors of all the pre-calculated boundary nodes in their respective partitions and sub-partitions SG _i , The definition is the same as

Queue unit, used to establish a partition SG _i and node d' and A priority queue stored in descending order, and all partitioned push into the queue;

The partition exclusion unit is used to pop the first one from the priority queue each time or If the popup is Then call the farthest neighbor unit, if the pop-up is if Then the farthest neighbor of d cannot be in SG _{i ,} and exclude this partition SG _i from the road network G _; Partitioned Push back the priority queue in descending order, if none, call the computing unit;

Computing unit for computing each The distance from all nodes d′ to d in the corresponding partition or subpartition SG _i and put all Depress the priority queue in descending order and call the furthest neighbor unit;

furthest neighbor unit for popping the first few from the priority queue from put the first few The corresponding d' is determined as q, q∈fn(p, V _G ).

Preferably, the computing unit is used for:

like Perform a Dijkstra algorithm with d as the source point to obtain the distance from d to all nodes d' in the partition or subpartition SG _i

like due to anything from d to All paths must pass through the boundary nodes of the partition or subpartition SG _i Construct a retaining d and The shortcut subgraph G' of the distance between them, and the distance calculation is performed on the shortcut subgraph G' to obtain the distance from d to all nodes d' in the partition or subpartition SG _i

Preferably, the calculation unit uses HEPV and HiTi technology to construct a reserved d and The short-cut subgraph G′ of the distance between

Preferably, the calculation unit pre-saves all boundary nodes Use the partition SG _i where d is located and the pre-saved distance between the two partition boundary nodes to construct a shortcut subgraph G′.

For other details of the second embodiment, reference may be made to the first embodiment, which will not be repeated here.

The present invention pre-calculates the distance between the boundary nodes of the sub-section SG _i in a certain sub-section SG _i , and simultaneously pre-calculates the respective farthest neighbors f of all the boundary nodes on the road network G and the respective distances of all the boundary nodes in the sub-sections and sub-sections The furthest neighbor in SG _i ; estimate the lower bound of the distance from node d in each partition or sub-partition SG _i to its furthest neighbor on the road network G, for Have $\left|\right|b-f\left|\right|-{\mathrm{ub}}_{{\mathrm{SG}}_i}^b\&le;\left|\right|d-\mathrm{fn}(d,V_G)\left|\right|,$ in $g(b,f)=\left|\right|b-f\left|\right|-{\mathrm{ub}}_{{\mathrm{SG}}_i}^b,$ Calculate the maximum value of g(b, f) in each partition or subpartition SG _i as the value of the partition or subpartition SG _i Push all the partitions of the hierarchical partition tree into a traversal queue, pop up each partition or sub-partition SG _i from the traversal queue in turn, and judge whether each sub-partition SG _i makes If so, then the nodes in SG _i Exclude this subdivision from the road network G, if not, push the subdivision SG _i of the unexcluded subdivision or the subdivision without subdivision itself into the traversal queue, pop each subdivision sequentially from the traversal queue Sub-partition SG _i of the partition, and repeat the above judgment until there are only partitions or sub-partitions without sub-partitions left in the traversal queue, wherein, the calculation The steps are as follows, when and when when , since any path from q to SG _i must pass through the border nodes of SG _i Use q to to estimate the upper bound of but in, is estimated using the triangle inequality, The definition is the same as is obtained from the distances of all boundary nodes in the pre-calculation and the farthest neighbors in the partition and sub-partition SG _i respectively; , use the triangle inequality to check whether the distance ||dq|| must be less than the distance from d to the farthest landmark of d ||df||, if there are landmarks u and f in node L, such that ||du||+||uq ||<||df||, then q must not be the farthest neighbor of d, so d must not be the reverse farthest neighbor of q, and remove the node d from the remaining partition or subpartition without subpartitions Exclude; check whether the furthest neighbor of each unexcluded d ∈ V _G is q, if yes, then determine d as p, p ∈ MRFN(q, V _G ), if not, exclude d, can be in The single reverse neighbor of the query point is quickly searched on the road network.

Each embodiment in this specification is described in a progressive manner, each embodiment focuses on the difference from other embodiments, and the same and similar parts of each embodiment can be referred to each other. As for the system disclosed in the embodiment, since it corresponds to the method disclosed in the embodiment, the description is relatively simple, and for relevant information, please refer to the description of the method part.

Professionals can further realize that the units and algorithm steps of the examples described in conjunction with the embodiments disclosed herein can be implemented by electronic hardware, computer software or a combination of the two. In order to clearly illustrate the possible For interchangeability, in the above description, the composition and steps of each example have been generally described according to their functions. Whether these functions are executed by hardware or software depends on the specific application and design constraints of the technical solution. Those skilled in the art may use different methods to implement the described functions for each specific application, but such implementation should not be regarded as exceeding the scope of the present invention.

Obviously, those skilled in the art can make various changes and modifications to the invention without departing from the spirit and scope of the invention. Thus, if these modifications and variations of the present invention fall within the scope of the claims of the present invention and equivalent technologies thereof, the present invention also intends to include these modifications and variations.

Claims (14)

1. A hierarchical partitioning method for obtaining single reverse farthest neighbors on a road network, characterized in that it comprises: Step 1: For a given node p on the road network G and all nodes V _G on the road network G, if there is a node q on the road network G, the road network distance between q and p ||qp|| is not less than the distance ||p′-p|| from p to any point p′ in V _G , then define q as the farthest neighbor of p relative to V _G , denoted as fn(p, V _G ); Step 2: For all nodes V _G on a given road network G, define the single-reverse farthest neighbor of q to be the set of q as the farthest neighbor point in V _G , that is, MRFN(q, V _G )={p| p∈V _G , fn(p,V _G ∪{q})=q}; Step 3: Use the top-down method to construct the hierarchical partition tree of the road network G. The nodes in the road network G are divided into m partitions SG _i , and each partition is recursively divided into several sub-partitions SG _i until Reach the required number of partitions and layers; Step 4: Define the boundary nodes of each subdivision or subdivision SG _i on the road network G as Where edge(d,d') represents the edge between d and d', Represents all nodes of the partition SG _i ; Step 5: Define the upper and lower bounds from a node q to a partition or sub-partition SG _i as q to The maximum and minimum distances of any node in , denoted as and The diameter of a partition or subpartition SG _i is defined as Define the upper and lower bounds from node q to node d as and Step 6: Define the farthest upper bound and farthest lower bound of a partition or sub-partition SG _i as arbitrary The maximum and minimum distances to its furthest neighbors on the road network G are denoted as and Define the distance from a node u to its furthest neighbor on the road network G as fub _u and flb _u ; Step 7: Pre-calculate the distance between the border nodes of the sub-partition SG _i in a certain partition SG _i , and pre-calculate the respective farthest neighbors f of all border nodes on the road network G and the respective partitions and sub-partitions of all border nodes the furthest neighbor within SG _i ; Step 8: select a plurality of nodes L on the road network G as landmarks, and use the Dijkstra algorithm to pre-calculate the distance from each node L to the remaining sub-divisions or all nodes on the sub-divisions; Step 9: Estimate the lower bound of the distance from node d in each partition or sub-partition SG _i to its furthest neighbor on the road network G, for Have in Calculate the maximum value of g(b, f) in each partition or subpartition SG _i as the value of the partition or subpartition SG _i Step 10: Push all the partitions of the hierarchical partition tree into a traversal queue, pop up each partition or sub-partition SG _i from the traversal queue in turn, and judge whether each sub-partition SG _i makes If so, then the nodes in SG _i Exclude this subdivision from the road network G, if not, push the subdivision SG _i of the unexcluded subdivision or the subdivision without subdivision itself into the traversal queue, and pop each subdivision in turn from the traversal queue subpartition SG _i , and repeat the above judgment until there are only subpartitions or subpartitions without subpartitions left in the traversal queue, where the calculation The steps are as follows, when and when when , since any path from q to SG _i must pass through the border nodes of SG _i Use q to to estimate the upper bound of but in, Estimated using the triangle inequality, The definition is the same as is obtained from the distances of all the boundary nodes in the pre-calculation and the farthest neighbors in the respective partitions and sub-partitions SG _i ; Step 11: For each of the remaining partitions without subpartitions or node d on the subpartition, use the triangle inequality to check whether the distance ||d-q|| must be less than the distance from d to the furthest neighbor f of d || d-f||, if there are landmarks u and the farthest neighbor f in the node L, so that ||d-u||+||u-q||<||d-f||, then q must not be the farthest neighbor of d, so d must Not being the reverse farthest neighbor of q, exclude the node d from the remaining partition or subpartition without subpartitions; Step 12: Check whether the furthest neighbor of each unexcluded d∈V _G is q, if yes, determine d to be p, p∈MRFN(q, V _G ), if not, exclude d. 2. The hierarchical partitioning method for acquiring single-reverse farthest neighbors on the road network according to claim 1, characterized in that, in step eight, the selected landmarks are evenly distributed on the road network G. 3. The hierarchical partitioning method for obtaining single reverse farthest neighbors on the road network as claimed in claim 1, characterized in that, in the step 3, each partition is recursively divided into several sub-partitions SG _i , using Erwig and Hagen The algorithm recursively divides each partition into several sub-partitions SG _i . 4. The hierarchical partitioning method for obtaining the single reverse farthest neighbor on the road network as claimed in claim 1, wherein said step 12 comprises: Step twelve one: define the upper bound and the lower bound of a certain node d to a certain partition or sub-partition SG _i as d to The maximum and minimum distances of any node in , denoted as and The diameter of a partition or subpartition SG _i is defined as Define the upper and lower bounds from node d to node d′ as and Step twelve two: when and when when , since any path from d to SG _i must pass through the border nodes of SG _i use d to to estimate the upper bound of but in, estimated using the triangle inequality, while is obtained from the farthest neighbors of all the pre-calculated boundary nodes in their respective partitions and sub-partitions SG _i , The definition is the same as Step 123: Establish a partition SG _i and node d' and A priority queue stored in descending order, and all partitioned push into the queue; Step 124: each time the first one is popped up from the priority queue or If the popup is Then go to step twelve six, if the pop-up is if Then the farthest neighbor of d cannot be in SG _{i ,} and exclude this partition SG _i from the road network G _; Partitioned Push back the priority queue in descending order, if none, then call step 12; Step twelve five: calculate each The distance from all nodes d′ to d in the corresponding partition or subpartition SG _i and put all Push back the priority queue in descending order, and call step 126; Step twelve six: pop the first few from the priority queue put the first few The corresponding d' is determined as q, q∈fn(p, V _G ). 5. the method for hierarchical partitioning of obtaining the single reverse farthest neighbor on the road network as claimed in claim 4, is characterized in that, in step twelve five, calculate each The distance from all nodes d′ to d in the corresponding partition or subpartition SG _i The steps include: like Perform a Dijkstra algorithm with d as the source point to obtain the distance from d to all nodes d' in the partition or subpartition SG _i like due to anything from d to All paths must pass through the boundary nodes of the partition or subpartition SG _i Construct a retaining d and The shortcut subgraph G' of the distance between them, and the distance calculation is performed on the shortcut subgraph G' to obtain the distance from d to all nodes d' in the partition or subpartition SG _i 6. the hierarchical partitioning method of obtaining the single reverse farthest neighbor on the road network as claimed in claim 5, is characterized in that constructing a reservation d and In the step of the short-cut subgraph G′ of the distance between two steps, HEPV and HiTi technologies are used. 7. The hierarchical partitioning method for obtaining single reverse farthest neighbors on the road network as claimed in claim 5, characterized in that, constructing a reserved d and boundary node In the step of the short-cut subgraph G′ of the inter-distance, all boundary nodes are pre-saved Use the distance between the partition SG _i where d is located and the pre-saved partition boundary node to construct a shortcut subgraph G′. 8. A hierarchical partitioning system for obtaining a single reverse farthest neighbor on a road network, characterized in that it includes: The first definition module is used for a given node p on the road network G and all nodes V _G on the road network G, if there is a node q on the road network G, the road network distance between q and p| |qp||is not less than the distance from p to any point p′ in V _G ||p′-p||, then define q as the furthest neighbor of p relative to V _G , denoted as fn(p, V _G ); The second definition module, for all nodes V _G on the given road network G, the single-reverse farthest neighbor of q is defined as the set of q as the farthest neighbor point in V _G , that is, MRFN(q, V _G )={ p|p∈V _G , fn(p,V _G ∪{q})=q}; The hierarchical partition module is used to construct a hierarchical partition tree of the road network G using a top-down method. The nodes in the road network G are divided into m partitions SG _i , and each partition is recursively divided into several sub-partitions SG _i , until the required number of partitions and layers is reached; The boundary node module is used to define the boundary node of each subdivision or subdivision SG _i on the road network G as Where edge(d,d') represents the edge between d and d', Represents all nodes of the partition SG _i ; The first upper and lower bound module is used to define the upper bound and lower bound from a certain node q to a certain partition or sub-partition SG _i as q to The maximum and minimum distances of any node in , denoted as and The diameter of a partition or subpartition SG _i is defined as Define the upper and lower bounds from node q to node d as and The second upper and lower bound module is used to define the farthest upper bound and the farthest lower bound of a partition or sub-partition SG _i as arbitrary The maximum and minimum distances to its furthest neighbors on the road network G are denoted as and Define the distance from a node u to its furthest neighbor on the road network G as fub _u and flb _u ; The pre-calculation module is used to pre-calculate the distance between the boundary nodes of the sub-division SG _i in a certain sub-division SG _i , and pre-calculate the respective farthest neighbors f of all boundary nodes on the road network G and the respective locations of all boundary nodes the furthest neighbors within the partition and subpartition SG _i ; The distance module is used to select a plurality of nodes L on the road network as landmarks, and uses the Dijkstra algorithm to pre-calculate the distance from each node L to the remaining partitions without sub-regions or all nodes on the sub-regions; The estimation module is used to estimate the lower bound of the distance from node d in each partition or sub-partition SG _i to its furthest neighbor on the road network G, for Have in Calculate the maximum value of g(b, f) in each partition or subpartition SG _i as the value of the partition or subpartition SG _i The queue module is used to push all the partitions of the hierarchical partition tree into a traversal queue, pop up each partition or sub-partition SG _i in turn from the traversal queue, and judge whether each sub-partition SG _i makes If so, then the nodes in SG _i Exclude this subdivision from the road network G, if not, push the subdivision SG _i of the unexcluded subdivision or the subdivision without subdivision itself into the traversal queue, and pop each subdivision in turn from the traversal queue subpartition SG _i , and repeat the above judgment until there are only subpartitions or subpartitions without subpartitions left in the traversal queue, where the calculation The steps are as follows, when and when when , since any path from q to SG _i must pass through the border nodes of SG _i Use q to to estimate the upper bound of but in, Estimated using the triangle inequality, The definition is the same as is obtained from the distances of all the boundary nodes in the pre-calculation and the farthest neighbors in the respective partitions and sub-partitions SG _i ; The node exclusion module is used to check whether the distance ||d-q|| is necessarily smaller than the distance from d to the furthest neighbor of d for each of the remaining partitions without subpartitions or node d on the subpartition ||d-f||, if there is a landmark u and the farthest neighbor f in the node L, so that ||d-u||+||u-q||<||d-f||, then q must not be the farthest neighbor of d, so d must not be the reverse farthest neighbor of q, and exclude the node d from the remaining sub-partition or sub-partition; The checking module is used to check whether the furthest neighbor of each unexcluded d ∈ V _G is q, if yes, then determine d to be p, p ∈ MRFN(q, V _G ), if not, then d is excluded . 9. The hierarchical zoning system for obtaining single reverse farthest neighbors on the road network according to claim 8, wherein the landmarks selected by the distance module are evenly distributed on the road network G. 10. The hierarchical partitioning system for obtaining the single reverse farthest neighbor on the road network according to claim 8, wherein the hierarchical partitioning module uses the Erwig and Hagen algorithm to recursively divide each partition into several sub-partitions SG _i . 11. The hierarchical partitioning system for obtaining the single reverse farthest neighbor on the road network as claimed in claim 8, wherein the checking module comprises: The first upper and lower bound unit is used to define the upper bound and lower bound from a certain node d to a certain partition or sub-partition SG _i as d to The maximum and minimum distances of any node in , denoted as and The diameter of a partition or subpartition SG _i is defined as Define the upper and lower bounds from node d to node d′ as and Estimation unit, used when and when when , since any path from d to SG _i must pass through the border nodes of SG _i use d to to estimate the upper bound of but in, estimated using the triangle inequality, while is obtained from the farthest neighbors of all the pre-calculated boundary nodes in their respective partitions and sub-partitions SG _i , The definition is the same as Queue unit, used to establish a partition SG _i and node d' and A priority queue stored in descending order, and all partitioned push into the queue; The partition exclusion unit is used to pop the first one from the priority queue each time or If the popup is Then call the farthest neighbor unit, if the pop-up is if Then the farthest neighbor of d cannot be in SG _{i ,} and exclude this partition SG _i from the road network G _; Partitioned Push back the priority queue in descending order, if none, call the computing unit; Computing unit for computing each The distance from all nodes d′ to d in the corresponding partition or subpartition SG _i and put all Depress the priority queue in descending order and call the furthest neighbor unit; furthest neighbor unit for popping the first few put the first few The corresponding d' is determined as q, q∈fn(p, V _G ). 12. The hierarchical partitioning system for acquiring a single reverse farthest neighbor on a road network as claimed in claim 11, wherein the computing unit is used for: like Perform a Dijkstra algorithm with d as the source point to obtain the distance from d to all nodes d' in the partition or subpartition SG _i like due to anything from d to All paths must pass through the boundary nodes of the partition or subpartition SG _i Construct a retaining d and The shortcut subgraph G' of the distance between them, and the distance calculation is performed on the shortcut subgraph G' to obtain the distance from d to all nodes d' in the partition or subpartition SG _i 13. The hierarchical partitioning system for obtaining the single reverse farthest neighbor on the road network as claimed in claim 12, wherein the calculation unit uses HEPV and HiTi technology to construct a reserved d and The short-cut subgraph G′ of the distance between 14. The hierarchical partitioning system for obtaining a single reverse farthest neighbor on a road network as claimed in claim 12, wherein the calculation unit pre-saves all boundary nodes Use the distance between the partition SG _i where d is located and the pre-saved partition boundary node to construct a shortcut subgraph G′.