CN104346444A - Optimum site selection method based on road network reverse spatial keyword query - Google Patents

Abstract

An optimal site selection method based on road network anti-space keyword query, adopts an index structure based on connection clustering for data sets, and uses a Dijkstra-like search method to traverse the index; when traversing the index, the present invention Firstly, the candidate results of the potential competitors of the inquired merchants are calculated; then, the proposed relevant rules are used to verify whether they are real competitive merchants. The invention combines the prior art of the spatial database and the anti-spatial keyword algorithm, and the entire query process does not need to traverse the entire data set, thereby providing the best performance.

Description

An Optimal Site Selection Method Based on Road Network Anti-Spatial Keyword Query

technical field

The invention relates to database indexing and query technology, in particular to an optimal site selection method based on road network anti-space keyword query.

Background technique

Spatial database was born and developed as an application technology, its purpose is to store, manage and retrieve various geospatial data (including spatial data and non-spatial data). At present, spatial databases are widely used in geographic information systems, computer-aided design, multimedia information systems and data warehouses, providing data storage and query solutions for the above systems. Road network spatial database, as an important part of spatial database, has received more and more attention due to its wide application.

In order to quickly and effectively access road network spatial data, experts and scholars have proposed a large number of spatial index methods. So far, the most influential and widely used road network space-based index is the index method based on connection clustering. It uses the adjacency information of the existing road network. Its construction idea is to cluster and store the adjacent nodes of any road network node and the data points on the road network, and then use the B-tree to index, so as to minimize the storage cost. Purpose.

On this basis, experts and scholars have proposed various road network-based queries and solutions, such as nearest neighbor query, continuous nearest neighbor query, and reverse nearest neighbor query. Among them, the anti-nearest neighbor query based on road network is a novel query proposed recently. It mainly conducts queries from the perspective of merchants, and returns to merchants the addresses that affect users the most based on road network distance, so as to help merchants make site selection recommendations.

At present, there are mature solutions for reverse nearest neighbor query on road networks. However, in some cases, the road network inverse nearest neighbor query not only needs to consider spatial information, but text description information, as an important part of data points, has not been effectively used in existing methods. In order to better help merchants make optimal location decisions, this requires the system to be able to process reverse nearest neighbor query results with text information in the road network environment. But none of the existing methods can effectively solve it.

Contents of the invention

The present invention overcomes the shortcoming that the prior art cannot effectively utilize the text description information, and provides an optimal site selection method based on road network anti-space keyword query.

The technical solution steps adopted by the present invention to solve its technical problems are as follows:

Step (1): Collect existing business information, build an index on it, collect and query business alternative address information and text information;

Step (2): For each candidate address of the inquiring merchant, use the Dijkstra-like method and use the query text information to find a merchant that has a potential competitive relationship with the inquiring merchant;

Step (3): Use the judgment rule to verify each potential competitor of the candidate address of the query merchant obtained in step (2);

Step (4): Utilize the results in step (3) to find the optimal alternative address of the inquired merchant.

The information of each merchant in the described step (1) includes address information and text information, wherein the address information is represented by a geographic coordinate, and the text information is represented by one or more groups of keywords; all merchant information is represented by It is indexed based on the index model of connection clustering. The index file contains all the geographic location information and text information of the merchant. The geographic information is stored in the connection table file, and the text information is stored in the data point file; query all merchants. Information is stored in text files.

In the step (2), for each alternative address of the inquiring merchant, through the Dijkstra-like method and using the query text information, find a merchant that has a potential competitive relationship with the inquiring merchant, by judging the inclusion of the keyword And the road network distance is realized, the calculated data point set is the merchant that may constitute a competitive relationship with the query merchant; in the calculation process, it is necessary to maintain a priority queue that stores the road network node and the distance from the node to the query merchant address The leader of the priority queue is the current road network node closest to the query point; in the process of expanding the road network to obtain data points through the Dijkstra method, it is also necessary to maintain the count tree corresponding to the current road network node. To save keyword counting information; the counting tree is composed of 2 ⁿ -1 nodes, each node contains three counting values c ₁ , c ₂ and c ₃ , where c ₁ means that the keyword in the query node to the current node is equal to The number of data points of the current keyword, c ₂ indicates the number of data points from the query node to the current node whose keywords contain the current keyword, and c ₃ indicates the data from the query node to the current node on the adjacent edge whose keywords contain the current keyword number of points; if the values of c ₁ or c ₂ of all boundary node counting trees reach the given value of k, the road network expansion ends, because there are no potential competitors in the expanded road network area; among them, in In the process of judging whether a data point is a potential competitor, three situations are considered:

2.1) The keyword set of the data point is all included by the keyword set of the query merchant. In this case, according to the value of the corresponding keyword in the counting tree of the current road network node, it is divided into two cases and processed differently:

a) The count value of the count tree of the current road network node corresponding to the data point keyword set is less than the given k value, then the current data point is added to the candidate set and the corresponding value of the count tree of the current node is updated;

b) The count value of the count tree of the current road network node corresponding to the data point keyword set is greater than or equal to the given k value, and the corresponding value of the count tree of the current node is updated;

2.2) The keyword set of the data point is partly included in the keyword set of the query merchant. In this case, the corresponding value of the count tree of the current node needs to be updated, and the data point is not added to the candidate set;

2.3) The keyword set of the data point is not included in the keyword set of the queried merchant at all. In this case, there is no need to do any processing on the data point and the counting tree.

Utilize judgment rule in the described step (3) to verify the potential competitive merchants of each query merchant's alternative address obtained in step (2), by verifying the k nearest merchants of the potential competitive merchants containing its keyword set It is realized by including query merchants; for each potential competitor merchant to be verified, first locate the geographic location and keyword set of the merchant in the index, and then according to the distance range from the potential competitor merchant to the query merchant, the keyword set Judging by the number of all merchants in the keyword set containing potential competing merchants; when judging, two situations need to be considered:

3.1) Within the distance from a potential competitor to the query merchant, if there are more than or equal to k merchants whose keyword set contains the keyword set of the potential competitor, then the potential competitor is not the real competitor of the query merchant;

3.2) If there are less than k merchants within the distance from the potential competitor to the query merchant, whose keyword set contains the keyword set of the potential competitor, then the potential competitor is the real competitor of the query merchant.

Utilize the result in the step (3) in the described step (4) to find the optimal alternative address of the query merchant, which is realized according to the number of real competitive merchants that each alternative address has, and the real competitive merchants that have The candidate address with the least number is the optimal candidate address for querying the merchant.

The beneficial effects that the present invention has are:

The present invention makes full use of the existing indexing technology in the spatial database, the anti-nearest neighbor query and the query technology with keywords, and the query result can be obtained by only traversing the merchant information in a part of the road network range, which greatly reduces the I/O time and CPU time, provides the best performance.

Description of drawings

Fig. 1 is a flow chart of the implementation steps of the present invention.

Figure 2 is a schematic diagram of the working principle of the optimal location method based on road network anti-space keyword query.

Figure 3 is a schematic diagram of the query.

Detailed ways

Now in conjunction with accompanying drawing and concrete implementation technical scheme of the present invention is described further:

As shown in Fig. 1 and Fig. 2, the concrete implementation process and working principle of the present invention are as follows:

Step (1): Collect existing business information, build an index on it, collect and query business alternative address information and text information;

Step (2): For each candidate address of the inquiring merchant, use the Dijkstra-like method and use the query text information to find a merchant that has a potential competitive relationship with the inquiring merchant;

Step (3): Use the judgment rule to verify each potential competitor of the candidate address of the query merchant obtained in step (2);

Step (4): Utilize the results in step (3) to find the optimal alternative address of the inquired merchant.

The information of each merchant in step (1) includes address information and text information, wherein the address information is represented by a geographic coordinate, and the text information is represented by one or more groups of keywords; all business information is aggregated based on connections The index model of the cluster builds an index for it. The index file contains all the business location information and text information, where the geographic information is stored in the connection table file, and the text information is stored in the data point file; all the information of the query business is stored in the text file. Specifically, the index module in FIG. 2 is shown.

In step (2), for each candidate address of the query merchant, through Dijkstra-like method and using the query text information, find the merchant that has potential competitive relationship with the query merchant, by judging the inclusion of the keyword and the road network The distance is realized, and the calculated data point set is the merchant that may constitute a competitive relationship with the query merchant; The head of the queue is always the road network node closest to the query point; in the process of obtaining data points by expanding the road network through the Dijkstra method, it is also necessary to maintain a count tree corresponding to the current road network node to save the key Word counting information; the counting tree is composed of 2 ⁿ -1 nodes, each node contains three counting values c ₁ , c ₂ and c ₃ , where c ₁ means that the key from the query node to the current node is equal to the current key c ₂ indicates the number of data points whose keywords contain the current keyword from the query node to the current node, and c ₃ indicates the number of data points whose keywords include the current keyword on the adjacent edge from the query node to the current node ; If the c ₁ or c ₂ values of all boundary node count trees reach the given k value, the road network expansion ends, because there is no potential competitive merchant in the expanded road network area. This step is specifically determined by the potential competitor calculation engine in FIG. 2 . Among them, in the process of judging whether a data point is a potential competitor, three situations are considered:

2.1) The keyword set of the data point is all included by the keyword set of the query merchant. In this case, according to the value of the corresponding keyword in the counting tree of the current road network node, it is divided into two cases and processed differently:

a) The count value of the count tree of the current road network node corresponding to the data point keyword set is less than the given k value, then the current data point is added to the candidate set and the corresponding value of the count tree of the current node is updated;

b) The count value of the count tree of the current road network node corresponding to the data point keyword set is greater than or equal to the given k value, and the corresponding value of the count tree of the current node is updated;

2.2) The keyword set of the data point is partly included in the keyword set of the query merchant. In this case, the corresponding value of the count tree of the current node needs to be updated, and the data point is not added to the candidate set;

2.3) The keyword set of the data point is not included in the keyword set of the queried merchant at all. In this case, there is no need to do any processing on the data point and the counting tree.

Taking the query point q in Figure 3 as an example, we can see that p ₄ , p ₆ , p ₇ and p ₈ are discarded points, so further verification of these points is not required.

In step (3), use the judgment rule to verify each potential competitor of the query merchant’s alternative address obtained in step (2), by verifying whether the k nearest merchants of the potential competitor’s merchant containing its keyword set contain the query merchants; for each potential competitor to be verified, first locate the location and keyword set of the merchant in the index, and then according to the distance from the potential competitor to the query merchant, the keyword set contains potential competitors It is judged by the quantity of all merchants in the keyword set of the merchant. Specifically, it is calculated by the filter engine of potential competitors in Figure 2. When judging, two situations need to be considered:

3.1) Within the distance from a potential competitor to the query merchant, if there are more than or equal to k merchants whose keyword set contains the keyword set of the potential competitor, then the potential competitor is not the real competitor of the query merchant;

3.2) If there are less than k merchants within the distance from the potential competitor to the query merchant, whose keyword set contains the keyword set of the potential competitor, then the potential competitor is the real competitor of the query merchant.

In step (4), use the results in step (3) to find the optimal candidate address of the query merchant, which is realized according to the number of real competitive merchants that each candidate address has, and the one with the least number of real competitive merchants The alternative address is the optimal alternative address of the inquiring merchant, specifically calculated by the calculation engine of the real competing merchants in Figure 2.

The content described in the embodiments of this specification is only an enumeration of the implementation forms of the inventive concept. The protection scope of the present invention should not be regarded as limited to the specific forms stated in the embodiments. Equivalent technical means that a person can think of based on the concept of the present invention.

Claims (5)

1. a kind of optimal site selection method based on road network anti-space keyword query: it is characterized in that the step of this method is as follows: Step (1): Collect existing business information, build an index on it, collect and query business alternative address information and text information; Step (2): For each candidate address of the inquiring merchant, use the Dijkstra-like method and use the query text information to find a merchant that has a potential competitive relationship with the inquiring merchant; Step (3): Use the judgment rule to verify each potential competitor of the candidate address of the query merchant obtained in step (2); Step (4): Utilize the results in step (3) to find the optimal alternative address of the inquired merchant. 2. a kind of optimal site selection method based on road network anti-space keyword query according to claim 1, is characterized in that: the information of each merchant in the described step (1) comprises address information and text information, The address information is represented by a geographical coordinate, and the text information is composed of one or more groups of keywords; all business information is indexed through an index model based on connection clustering, and the index file contains all business location information And text information, wherein the geographical information is stored in the connection table file, the text information is stored in the data point file; all the information of the business query is stored in the text file. 3. a kind of best site selection method based on road network anti-space keyword query according to claim 1, is characterized in that: in described step (2), for each inquiry businessman alternative address, by class Di Jestella method, and using the query text information to find businesses that have a potential competitive relationship with the query business, it is realized by judging the inclusion of keywords and the distance of the road network. The calculated set of data points is the possible composition of the query business. Competitive merchants; in the calculation process, it is necessary to maintain a priority queue that stores road network nodes and the distance from the node to the address of the query merchant. The leader of the priority queue is the road network node that is currently closest to the query point; through In the process of Dijkstra method expanding the road network to obtain data points, it is also necessary to maintain a counting tree corresponding to the current road network node to store keyword counting information; the counting tree is composed of 2 ⁿ -1 nodes, each The node contains three count values respectively c ₁ , c ₂ and c ₃ , where c ₁ indicates the number of data points whose keywords are equal to the current keyword from the query node to the current node, and c ₂ indicates the number of data points from the query node to the current node The number of data points containing the current keyword, c ₃ indicates the number of data points whose keywords contain the current keyword on the adjacent edge from the query node to the current node; if the values of c ₁ or c ₂ of all boundary node count trees have reached Given a value of k, the road network expansion ends, because there are no potential competitors in the expanded road network area; among them, in the process of judging whether a data point is a potential competitor, three situations are considered: 2.1) The keyword set of the data point is all included by the keyword set of the query merchant. In this case, according to the value of the corresponding keyword in the counting tree of the current road network node, it is divided into two cases and processed differently: a) The count value of the count tree of the current road network node corresponding to the data point keyword set is less than the given k value, then the current data point is added to the candidate set and the corresponding value of the count tree of the current node is updated; b) The count value of the count tree of the current road network node corresponding to the data point keyword set is greater than or equal to the given k value, and the corresponding value of the count tree of the current node is updated; 2.2) The keyword set of the data point is partly included in the keyword set of the query merchant. In this case, the corresponding value of the count tree of the current node needs to be updated, and the data point is not added to the candidate set; 2.3) The keyword set of the data point is not included in the keyword set of the queried merchant at all. In this case, there is no need to do any processing on the data point and the counting tree. 4. a kind of optimal location method based on road network anti-space keyword query according to claim 1, is characterized in that: in described step (3), utilize judgment rule to obtain in step (2) each The verification of a potential competitor of an alternate address of a query merchant is realized by verifying whether the k nearest merchants of the potential competitor that contain its keyword set include the query merchant; for each potential competitor to be verified, first of all Locate the geographic location and keyword set of the merchant in the index, and then judge according to the number of all merchants whose keyword set includes the keyword set of the potential competitor within the distance from the potential competitor to the query merchant; when judging, it is necessary Consider two cases: 3.1) Within the distance from a potential competitor to the query merchant, if there are more than or equal to k merchants whose keyword set contains the keyword set of the potential competitor, then the potential competitor is not the real competitor of the query merchant; 3.2) If there are less than k merchants within the distance from the potential competitor to the query merchant, whose keyword set contains the keyword set of the potential competitor, then the potential competitor is the real competitor of the query merchant. 5. a kind of optimal site selection method based on road network anti-space keyword query according to claim 1, is characterized in that: in the described step (4), utilize the result in the step (3) to find the query merchant's The optimal candidate address is realized according to the number of real competitive merchants that each candidate address has, and the candidate address with the least number of real competitive merchants is the optimal candidate address for the inquiring merchant.