CN116776010A - Query method, device, equipment and storage medium for target position user - Google Patents

Abstract

The embodiment of the present application discloses a query method, device, equipment and storage medium for target location users. The query method includes: obtaining the target area range to be queried; converting the target area range into Multiple one-dimensional value intervals; search for candidate user sets whose location codes satisfy the multiple one-dimensional value intervals from a preset grid database; the grid database stores multiple user identifiers and information about each user The location code associated with the user is used; the candidate user set is filtered using the target area range to determine the target user located within the target area range. By uniformly encoding the user location, the target area range is converted into multiple one-dimensional value intervals. There is no need to adjust the user location storage logic according to different query areas. One-dimensional search of interval values can be performed for any query area, which greatly improves the processing efficiency. .

Description

Target location user query method, device, equipment and storage medium

Technical Field

The present application relates to, but is not limited to, the field of big data processing technology, and in particular to a method, device, equipment and storage medium for querying users at a target location.

Background Art

In LBS (Location-Based Service), the system usually has to process the locations of a large number of users, and the user locations are also in a state of dynamic update. Finding the target location user according to the location range is a common demand. Due to the changes in user locations and the uncertainty of the area range, how to efficiently retrieve the target results under the massive user base has become a difficult problem. The operator's location signaling big data faces such a challenge.

The existing Google S2 grid coding range search technology has the following disadvantages: it uses Level-15 and Level-22 two-level traversal, which is inefficient when the number of grids is large; the K-V structure with time + grid as the key and user set as the value cannot incrementally update the user's location, and all user locations need to be fully recorded in each time slice.

Summary of the invention

In view of this, the embodiments of the present application provide a method, device, equipment and storage medium for querying users at a target location, which at least solves the problem of inefficiency in searching for users within a target area among a large number of users due to changes in user locations and uncertainty in area ranges.

The technical solution of the embodiment of the present application is implemented as follows:

In a first aspect, an embodiment of the present application provides a method for querying a user at a target location, the method comprising:

Obtain the target area range to be queried; convert the target area range into multiple one-dimensional value intervals through the S2 grid coverage algorithm; search for a candidate user set whose position codes satisfy the multiple one-dimensional value intervals from a preset grid database; the grid database stores identifiers of multiple users and position codes associated with each of the users; use the target area range to screen the candidate user set and determine the target users within the target area range.

In some embodiments, the range of the target area is converted into multiple one-dimensional value intervals through the S2 grid coverage algorithm, including: using the S2 grid coverage algorithm to determine the N grids covered by the target area; wherein N is less than or equal to a preset maximum number of grids, and the level of each of the grids is between a preset minimum level and a maximum level; converting the S2 grid code of each of the grids into a one-dimensional value interval; connecting the value intervals of adjacent grids in the N grids end to end to obtain a merged M one-dimensional value interval; wherein M is a natural number less than N.

In some embodiments, the method further includes: using the S2 geographic location coding system to encode the two-dimensional coordinates of each of the users to obtain the location code of the corresponding user; using the identifier of each of the users as a key and the location code of the corresponding user as a value and storing it in the grid database.

In some embodiments, the position code is a first-level grid precision, the grid database is an ordered set structure of Redis, and the value of the ordered set structure is a double-precision floating point type. The method also includes: for each of the users, converting the position code of the first-level grid precision into a position code of the second-level grid precision matching the double-precision floating point type; storing the position code of the second-level grid precision in the ordered set structure as a value associated with the corresponding user; wherein the grid corresponding to the second-level grid precision is the parent grid of the grid corresponding to the first-level grid precision.

In some implementations, the method further includes: in response to the first user's two-dimensional coordinate update, encoding the updated two-dimensional coordinate to obtain a new position code; and updating the value associated with the first user in the grid database using the new position code.

In some embodiments, searching from a set grid database for a set of candidate users whose position codes satisfy the multiple one-dimensional value intervals includes: for each one-dimensional value interval, searching from the grid database for users whose position codes belong to the corresponding one-dimensional value interval to obtain a query result; the query result includes an identifier of the user and an associated position code; and merging the query results of the multiple one-dimensional value intervals to obtain the candidate user set.

In some implementations, the using the target area range to screen the candidate user set to determine the target user within the target area range includes: for each candidate user in the candidate user set, when the boundary of the target area range completely includes the minimum grid to which the location of the corresponding candidate user belongs, determining the corresponding candidate user as the target user.

In a second aspect, an embodiment of the present application provides a device for querying a user at a target location, the device comprising:

An acquisition module is used to obtain the target area range to be queried;

A conversion module, used to convert the target area range into multiple one-dimensional value intervals through an S2 grid coverage algorithm;

A search module, used to search for a set of candidate users whose position codes satisfy the multiple one-dimensional value intervals from a preset grid database; the grid database stores multiple user identifiers and position codes associated with each of the users;

The screening module is used to screen the candidate user set using the target area range to determine the target users within the target area range.

In a third aspect, an embodiment of the present application provides a computer device, including a memory and a processor, wherein the memory stores a computer program that can be executed on the processor, and when the processor executes the program, some or all of the steps in the above method are implemented.

In a fourth aspect, an embodiment of the present application provides a computer-readable storage medium having a computer program stored thereon, which implements some or all of the steps in the above method when executed by a processor.

The embodiments of the present application have at least the following technical effects:

In the embodiment of the present application, the S2 grid coverage algorithm is used to process the target area range to be queried into multiple one-dimensional value intervals under the grid, and the user's identification and position code are stored in the grid database in association, so as to use the multiple value intervals to perform a one-dimensional value range search on the user position, obtain the user position under the regional coverage grid, and then screen out the target user within the target area. In this way, by uniformly encoding the user position, the target area range is converted into multiple one-dimensional value intervals, and there is no need to adjust the user position storage logic according to different query areas. One-dimensional search of interval values can be performed for any query area, which greatly improves processing efficiency.

It should be understood that the above general description and the following detailed description are merely exemplary and explanatory, and are not intended to limit the technical solutions of the present disclosure.

BRIEF DESCRIPTION OF THE DRAWINGS

The drawings herein are incorporated into the specification and constitute a part of the specification. These drawings illustrate embodiments consistent with the present application and are used together with the specification to illustrate the technical solution of the present application.

FIG1 is a schematic diagram of a flow chart of a method for querying a target location user provided by an embodiment of the present application;

FIG2 is a schematic diagram of a flow chart of a method for querying a target location user provided by an embodiment of the present application;

FIG3 is a schematic diagram of a flow chart of a method for querying a target location user provided by an embodiment of the present application;

FIG4 is a system framework diagram for searching for a target user by location based on a regional range provided by an embodiment of the present application;

FIG5A is a schematic diagram of a grid coverage graphical effect provided in an embodiment of the present application;

FIG5B is a schematic diagram of a grid coverage graphical effect provided in an embodiment of the present application;

FIG5C is a schematic diagram of a grid coverage graphical effect provided in an embodiment of the present application;

FIG5D is a schematic diagram of a grid coverage graphical effect provided in an embodiment of the present application;

FIG6 is a schematic diagram of the structure of a query device for a target location user provided in an embodiment of the present application;

FIG. 7 is a schematic diagram of a hardware entity of a computer device provided in an embodiment of the present application.

DETAILED DESCRIPTION

In order to make the purpose, technical solutions and advantages of the present application clearer, the technical solutions of the present application are further elaborated in detail below in conjunction with the drawings and embodiments. The described embodiments should not be regarded as limiting the present application. All other embodiments obtained by ordinary technicians in the field without making creative work are within the scope of protection of the present application.

In the following description, reference is made to “some embodiments”, which describe a subset of all possible embodiments, but it will be understood that “some embodiments” may be the same subset or different subsets of all possible embodiments and may be combined with each other without conflict.

The terms "first/second/third" involved are merely used to distinguish similar objects and do not represent a specific ordering of the objects. It is understandable that "first/second/third" can be interchanged with a specific order or sequence where permitted so that the embodiments of the present application described herein can be implemented in an order other than that illustrated or described herein.

Unless otherwise defined, all technical and scientific terms used herein have the same meaning as those commonly understood by those skilled in the art to which this application belongs. The terms used herein are only for the purpose of describing this application and are not intended to limit this application.

Before further describing the embodiments of the present application in detail, the nouns and terms involved in the embodiments of the present application are explained first. The nouns and terms involved in the embodiments of the present application are subject to the following interpretations.

A related technology mentions a grid processing method, which dynamically adjusts the GeoHash grid size according to the density of registered users, associates users to the grid, and selects users with the same grid as nearby target users. However, the technology of using Geo Hash grid coding for range search has the following disadvantages: 1) It is necessary to determine the grid accuracy in advance according to various dimensional parameters, and traverse the surrounding grids during calculation to achieve a search within a certain range; 2) It is suitable for searching for similar elements within a certain range around a seed position, such as the "nearby people" function, and cannot perform range search for areas with arbitrary boundaries; 3) When the number of users is too large and widely distributed, the number of grids and the number of people under the grids are both large, and traversing the grids and then traversing the users in the grids is inefficient.

Another related technology is a method for using S2 to encode the location to build an index for regional query, which constructs a K-V structure, in which the key uses time + Level-15 grid + Level-22 grid as the index, uses the S2 area coverage algorithm, and matches the Level-15 and Level-25 secondary indexes for the obtained coverage grid, thereby hitting the trajectory data in the corresponding grid. However, the technology of using Google S2 grid coding for range search has the following disadvantages: 1) Level-15 (306-meter accuracy) and Level-22 (2-meter accuracy) fixed levels are used as secondary indexes, and all users and regions need to be processed as these two levels for sequential matching; 2) The characteristic of S2 coding that the values are similar in adjacent spaces is not used, but Level-15 and Level-22 are used for two-level traversal, which is inefficient when the number of grids is large; 3) The K-V structure with time + grid as the key and user set as the value cannot incrementally update the user's location, and all user locations need to be fully recorded in each time slice.

The embodiment of the present application provides a method for querying users at a target location, which can be executed by a processor of a computer device. The computer device may refer to a server, a laptop, a tablet computer, a desktop computer, a smart TV, a set-top box, a mobile device (such as a mobile phone, a portable video player, a personal digital assistant, a dedicated messaging device, a portable gaming device), and other devices that have the ability to query users at a target location. FIG. 1 is a flow chart of a method for querying users at a target location provided by an embodiment of the present application. As shown in FIG. 1 , the method includes the following steps S110 to S140:

Step S110, obtaining the target area range to be queried.

Here, the embodiment of the present application aims to query the user data contained in a target area range, i.e., a geographic space area, by using the user as a query condition. The most common way to describe any geographical area range is a polygon, and in particular, a circle can also be approximated by a polygon.

Step S120: convert the target area range into multiple one-dimensional value intervals through the S2 grid coverage algorithm.

Here, in the implementation, the input target area range is modeled as S2Polygon, and multiple grids of different sizes covered by S2Polygon are obtained according to the regional optimal coverage method (S2RegionCover) provided by S2. Then, the value interval of S2 code under each grid is processed to obtain multiple one-dimensional value intervals.

It should be noted that Google S2 achieves a dimensionality reduction representation of the earth's surface space based on space filling curves. The grid accuracy of Google S2 is divided into 30 levels, and a lower level (larger) grid can always cover exactly 4 higher level (smaller) grids. All grids are represented by 64-bit fixed-length integers. A grid has a fixed value range, called the minimum range to the maximum range (rangeMin～rangeMax). The value range does not overlap with other grids of the same level, and the value range of the parent level grid is completely consistent with the union of the value ranges of the sub-grids it covers.

Step S130, searching a preset grid database for a set of candidate users whose position codes satisfy the multiple one-dimensional value intervals.

Here, the grid database stores multiple user identifiers and location codes associated with each user. That is, the grid database has a K-V (key-value mapping) structure and supports searching by value range, returning key-value pair records that meet the conditions, that is, returning users and their location codes whose location codes are within the specified range.

In the implementation, the user locations corresponding to each user, such as longitude and latitude coordinates, are uniformly S2-encoded in advance to obtain a one-dimensional location code for each user, which is stored in a grid database with a K-V structure, where the key is the user's unique identifier and the value is the location code of the corresponding user, i.e., the highest precision one-dimensional representation value of S2. This facilitates subsequent one-dimensional linear search according to the value interval of the region.

Step S140: screening the candidate user set by using the target area range to determine the target users within the target area range.

Here, since the coverage of the grid is larger than the actual target area, each user in the candidate user set found by the grid is screened to determine whether the location of the user found by the grid is within the target area, and then the users included in the target area are retained as target users.

In the embodiment of the present application, the S2 grid coverage algorithm is used to process the target area range to be queried into multiple one-dimensional value intervals under the grid, and the user's identification and position code are stored in the grid database in association, so as to use the multiple value intervals to perform a one-dimensional value range search on the user position, obtain the user position under the regional coverage grid, and then filter out the target user within the target area. In this way, by uniformly encoding the user position, the target area range is converted into multiple one-dimensional value intervals, and there is no need to adjust the user position storage logic according to different query areas. One-dimensional search of interval values can be performed for any query area, which greatly improves processing efficiency.

In some embodiments, before step S130, the method further includes steps 101 and 102:

Step 101, using the S2 geographic location coding system to encode the two-dimensional coordinates of each user to obtain the location code of the corresponding user;

Here, the two-dimensional coordinates of each user are the location coordinates composed of latitude and longitude. For example, the location coordinates of user u1 are (31.36529787524528, 120.43801146916059). Using the Google S2 geographic location coding system, it is converted into the S2 grid code to obtain its 64-bit integer code value, such as 3869610778954949709 (corresponding hexadecimal code is 35b39e805aa1e44d). According to the S2 coding rules, this is a Level-30 grid, and the positioning accuracy of this level on the earth's surface is about 9 millimeters (mm). That is, the coding accuracy of the user's location is 9mm.

Step 102: The identifier of each user is used as a key, and the position of the corresponding user is encoded as a value and stored in the grid database.

Here, each user corresponds to a unique key, and the user's location can be updated in real time, achieving incremental updates and facilitating instant feedback queries.

In some embodiments, the position code is a first-level grid precision, the grid database is an ordered set structure of Redis, and the value of the ordered set structure is a double-precision floating point type. The method also includes: for each of the users, converting the position code of the first-level grid precision into a position code of the second-level grid precision matching the double-precision floating point type; storing the position code of the second-level grid precision in the ordered set structure as a value associated with the corresponding user; wherein the grid corresponding to the second-level grid precision is the parent grid of the grid corresponding to the first-level grid precision.

Here, according to the coding rules of S2, the first-level grid accuracy is the positioning accuracy corresponding to the grid of Level-30, that is, 9mm, and the second-level grid accuracy is the positioning accuracy corresponding to the grid of Level-25, that is, 30 centimeters (cm). The K-V of the ordered set structure (Sorted Set) of Redis is respectively called member and score. Because its score part is designed as a double-precision floating point type (double), when it is used to store 8-byte integers, only 52 (mantissa) + 1 (sign bit) + 1 (highest bit hidden) = 54Bit valid bits can be retained. Therefore, according to the S2 coding rules, the user's unique identifier is used as a member, and the user's Level-25 S2 code is used as the score, which is stored in the user set structure.

In some embodiments, after step 102, the method further includes: in response to the update of the two-dimensional coordinates of the first user, encoding the updated two-dimensional coordinates to obtain a new position code; and updating the value associated with the first user in the grid database using the new position code.

In the above embodiment, when the user's location is refreshed, the latitude and longitude coordinates of the new location are converted into a location code, and the value associated with the user in the K-V structure is updated. In this way, the user's location is incrementally updated among a large number of users, and the target is hit quickly and in real time.

Based on FIG. 1 , FIG. 2 is a flow chart of a method for querying a target location user provided in an embodiment of the present application. As shown in FIG. 2 , the above step S120 “converting the target area range into multiple one-dimensional value intervals by using the S2 grid coverage algorithm” includes the following steps S210 to S230:

Step S210: using the S2 grid coverage algorithm to determine the N grids covered by the target area.

Here, N is less than or equal to the preset maximum number of grids, and the level of each grid is between the preset minimum level and the maximum level; the grid accuracy of Google S2 is divided into 30 levels, and a lower level (larger) grid can always cover exactly 4 higher level (smaller) grids.

Step S220, converting the S2 grid code of each of the grids into a one-dimensional value interval.

Here, all grids are represented by 64-bit fixed-length integers. A grid has a fixed value range, called rangeMin~rangeMax, which is the value range of the S2 code under the grid.

Step S230, connecting the value intervals of adjacent grids in the N grids end to end to obtain M merged one-dimensional value intervals.

Here, M is a natural number less than N, for example, N is 8 and M is 6. The merged M segments of one-dimensional value intervals are the same as the valid values contained in the original N value intervals. Combined with the characteristics of S2 coding, the two endpoints of the value interval (i.e., rangeMin and rangeMax) are both 30-level codes, and the last (rightmost) bit is fixed to 1, so the range of the above values can be extended by 2 invalid values, namely rangeMin-1 and rangeMax+1, so that the value intervals of adjacent grids are connected end to end after optimization, thereby reducing the number of fragments and facilitating subsequent segmented retrieval queries.

FIG3 is a flow chart of a method for querying a target location user provided by an embodiment of the present application. As shown in FIG3 , the method includes the following steps S310 to S350:

Step S310, obtaining the target area range to be queried.

Step S320: convert the target area range into multiple one-dimensional value intervals through the S2 grid coverage algorithm.

Here, the above steps S310 to S320 correspond to the above steps S110 to S120 respectively, and the specific implementation of the above steps S110 to S120 may be referred to during implementation.

Step S330: for each one-dimensional value interval, searching the grid database for users whose location codes belong to the corresponding one-dimensional value interval to obtain a query result.

Here, the query result includes the user's identifier and the associated location code.

Step S340: merging the query results of the multiple one-dimensional value intervals to obtain the candidate user set.

For example, user A whose coding position satisfies a1≤x≤b1 and A's actual coding position L1 are found, user B and A's actual coding position L2 and user C and C's actual coding position L3 are found, thereby obtaining the candidate user set {user A, user B, user C} under the regional coverage grid.

Step S350 : for each candidate user in the candidate user set, if the boundary of the target area completely includes the smallest grid to which the location of the corresponding candidate user belongs, determine the corresponding candidate user as a target user.

Here, the minimum grid is a Level-30 grid, and the accuracy is 9 mm, that is, when the minimum grid corresponding to the user position is within the boundary of the target area, it is determined that the user position is indeed within the target area.

In the above embodiment, the target area range is processed into multiple value intervals, and then the location codes that meet the conditions of the multiple value intervals are searched from the stored grid database to obtain users under the regional coverage grid; at the same time, for each user in the candidate user set screened out by the grid, it is determined whether the target area range includes the smallest grid to which the user's location belongs, thereby retaining the target users within the target area range as the final query results.

The query method for the target location user is described below in conjunction with a specific embodiment. However, it should be noted that the specific embodiment is only for better illustrating the present application and does not constitute an improper limitation on the present application.

The embodiment of the present application proposes a system for searching for a target user by location according to an area range. As shown in FIG4 , the system includes a user location storage module 41, an area range processing module 42, a range search user module 43, and a location area matching module 44.

The user location storage module 41 is used to convert the location coordinates of all users into S2 grid codes using the Google S2 geographic location coding system, and store them in the database with the key being the user's unique identifier and the value being the one-dimensional location code with the highest accuracy in the S2 grid code. Compared with the related art that uses time_c15_c22 as the key and the user set at the same grid location as the value, the embodiment of the present application encodes the user location, with the key being the user's unique identifier and the value being the one-dimensional representation value with the highest accuracy in S2.

Each user's location is represented as longitude and latitude, that is, a two-dimensional coordinate consisting of latitude and longitude. For example, the location coordinates of user u1 are (31.36529787524528, 120.43801146916059). Using the Google S2 geographic location coding system, it is converted into an S2 grid code to obtain its 64-bit integer code value, such as 3869610778954949709 (the corresponding hexadecimal code is 35b39e805aa1e44d). This process uses the Java SDK coding as follows:

1.S2CellId s2CellId=S2CellId.fromLatLng(

S2LatLng.fromDegrees(31.36529787524528,120.43801146916059)); 2.System.out.println(s2CellId.id());

According to the coding rules of S2, this is the Level-30 grid, and the positioning accuracy of this level on the earth's surface is about 9mm. The location coordinates of all users are converted in this way. For example, the data of 10 users are as follows in Table 1:

Table 1 The latitude and longitude coordinates of 10 users and their corresponding location codes

user Latitude and longitude coordinates Positional encoding u1 (31.36529787524528,120.43801146916059) 3869610778954949709 u2 (31.36632390057698,120.43966370991376) 3869610782012042381 u3 (31.365920820532406,120.4422815459123) 3869610806528482041 u4 (31.365462772928936,120.44468480518964) 3869610804782716089 u5 (31.36498640105347,120.44341880253461) 3869610807034091899 u6 (31.364583315273084,120.4407151358476) 3869610780744343071 u7 (31.364528348896393,120.43917018345502) 3869610781522426437 u8 (31.363593915574565,120.43837624958661) 3869610779558776805 u9 (31.363685527095264,120.44052201679852) 3869610780586528131 u10 (31.36265947296363,120.43936330250409) 3869610769638744613

Select a database with the following characteristics to store users and their location codes: on the one hand, it has a key-value mapping structure, that is, the user is used as the key, each user corresponds to a unique key, and the location code is used as the value to associate with the user; on the other hand, it supports searching by value range and returns key-value pair records that meet the conditions, that is, returns users and their location codes whose location codes are within the specified range.

A known database that meets the above conditions is implemented as a Redis ordered set (Sorted Set), whose K-V is called member and score respectively. Because its score part is designed as double (double-precision floating point type), when it is used to store an 8-byte integer, only 52 (mantissa) + 1 (sign bit) + 1 (highest bit hidden) = 54 bits of valid bits can be retained. According to the S2 encoding rule, 54 bits are used for Level-25. The precision of the 30-level grid needs to be reduced and converted to its 25-level parent grid. For example, the 25-level parent grid of the 30-level grid 3869610778954949709 is encoded as 3869613036593792000 (corresponding hexadecimal encoding is 35b3a08e0064c400). This process uses the Java SDK encoding such as:

1.S2CellId pCellId=s2CellId.parent(25);

2.System.out.println(pCellId.id());

According to the S2 encoding rules, this is a Level-25 grid, which has a positioning accuracy of about 30 cm on the earth's surface. The user's unique identifier is used as the member, and the user's Level-25 S2 code is used as the score, which is stored in the user set structure. For example, the following ZADD command "ZADD users3869613036593792000u1" is used to store user u1 and its location code in the ordered set structure named users in Redis.

All users and location codes (depending on the limitations of the database implementation, different precisions may be used) are stored in the database K-V structure, and each user has a unique record. When the user's location is refreshed, the longitude and latitude of the new location are converted to the location code, and the value associated with the user in the K-V structure is updated. The structure after storage is as shown in Table 2:

Table 2 User and location codes stored in the database K-V structure

The area range processing module 42 is used to process the area range into multiple value intervals. The embodiment of the present application uses the S2 grid to cover the area, obtains multiple grids of different sizes, takes the rangeMin to rangeMax range of each grid, that is, the value interval of the S2 code under the grid, and performs head-to-tail connection compression to obtain multiple one-dimensional value intervals.

The most common way to describe any geographical area is with a polygon. In particular, a circle can also be approximated by a polygon. A polygon can be described by a sequence of vertices, where each vertex is a two-dimensional coordinate consisting of latitude and longitude. For example, a rectangle can be represented by the following sequence if its four vertices are arranged clockwise: (31.365309728100144, 120.43889177031652), (31.365309728100144, 120.44315111823217), (31.361660168572687, 120.44315111823217), (31.361660168572687, 120.43889177031652).

Use the grid coverage algorithm (RegionConverer) provided by S2, input a geographic polygon, select the appropriate minimum level (minLevel), maximum level (maxLevel), and maximum grid (maxCells) parameters, and the output result is a set of S2 grids covering the polygon. The level of each grid is between the minimum level and the maximum level, and the total number of grids is within the maximum cell. This process uses the Java SDK code such as:

1.S2RegionCoverer s2RegionCoverer=new S2RegionCoverer();

2.s2RegionCoverer.setMinLevel(2);

3.s2RegionCoverer.setMaxLevel(20);

4.s2RegionCoverer.setMaxCells(10);

5.List<S2CellId>s2CellIds＝

s2RegionCoverer.getInteriorCovering(s2Region).cellIds();

6.for(S2CellId s2CellId:s2CellIds)

7.{System.out.println(s2CellId.id());

8.}

Figures 5A to 5D are schematic diagrams of the graphical effect of grid coverage provided by the embodiments of the present application, wherein Figure 5A illustrates the situation when a maximum of 5 grids are used for coverage, Figure 5B illustrates the situation when a maximum of 10 grids are used for coverage, Figure 5C illustrates the situation when a maximum of 20 grids are used for coverage, and Figure 5D illustrates the situation when a maximum of 50 grids are used for coverage. It can be seen that the maximum grid parameter (max cells) has an effect on the coverage effect. Using more grids 51 will be able to fit the boundaries of polygons 52 (such as rectangles) more finely, making the coverage range of these grids 51 overflowing outside the polygon 52 smaller. However, more grids will make the value intervals of these grids more fragmented and discrete.

Assume that 10 grids are used for coverage, and each grid is converted into a one-dimensional value interval, that is, the rangeMin to rangeMax corresponding to each grid is taken. This process is coded using the Java SDK as follows:

1.S2CellId rangeMin=s2CellId.rangeMin();

2.S2CellId rangeMax=s2CellId.rangeMax();

3.System.out.println(rangeMin.id()+"～"+rangeMax.id());

The following results are obtained by processing these 10 grids as shown in Table 3:

Table 3 The value interval information corresponding to the 10 grids

Combined with the characteristics of S2 coding, rangeMin and rangeMax are both 30-level codes, and the last (rightmost) bit is fixed to 1, so the range of the above value can be extended by 2 invalid values, namely rangeMin-1 and rangeMax+1, so that the value ranges of adjacent grids are connected end to end to reduce the number of fragments, but the valid values they contain remain completely unchanged. The results after expansion are as follows in Table 4:

Table 4 The value interval information corresponding to the 10 expanded grids

After this optimization, the value range can be combined into 5 segments, as shown in Table 5 below:

Table 5 The five value intervals after merging

At this point, the input area range is processed into multiple value intervals. The area range covered by the above 10 grids is converted into the following 5 value intervals:

[3869610766831190016,3869610766965407745] ∪[3869610768307585024,3869610770455068672] ∪[3869610779581874176,386961078172 9357824] ∪[3869610782266228736,3869610782803099648] ∪[3869610806425419776,3869610809646645248]

The range search user module 43 is used to perform a one-dimensional range search on the user position using multiple value intervals, such as searching for x that satisfies the conditions a1≤x≤b1 or a2≤x≤b2 or ... or an≤x≤bn, to obtain users in the area coverage grid.

Searching for matching records based on the value range is an operation required by the "user location storage module" to support the K-V structure database. The aforementioned database implementation that meets the requirements, that is, the ordered set structure of Redis, can be implemented through the zrangeByScore command. For example, if the value range [3869610779581874176,3869610781729357824] is entered, the user and his location can be obtained through this command "ZRANGEBYSCORE users 38696107795818741763869610781729357824WITHSCORES". The results of the above command matching the above 10 user records are as follows in Table 6:

Table 6 Three matching records found based on 1 value range

key value u6 3869610780744343071 u7 3869610781522426437 u9 3869610780586528131

The users and their locations within the five value intervals are queried respectively, and the five results are combined. The final set of users within any value interval is as shown in Table 7:

Table 7 User sets found in all value ranges

The location area matching module 44 is used to determine whether the area multi-boundary contains the user location for each user screened out by the grid, and retain the contained users as the final result within the area boundary.

Since the grid coverage exceeds the true range of the region, the user found according to the grid range may be outside the region boundary. This module needs to determine whether the region polygon contains the user's location (S2 grid) to confirm whether the user's location is indeed within the region. When the polygon boundary completely contains the tiny grid where the user's location is located (Level-30 grid accuracy is 9 mm), the calculation result is true. This process uses the Java SDK code such as:

1.S2Cell s2Cell=new S2Cell(new S2CellId(3869610806528482041L));

2. // Whether the polygon completely contains the grid

3.boolean contained=s2Polygon.contains(s2Cell);

4.System.out.println(contained);

The calculation results for users in the coverage areas of the above five grids are:

Table 7 User sets found in all value ranges

According to the results, the users whose locations are within the area are solved, and the final result is: {u6,u7,u9}, that is, users u6, u7, and u9 are located in the target area.

Since the grid coverage is larger than the actual target area, the embodiment of the present application determines whether the multi-boundary of the area (modeled as S2Polygon) contains the user location (modeled as S2Cell) for each user screened out by the grid, and retains the included users, which is the final result within the area boundary. In the process, the user position is coded at up to level 30, so the overall accuracy can reach up to 9 mm.

In the embodiments of the present application, on the one hand, the user coding position is fixed and has nothing to do with the user density, the number of users, and the area where the users are distributed; on the other hand, the same user location data can support area range searches with arbitrary boundaries without adjusting the preprocessing mechanism; thirdly, among a large number of users, incremental updates of user locations are allowed to quickly hit the target in real time.

The embodiments of the present application have at least the following technical effects: 1) user locations are processed uniformly, and any area range is converted into an interval of one-dimensional values, and there is no need to adjust the user location storage logic according to different query areas; 2) relative to the operation of traversing the grid in sequence used in the known GeoHash grid and Google S2 gridding processing, the embodiments of the present application search for one-dimensional interval values, which greatly improves the processing efficiency; 3) different from the related art that uses the grid as an index and stores the user set as a value structure, the embodiments of the present application use the user as the key, and the location of each user can be updated in real time, realizing incremental updates and instant feedback queries; 4) the user location encoding accuracy is 9 mm (the accuracy is 30 cm when using Redis storage), which is better than the 2-meter accuracy of the Level-15+Level-22 two-level index in the related art, and has a wide range of applicability in practical applications.

The target user query method provided in the embodiment of the present application can be applied in the scenario of dynamic update of massive user locations. It does not need to maintain the relationship between users and regions in advance. It can quickly find users in the local area based on the area range input immediately. It can be applied to products that select users in real time for insight or contact under the big data of operator location.

Based on the foregoing embodiments, an embodiment of the present application provides a query device for target location users, which includes the modules included and the sub-modules included in each module, which can be implemented by a processor in a computer device; of course, it can also be implemented by a specific logic circuit; in the implementation process, the processor can be a central processing unit (CPU), a microprocessor (MPU), a digital signal processor (DSP) or a field programmable gate array (FPGA), etc.

FIG6 is a schematic diagram of the composition structure of a query device for a target location user provided in an embodiment of the present application. As shown in FIG6 , the query device 600 includes: an acquisition module 610, a conversion module 620, a search module 630, and a screening module 640, wherein:

An acquisition module 610 is used to acquire the target area range to be queried;

A conversion module 620, configured to convert the target area range into multiple one-dimensional value intervals through an S2 grid covering algorithm;

A search module 630 is used to search for a set of candidate users whose position codes satisfy the multiple one-dimensional value intervals from a preset grid database; the grid database stores multiple user identifiers and position codes associated with each of the users;

The screening module 640 is used to screen the candidate user set using the target area range to determine the target users within the target area range.

In some possible embodiments, the conversion module 620 includes: a first determination submodule, used to determine the N grids covered by the target area range using the S2 grid coverage algorithm; wherein N is less than or equal to a preset maximum number of grids, and the level of each of the grids is between a preset minimum level and a maximum level; a conversion submodule, used to convert the S2 grid code of each of the grids into a one-dimensional value interval; a merging submodule, used to connect the value intervals of adjacent grids in the N grids end to end to obtain M merged one-dimensional value intervals; wherein M is a natural number less than N.

In some possible embodiments, the device also includes: an encoding module, used to encode the two-dimensional coordinates of each of the users using the S2 geographic location coding system to obtain the location code of the corresponding user; a storage module, used to store the identifier of each of the users as a key and the location code of the corresponding user as a value in the grid database.

In some possible embodiments, the position code is a first-level grid precision, the grid database is an ordered set structure of Redis, the value of the ordered set structure is a double-precision floating point type, and the storage module is also used to convert the position code of the first-level grid precision into a second-level grid precision position code matching the double-precision floating point type for each of the users; the position code of the second-level grid precision is stored in the ordered set structure as a value associated with the corresponding user; wherein the grid corresponding to the second-level grid precision is the parent grid of the grid corresponding to the first-level grid precision.

In some possible embodiments, the device further includes an updating module for encoding the updated two-dimensional coordinates in response to the update of the two-dimensional coordinates of the first user to obtain a new position code; and using the new position code to update the value associated with the first user in the grid database.

In some possible embodiments, the search module includes: a search submodule, used to search from the grid database for users whose position codes belong to the corresponding one-dimensional value interval for each segment of the one-dimensional value interval, to obtain a query result; the query result includes the user's identifier and the associated position code; and a merging submodule, used to merge the query results of the multiple one-dimensional value intervals to obtain the candidate user set.

In some possible embodiments, the screening module is further used to determine, for each candidate user in the candidate user set, that the corresponding candidate user is the target user when the boundary of the target area completely includes the minimum grid to which the location of the corresponding candidate user belongs.

The description of the above device embodiment is similar to the description of the above method embodiment, and has similar beneficial effects as the method embodiment. In some embodiments, the functions or modules included in the device provided by the embodiments of the present disclosure can be used to execute the method described in the above method embodiment. For technical details not disclosed in the device embodiment of the present application, please refer to the description of the method embodiment of the present application for understanding.

It should be noted that in the embodiment of the present application, if the query method of the target location user is implemented in the form of a software function module and sold or used as an independent product, it can also be stored in a computer-readable storage medium. Based on such an understanding, the technical solution of the embodiment of the present application is essentially or the part that contributes to the relevant technology can be embodied in the form of a software product, which is stored in a storage medium and includes several instructions to enable a computer device (which can be a personal computer, a server, or a network device, etc.) to execute all or part of the methods described in each embodiment of the present application. The aforementioned storage medium includes: various media that can store program codes, such as a U disk, a mobile hard disk, a read-only memory (ROM), a disk or an optical disk. In this way, the embodiment of the present application is not limited to any specific hardware, software or firmware, or any combination of hardware, software, and firmware.

An embodiment of the present application provides a computer device, including a memory and a processor, wherein the memory stores a computer program that can be run on the processor, and when the processor executes the program, some or all of the steps in the above method are implemented.

The embodiment of the present application provides a computer-readable storage medium on which a computer program is stored, and when the computer program is executed by a processor, some or all of the steps in the above method are implemented. The computer-readable storage medium can be transient or non-transient.

An embodiment of the present application provides a computer program, including a computer-readable code. When the computer-readable code is run in a computer device, a processor in the computer device executes some or all of the steps for implementing the above method.

The embodiment of the present application provides a computer program product, which includes a non-transitory computer-readable storage medium storing a computer program, and when the computer program is read and executed by a computer, some or all of the steps in the above method are implemented. The computer program product can be implemented specifically by hardware, software or a combination thereof. In some embodiments, the computer program product is specifically embodied as a computer storage medium, and in other embodiments, the computer program product is specifically embodied as a software product, such as a software development kit (SDK) and the like.

It should be noted here that the description of the various embodiments above tends to emphasize the differences between the various embodiments, and the same or similar aspects can be referenced to each other. The description of the above device, storage medium, computer program and computer program product embodiments is similar to the description of the above method embodiment, and has similar beneficial effects as the method embodiment. For technical details not disclosed in the embodiments of the device, storage medium, computer program and computer program product of this application, please refer to the description of the method embodiment of this application for understanding.

It should be noted that FIG. 7 is a schematic diagram of a hardware entity of a computer device in an embodiment of the present application. As shown in FIG. 7 , the hardware entity of the computer device 700 includes: a processor 701, a communication interface 702, and a memory 703, wherein:

Processor 701 generally controls the overall operation of computer device 700 .

The communication interface 702 enables the computer device to communicate with other terminals or servers through a network.

The memory 703 is configured to store instructions and applications executable by the processor 701, and can also cache data to be processed or processed by the processor 701 and each module in the computer device 700 (for example, image data, audio data, voice communication data, and video communication data), which can be implemented by flash memory (FLASH) or random access memory (Random Access Memory, RAM). Data transmission between the processor 701, the communication interface 702 and the memory 703 can be carried out through the bus 704.

It should be understood that "one embodiment" or "an embodiment" mentioned throughout the specification means that specific features, structures or characteristics related to the embodiment are included in at least one embodiment of the present application. Therefore, "in one embodiment" or "in an embodiment" appearing throughout the specification does not necessarily refer to the same embodiment. In addition, these specific features, structures or characteristics can be combined in one or more embodiments in any suitable manner. It should be understood that in various embodiments of the present application, the size of the serial number of each step/process mentioned above does not mean the order of execution, and the execution order of each step/process should be determined by its function and internal logic, and should not constitute any limitation on the implementation process of the embodiment of the present application. The serial numbers of the embodiments of the present application mentioned above are for description only and do not represent the advantages and disadvantages of the embodiments.

It should be noted that, in this article, the terms "include", "comprises" or any other variations thereof are intended to cover non-exclusive inclusion, so that a process, method, article or device including a series of elements includes not only those elements, but also other elements not explicitly listed, or also includes elements inherent to such process, method, article or device. In the absence of further restrictions, an element defined by the sentence "comprises a ..." does not exclude the existence of other identical elements in the process, method, article or device including the element.

In the several embodiments provided in the present application, it should be understood that the disclosed devices and methods can be implemented in other ways. The device embodiments described above are only schematic. For example, the division of the units is only a logical function division. There may be other division methods in actual implementation, such as: multiple units or components can be combined, or can be integrated into another system, or some features can be ignored, or not executed. In addition, the coupling, direct coupling, or communication connection between the components shown or discussed can be through some interfaces, and the indirect coupling or communication connection of the devices or units can be electrical, mechanical or other forms.

The units described above as separate components may or may not be physically separated, and the components displayed as units may or may not be physical units; they may be located in one place or distributed on multiple network units; some or all of the units may be selected according to actual needs to achieve the purpose of the present embodiment.

In addition, all functional units in the embodiments of the present application may be integrated into one processing unit, or each unit may be a separate unit, or two or more units may be integrated into one unit; the above-mentioned integrated units may be implemented in the form of hardware or in the form of hardware plus software functional units.

A person of ordinary skill in the art can understand that all or part of the steps of implementing the above method embodiment can be completed by hardware related to program instructions, and the aforementioned program can be stored in a computer-readable storage medium. When the program is executed, it executes the steps of the above method embodiment; and the aforementioned storage medium includes: a mobile storage device, a read-only memory (ROM), a magnetic disk or an optical disk, and other media that can store program codes.

Alternatively, if the above-mentioned integrated unit of the present application is implemented in the form of a software function module and sold or used as an independent product, it can also be stored in a computer-readable storage medium. Based on this understanding, the technical solution of the present application can essentially or in other words, the part that contributes to the relevant technology can be embodied in the form of a software product, which is stored in a storage medium and includes a number of instructions for a computer device (which can be a personal computer, a server, or a network device, etc.) to execute all or part of the methods described in each embodiment of the present application. The aforementioned storage medium includes: various media that can store program codes, such as mobile storage devices, ROMs, magnetic disks, or optical disks.

The above is only an implementation method of the present application, but the protection scope of the present application is not limited thereto. Any technician familiar with the technical field can easily think of changes or substitutions within the technical scope disclosed in the present application, which should be included in the protection scope of the present application.

Claims (10)

1. A query method for target location users, characterized in that the method includes: Get the target area range to be queried; Convert the target area range into multiple one-dimensional value intervals through the S2 grid coverage algorithm; Find a set of candidate users whose location codes satisfy the multiple one-dimensional value intervals from a preset grid database; the grid database stores multiple user identifiers and location codes associated with each user; The target area range is used to filter the candidate user set, and target users located within the target area range are determined. 2. The method according to claim 1, characterized in that converting the range of the target area into multiple one-dimensional value intervals through the S2 grid coverage algorithm includes: Use the S2 grid coverage algorithm to determine N grids covered by the target area; where N is less than or equal to the preset maximum number of grids, and the level of each grid is at the preset minimum level. to the maximum level; Convert the S2 grid code of each grid into a one-dimensional value interval; The value intervals of adjacent grids among the N grids are connected end-to-end to obtain a merged M-segment one-dimensional value interval; where M is a natural number smaller than N. 3. The method according to claim 1, characterized in that, the method further comprises: Use the S2 geographical location coding system to encode the two-dimensional coordinates of each user to obtain the location code of the corresponding user; The identity of each user is used as a key, and the location of the corresponding user is encoded as a value and stored in the grid database. 4. The method according to claim 3, characterized in that the position encoding is a first-level grid precision, the grid database is an ordered set structure of Redis, and the value of the ordered set structure is a double Precision floating point type, the method also includes: For each user, convert the first-level grid-precision position code into a second-level grid-precision position code that matches the double-precision floating point type; The position code of the second-level grid precision is stored in the ordered set structure as a value associated with the corresponding user; wherein the grid corresponding to the second-level grid precision is the first-level The grid precision corresponds to the grid's parent grid. 5. The method according to claim 3, characterized in that the method further comprises: In response to the first user's two-dimensional coordinate update, encode the updated two-dimensional coordinates to obtain a new position code; A value in the grid database associated with the first user is updated with the new location encoding. 6. The method according to any one of claims 1 to 5, characterized in that the search for a set of candidate users whose location codes satisfy the multiple one-dimensional value intervals from the set grid database includes: For each one-dimensional value interval, search for users whose location codes belong to the corresponding one-dimensional value interval from the grid database, and obtain query results; the query results include the identification and association of the user position coding; The query results of the multiple one-dimensional value intervals are combined to obtain the candidate user set. 7. The method according to any one of claims 1 to 5, characterized in that the set of candidate users is screened using the target area range to determine the target users located within the target area range, include: For each candidate user in the candidate user set, if the boundary of the target area completely includes the minimum grid to which the corresponding candidate user's location belongs, the corresponding candidate user is determined to be the target user. 8. A query device for target location users, characterized in that the device includes: The acquisition module is used to obtain the target area range to be queried; A conversion module used to convert the target area range into multiple one-dimensional value intervals through the S2 grid coverage algorithm; A search module, configured to search from a preset grid database for a set of candidate users whose location codes satisfy the multiple one-dimensional value intervals; the grid database stores identifications of multiple users and information related to each user. associated position encoding; A screening module is configured to use the target area range to screen the candidate user set and determine target users located within the target area range. 9. A computer device, including a memory and a processor, the memory stores a computer program that can be run on the processor, characterized in that when the processor executes the program, any one of claims 1 to 7 is implemented steps in the method. 10. A computer-readable storage medium with a computer program stored thereon, characterized in that when the computer program is executed by a processor, the steps in the method of any one of claims 1 to 7 are implemented.