技术领域technical field
本发明属于空间数据存储及搜索技术领域，具体涉及一种基于二维地理位置的海量数据空间范围查询方法。The invention belongs to the technical field of spatial data storage and search, and in particular relates to a method for querying the spatial range of massive data based on two-dimensional geographic locations.
背景技术Background technique
在目前的大数据时代，一个系统的数据量达到TB级别甚至PB级别，面对海量数据，如何对其进行高效地存储、管理和搜索便成为一个技术难题。在传统关系型数据库上存储海量数据时，通常采用分片(Shard)逻辑实现，将同一数据库中的数据水平分片拆分到不同数据库中，以有效发挥多台服务器的性能。而数据库水平分片一方面能够有效发挥出多台服务器的性能，另一方面也给原本简单的查找逻辑带来了困难和效率问题，因此一个好的分片逻辑和相对应的查找逻辑至关重要。In the current era of big data, the amount of data in a system reaches TB level or even PB level. Faced with massive data, how to efficiently store, manage and search it has become a technical problem. When storing massive amounts of data on traditional relational databases, shard logic is usually used to split the data in the same database horizontally into different databases to effectively utilize the performance of multiple servers. On the one hand, the horizontal sharding of the database can effectively exert the performance of multiple servers, on the other hand, it also brings difficulties and efficiency problems to the original simple search logic. Therefore, a good sharding logic and corresponding search logic are crucial. important.
移动互联网的兴起促使越来越多的应用构建在移动平台之上，而移动端应用相较于传统PC端应用而言可以更好地和用户地理位置信息相结合，这也使得基于地理位置的搜索场景十分常见。一般而言地理位置信息采用经纬度坐标来表示，而二维数据查询没有办法使用传统的一维索引结构，因而较为经济高效的做法是将二维地理位置坐标使用GeoHash编码完成一维化处理。The rise of the mobile Internet has prompted more and more applications to be built on the mobile platform, and compared with traditional PC-side applications, mobile applications can be better combined with user location information, which also makes location-based Search scenarios are very common. Generally speaking, geographic location information is represented by latitude and longitude coordinates, but there is no way to use the traditional one-dimensional index structure for two-dimensional data query. Therefore, a more cost-effective method is to use GeoHash encoding to complete one-dimensional processing of two-dimensional geographic location coordinates.
GeoHash是由Gustavo Niemeyer提出的地理位置编码方法，其主要思想是将地球上的空间以经度和纬度两个维度进行二分，二分次数越多最终结果的精度就越高，最后将经度上的二分编码值和纬度上的二分编码值进行交叉合并，得到最后的GeoHash编码值。GeoHash编码实际上表示的是一个矩形区域，其编码长度越长，代表的矩形区域越小，并且对于两个GeoHash编码a和b，若a是b的前缀，则a代表的矩形区域完全包含b代表的矩形区域。GeoHash is a geographical location encoding method proposed by Gustavo Niemeyer. Its main idea is to divide the space on the earth into two dimensions of longitude and latitude. value and the binary coded value on the latitude are cross-merged to get the final GeoHash coded value. GeoHash codes actually represent a rectangular area, the longer the code length, the smaller the represented rectangular area, and for two GeoHash codes a and b, if a is the prefix of b, the rectangular area represented by a completely contains b Represents a rectangular area.
当前已有的基于GeoHash的地理位置查询，一般只是一个GeoHash方块的搜索，难以应对不规则的空间区域，同时也难以处理数据量较大时的场景。The current GeoHash-based geographic location query is generally only a GeoHash square search, which is difficult to deal with irregular spatial regions, and it is also difficult to deal with scenarios with a large amount of data.
发明内容Contents of the invention
鉴于上述，本发明提供了一种基于二维地理位置的海量数据空间范围查询方法，该方法通过两级索引查找，既有效应对了大数据环境下的分片场景，又能够应对不规则空间区域的快速查找场景。In view of the above, the present invention provides a method for querying the spatial range of massive data based on two-dimensional geographic location. The method can not only effectively deal with fragmentation scenarios in a big data environment, but also deal with irregular spatial regions through two-level index search. quick search scene.
一种基于二维地理位置的海量数据空间范围查询方法，包括如下步骤：A method for querying the spatial range of massive data based on two-dimensional geographic location, comprising the following steps:
(1)通过第一级索引搜索，首先定位到目标空间区域有可能落在的所有数据库分片，组成待搜索分片集合S；(1) Through the first-level index search, first locate all the database fragments that may fall in the target space area, and form the fragmentation set S to be searched;
(2)在待搜索分片集合S内使用第二级索引搜索，将落入目标空间范围的数据加入结果集R中；(2) Use the second-level index search in the fragment set S to be searched, and add the data falling into the target space range into the result set R;
(3)返回给出结果集R即搜索所得的目标数据。(3) Return the given result set R, that is, the target data obtained from the search.
进一步地，所述第一级索引采用GeoHash编码来构建，相应的分片逻辑也是根据GeoHash编码进行，以使得空间上相邻的数据尽可能存放在同一数据库分片上。Furthermore, the first-level index is constructed using GeoHash codes, and the corresponding fragmentation logic is also performed according to GeoHash codes, so that spatially adjacent data can be stored on the same database fragment as much as possible.
进一步地，所述第一级索引中的每一个节点都是一段GeoHash编码前缀，父节点的GeoHash编码必然是两个子节点GeoHash编码的前缀，即父节点代表的地理位置空间必然完全包含其子节点代表的地理位置空间。Further, each node in the first-level index is a GeoHash code prefix, and the GeoHash code of the parent node must be the prefix of the GeoHash codes of the two child nodes, that is, the geographic location space represented by the parent node must completely contain its child nodes Represents the geographic space.
进一步地，所述第二级索引采用类似线段树的思想进行组织，父节点所对应的空间范围完全包含其子节点对应的空间范围。Further, the second-level index is organized using an idea similar to a line segment tree, and the spatial range corresponding to a parent node completely includes the spatial range corresponding to its child nodes.
进一步地，所述第二级索引的构建过程为：对于待加入索引树的节点A，若当前索引树为空，则将其作为第一个节点加入索引树；若当前索引树非空，则进一步判断当前索引树根节点的GeoHash编码是不是节点A的GeoHash编码前缀：若不是，则将当前根节点和节点A的最长公共前缀作为父节点，当前根节点和节点A作为其两个子节点；若是，则搜索其根节点的左右子树，直到找到节点A应该插入的位置，此时若该位置为空，则将节点A插入，若该位置非空，则需要将该位置上已有的节点与节点A合并生成父节点后插入。Further, the construction process of the second-level index is: for the node A to be added to the index tree, if the current index tree is empty, add it as the first node to the index tree; if the current index tree is not empty, then Further judge whether the GeoHash code of the root node of the current index tree is the GeoHash code prefix of node A: if not, take the longest common prefix of the current root node and node A as the parent node, and the current root node and node A as its two child nodes ; If so, search the left and right subtrees of the root node until you find the position where node A should be inserted. At this time, if the position is empty, then insert node A. If the position is not empty, you need to have The node of is merged with node A to generate a parent node and then inserted.
进一步地，所述步骤(1)中第一级索引搜索的具体实现过程如下：Further, the specific implementation process of the first-level index search in the step (1) is as follows:
1.1采用二叉树搜索方式从索引根节点开始递归调用遍历搜索其左右子树，搜索到的每一个叶子节点即对应表示一个数据库分片；1.1 Use the binary tree search method to recursively call and traverse the left and right subtrees from the index root node, and each leaf node searched corresponds to a database fragment;
1.2若当前节点所表示的空间范围与目标空间区域存在交集且当前节点非叶子节点，则递归调用遍历搜索当前节点的左右子树，若不存在交集则直接回溯；1.2 If there is an intersection between the spatial range represented by the current node and the target spatial area and the current node is not a leaf node, recursively call to traverse and search the left and right subtrees of the current node, and directly backtrack if there is no intersection;
1.3若当前节点所表示的空间范围与目标空间区域存在交集且当前节点为叶子节点，则将当前节点对应的数据库分片加入待搜索分片集合S中，若不存在交集则直接回溯。1.3 If there is an intersection between the spatial range represented by the current node and the target spatial area and the current node is a leaf node, add the database fragment corresponding to the current node to the fragment set S to be searched, and directly backtrack if there is no intersection.
完成上述步骤后即得到一个待搜索的数据库分片集合S，一般来说，搜索的空间区域远远小于一个数据库分片表示的区域，因而S中通常只有一个数据库分片；但是由于GeoHash编码存在突变可能(即位置上相近的两个点，GeoHash编码值相距甚远)，因此集合S中有出现2个以上分片的可能。After completing the above steps, a set S of database fragments to be searched is obtained. Generally speaking, the search space area is much smaller than the area represented by a database fragment, so there is usually only one database fragment in S; however, due to the existence of GeoHash codes Mutations are possible (that is, the GeoHash encoding values of two points that are close to each other are far apart), so there may be more than 2 fragments in the set S.
进一步地，所述步骤(2)中第二级索引搜索的具体实现过程如下：Further, the specific implementation process of the second-level index search in the step (2) is as follows:
2.1采用二叉树搜索方式从索引根节点开始递归调用遍历搜索其左右子树；2.1 Use the binary tree search method to recursively call and traverse from the index root node to search its left and right subtrees;
2.2若当前节点所表示的空间范围完全被包含于目标空间区域内，则将当前节点所对应的数据加入结果集R中并进行回溯，若当前节点所表示的空间范围与目标空间区域不存在交集则直接回溯；2.2 If the spatial range represented by the current node is completely contained in the target spatial region, then add the data corresponding to the current node into the result set R and perform backtracking, if there is no intersection between the spatial range represented by the current node and the target spatial region directly trace back;
2.3若当前节点所表示的空间范围与目标空间区域存在交集，且当前节点为叶子节点或当前GeoHash编码长度已达到阈值M，则将当前节点所对应的数据加入结果集R中并进行回溯；2.3 If there is an intersection between the spatial range represented by the current node and the target spatial area, and the current node is a leaf node or the current GeoHash code length has reached the threshold M, then add the data corresponding to the current node to the result set R and perform backtracking;
2.4若当前节点所表示的空间范围与目标空间区域存在交集，且当前节点非叶子节点，当前GeoHash编码长度未达到阈值M，则递归调用遍历搜索当前节点的左右子树。2.4 If there is an intersection between the spatial range represented by the current node and the target spatial area, and the current node is not a leaf node, and the current GeoHash code length does not reach the threshold M, recursively call to traverse and search the left and right subtrees of the current node.
进一步地，所述阈值M根据数据量和相应速度需求动态调节。Further, the threshold M is dynamically adjusted according to the amount of data and corresponding speed requirements.
本发明海量数据空间范围查询方法能够在使用关系型数据库的情况下，有效应对大数据环境下基于地理位置的空间范围查询，查询效率较高，且无须构建复杂难以维护的二维空间索引。The method for querying the spatial range of massive data of the present invention can effectively cope with the spatial range query based on geographic location in a big data environment under the condition of using a relational database, the query efficiency is high, and there is no need to construct a complex and difficult to maintain two-dimensional spatial index.
附图说明Description of drawings
图1为本发明方法的整体流程示意图。Fig. 1 is the overall flow diagram of the method of the present invention.
图2为一级索引搜索示意图。Figure 2 is a schematic diagram of a first-level index search.
图3为GeoHash突变示意图。Figure 3 is a schematic diagram of GeoHash mutation.
图4为本发明空间范围搜索示意图。Fig. 4 is a schematic diagram of spatial range search in the present invention.
图5为二级索引构建示意图。Figure 5 is a schematic diagram of secondary index construction.
具体实施方式Detailed ways
为了更为具体地描述本发明，下面结合附图及具体实施方式对本发明的技术方案进行详细说明。In order to describe the present invention more specifically, the technical solutions of the present invention will be described in detail below in conjunction with the accompanying drawings and specific embodiments.
如图1所示，本发明基于二维地理位置的海量数据空间范围查询方法，具体包括以下步骤：As shown in Figure 1, the present invention is based on the two-dimensional geographic location massive data spatial scope query method, specifically comprises the following steps:
(1)根据第一级索引搜索，首先定位到目标空间区域所在的数据库分片。(1) According to the first-level index search, first locate the database fragment where the target space area is located.
为了应对海量数据场景，数据库需要做分片处理，以发挥出多台服务器的性能，而第一级索引的作用就是用于查找目标区域所在的数据库分片，具体的索引采用GeoHash编码来构建，相应的分片逻辑也是根据GeoHash编码值进行，以使得相邻位置数据更有可能分配到一个数据库分片上。In order to cope with massive data scenarios, the database needs to be fragmented to maximize the performance of multiple servers, and the first-level index is used to find the database fragment where the target area is located. The specific index is constructed using GeoHash encoding. The corresponding sharding logic is also based on the GeoHash coded value, so that adjacent location data is more likely to be assigned to a database shard.
其中，索引中的每一个节点都是一段GeoHash编码前缀，并且父节点的GeoHash编码必然是两个子节点GeoHash编码的前缀，也就是说，父节点代表的地理位置空间，必然完全包含其子节点代表的地理位置空间。Among them, each node in the index is a GeoHash code prefix, and the GeoHash code of the parent node must be the prefix of the GeoHash code of the two child nodes, that is to say, the geographic location space represented by the parent node must completely contain the geohash code represented by its child nodes. geographical space.
第一级索引的搜索过程具体包含以下步骤：The search process of the first-level index specifically includes the following steps:
1.1从索引根节点开始遍历索引左右子树。1.1 Traverse the left and right subtrees of the index starting from the root node of the index.
1.2若当前节点代表的空间范围和目标区域存在交集，且当前节点非叶子节点，则递归调用遍历其左右子树。1.2 If there is an intersection between the spatial range represented by the current node and the target area, and the current node is not a leaf node, recursively call to traverse its left and right subtrees.
1.3若当前节点代表的空间范围和目标区域无交集，则直接回溯。1.3 If there is no intersection between the spatial range represented by the current node and the target area, backtrack directly.
1.4若当前节点代表的空间范围和目标交集存在交集，且当前节点为叶子节点，则将当前节点代表的分片加入待搜索的分片集合S，并回溯。1.4 If there is an intersection between the spatial range represented by the current node and the target intersection, and the current node is a leaf node, add the fragment represented by the current node to the fragment set S to be searched, and backtrack.
完成上述步骤后即得到一个待搜索的数据库分片集合S，一般来说，搜索的空间区域远远小于一个数据库分片表示的区域，因而S中通常只有一个数据库分片。但是由于GeoHash存在突变可能(即位置上相近的两个点，GeoHash编码值相距甚远)，因此集合S中有可能出现2个以上分片的可能。After completing the above steps, a set S of database fragments to be searched is obtained. Generally speaking, the searched space area is much smaller than the area represented by one database fragment, so there is usually only one database fragment in S. However, due to the possibility of mutation in GeoHash (that is, two points that are close in position, the GeoHash encoding values are far apart), so there may be more than 2 fragments in the set S.
(2)在上一步骤所得的待搜索分片内使用第二级搜索继续搜索，将落入目标空间范围的数据加入结果集。(2) Use the second-level search to continue searching in the segment to be searched obtained in the previous step, and add the data falling into the target space range to the result set.
在得到待搜索的数据库分片集合S后，下一步使用第二级索引在具体分片内搜索数据，具体过程为：After obtaining the database shard set S to be searched, the next step is to use the second-level index to search for data in a specific shard. The specific process is as follows:
2.1从索引根节点开始搜索，递归调用搜索其左右子树。2.1 Start searching from the index root node, and recursively call to search its left and right subtrees.
2.2若当前节点所代表的空间区域完全包含于目标区域之内，则将当前节点所对应的数据加入结果集R，并回溯。2.2 If the spatial region represented by the current node is completely included in the target region, add the data corresponding to the current node into the result set R, and backtrack.
2.3若当前节点所代表空间区域和目标区域无交集，则直接回溯。2.3 If there is no intersection between the spatial area represented by the current node and the target area, backtrack directly.
2.4若当前节点所代表的空间区域和目标区域存在交集，且当前节点为叶子节点或者当前GeoHash长度已达到阈值M，则将当前节点对应的数据加入结果集R，并回溯。2.4 If there is an intersection between the spatial area represented by the current node and the target area, and the current node is a leaf node or the current GeoHash length has reached the threshold M, then add the data corresponding to the current node to the result set R, and backtrack.
2.5若当前节点所代表的目标区域和目标区域存在交集，当前节点非叶子节点并且当前GeoHash长度并未达到阈值M，则递归调用搜索其左右子树。2.5 If there is an intersection between the target area represented by the current node and the target area, the current node is not a leaf node and the current GeoHash length does not reach the threshold M, recursively call to search its left and right subtrees.
其中二级索引的构建过程包含以下步骤：The construction process of the secondary index includes the following steps:
①对于待加入索引树的节点a，若当前索引树为空，则其作为第一个节点加入索引树，若当前索引树非空，则需要根据以下情况判断。① For the node a to be added to the index tree, if the current index tree is empty, it will be added as the first node to the index tree. If the current index tree is not empty, it needs to be judged according to the following conditions.
②若当前索引树的根节点的GeoHash不是节点a的GeoHash编码的前缀，则将该根节点和节点a的最长公共前缀作为父节点，子节点分别是该跟节点和节点a。②If the GeoHash of the root node of the current index tree is not the prefix of the GeoHash code of node a, then the longest common prefix of the root node and node a is used as the parent node, and the child nodes are the root node and node a respectively.
③若当前索引树的根节点的GeoHash是节点a的GeoHash编码的前缀，则搜索其左右子树，直到找到节点a应该插入的位置，此时若该位置为空，则将节点a插入，若该位置非空，则需要将该位置的节点和节点a合并生成父节点并插入，这个过程需要向上不断调整。③If the GeoHash of the root node of the current index tree is the prefix of the GeoHash code of node a, then search its left and right subtrees until the position where node a should be inserted is found. If the position is empty at this time, then insert node a, if If the position is not empty, the node at this position needs to be merged with node a to generate a parent node and inserted. This process needs to be continuously adjusted upwards.
(3)返回结果集即搜索所得的目标数据。(3) The returned result set is the target data obtained from the search.
基于上述技术方案，在以下实施案例中，关系型数据库采用MySQL，其中需要进行空间范围查询的表结构如表1所示。Based on the above technical solution, in the following implementation cases, the relational database adopts MySQL, and the table structure that needs to be queried by spatial range is shown in Table 1.
表1Table 1
首先是一级索引的搜索过程，如图2所示，通常来说目标空间范围的大小远小于一个数据库分片表示的空间范围大小，因此一般待搜索的空间范围会落入到一个数据库分片中，但是由于GeoHash存在突变的可能，如图3所示，点b和点c的距离较点b和点a而言要近得多，而b和a属于同一GeoHash块，而b和c则不是，因此待搜索的空间范围也有可能落入多个数据库分片中，一级索引搜索得到待搜索的数据库分片集合S后，下一步在相应内的数据库分片内再进行搜索；在二级索引进行搜索时，具体步骤如下：The first is the search process of the first-level index, as shown in Figure 2. Generally speaking, the size of the target space range is much smaller than the size of the space range represented by a database fragment, so generally the space range to be searched will fall into a database fragment However, due to the possibility of mutation in GeoHash, as shown in Figure 3, the distance between point b and point c is much closer than point b and point a, and b and a belong to the same GeoHash block, while b and c are No, so the space range to be searched may also fall into multiple database fragments. After the first-level index search obtains the database fragmentation set S to be searched, the next step is to search in the corresponding database fragmentation; When searching on a level index, the specific steps are as follows:
(1)从索引根节点开始搜索，递归调用搜索其左右子树。(1) Start searching from the index root node, and recursively call to search its left and right subtrees.
(2)若当前节点所代表的空间区域完全包含于目标区域之内，则将当前节点所对应的数据加入结果集R，并回溯。(2) If the spatial region represented by the current node is completely included in the target region, add the data corresponding to the current node into the result set R, and backtrack.
(3)若当前节点所代表空间区域和目标区域无交集，则直接回溯。(3) If the spatial region represented by the current node has no intersection with the target region, backtrack directly.
(4)若当前节点所代表的空间区域和目标区域存在交集，且当前节点为叶子节点或者当前GeoHash长度已达到阈值M，则将当前节点对应的数据加入结果集R，并回溯。(4) If there is an intersection between the spatial region represented by the current node and the target region, and the current node is a leaf node or the current GeoHash length has reached the threshold M, then add the data corresponding to the current node to the result set R, and backtrack.
(5)若当前节点所代表的目标区域和目标区域存在交集，当前节点非叶子节点并且当前GeoHash长度并未达到阈值M，则递归调用搜索其左右子树。(5) If there is an intersection between the target area represented by the current node and the target area, the current node is not a leaf node and the current GeoHash length does not reach the threshold M, recursively call to search its left and right subtrees.
其空间范围搜索的对应效果如图4所示，其中大的矩形框为当前分片表示区域，色块相同的对应同一个索引节点，色块最小时则对应搜索到叶节点的情形，色块较大时，则为上述中的步骤(2)或者步骤(4)；实际上数据没有这么密集，还可以做进一步的简化。The corresponding effect of its spatial range search is shown in Figure 4, in which the large rectangular box is the current fragment representation area, the same color block corresponds to the same index node, and the smallest color block corresponds to the situation where a leaf node is searched, the color block When it is larger, it is step (2) or step (4) in the above; in fact, the data is not so dense, and further simplification can be made.
其中二级索引的构建过程如图5所示，假设当前索引树是step1中的情境，则10100加入时，当前索引树根节点1000并非10100的前缀，因此构建10100和根节点1000的共同前缀父节点10，即step2；然后10110加入，10100一路搜索到10的右子树，10100和10110构建共同最长前缀的父节点101，并插入索引树中，如step3所示。The construction process of the secondary index is shown in Figure 5. Assuming that the current index tree is the situation in step1, when 10100 is added, the root node 1000 of the current index tree is not the prefix of 10100, so the common prefix parent of 10100 and root node 1000 is constructed Node 10, that is, step2; then 10110 joins, 10100 searches all the way to the right subtree of 10, 10100 and 10110 build the parent node 101 with the longest common prefix, and insert it into the index tree, as shown in step3.
上述对实施例的描述是为便于本技术领域的普通技术人员能理解和应用本发明。熟悉本领域技术的人员显然可以容易地对上述实施例做出各种修改，并把在此说明的一般原理应用到其他实施例中而不必经过创造性的劳动。因此，本发明不限于上述实施例，本领域技术人员根据本发明的揭示，对于本发明做出的改进和修改都应该在本发明的保护范围之内。The above description of the embodiments is for those of ordinary skill in the art to understand and apply the present invention. It is obvious that those skilled in the art can easily make various modifications to the above-mentioned embodiments, and apply the general principles described here to other embodiments without creative efforts. Therefore, the present invention is not limited to the above embodiments, and improvements and modifications made by those skilled in the art according to the disclosure of the present invention should fall within the protection scope of the present invention.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810201147.5ACN108446357A (en) | 2018-03-12 | 2018-03-12 | A kind of mass data spatial dimension querying method based on two-dimentional geographical location |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810201147.5ACN108446357A (en) | 2018-03-12 | 2018-03-12 | A kind of mass data spatial dimension querying method based on two-dimentional geographical location |
| Publication Number | Publication Date |
|---|---|
| CN108446357Atrue CN108446357A (en) | 2018-08-24 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201810201147.5APendingCN108446357A (en) | 2018-03-12 | 2018-03-12 | A kind of mass data spatial dimension querying method based on two-dimentional geographical location |
| Country | Link |
|---|---|
| CN (1) | CN108446357A (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109783508A (en)* | 2018-12-29 | 2019-05-21 | 亚信科技（南京）有限公司 | Data query method, apparatus, computer equipment and storage medium |
| CN110211031A (en)* | 2019-06-05 | 2019-09-06 | 山东大学 | Method, system, storage medium and device for sampling multi-class scatter plots based on recursive partitioning |
| CN110704453A (en)* | 2019-10-15 | 2020-01-17 | 腾讯音乐娱乐科技（深圳）有限公司 | Data query method and device, storage medium and electronic equipment |
| CN112131373A (en)* | 2019-06-25 | 2020-12-25 | 杭州海康威视数字技术股份有限公司 | Information searching method and device, electronic equipment and readable storage medium |
| CN112948717A (en)* | 2021-05-13 | 2021-06-11 | 北京电信易通信息技术股份有限公司 | Massive space POI searching method and system based on multi-factor constraint |
| CN114461638A (en)* | 2022-01-13 | 2022-05-10 | 杭州网易云音乐科技有限公司 | Location index construction method, user determination method, apparatus, medium and device |
| CN114880350A (en)* | 2022-05-07 | 2022-08-09 | 高德软件有限公司 | Spatial data retrieval method, device, electronic device and storage medium |
| CN115630203A (en)* | 2022-12-12 | 2023-01-20 | 杭州数梦工场科技有限公司 | Method for generating n-ary tree and method and device for determining intersection relation |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20120226889A1 (en)* | 2011-03-01 | 2012-09-06 | Dwight Merriman | System and method for determining exact location results using hash encoding of multi-dimensioned data |
| CN105488172A (en)* | 2015-11-30 | 2016-04-13 | 北京奇艺世纪科技有限公司 | Location-based data query method and device |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20120226889A1 (en)* | 2011-03-01 | 2012-09-06 | Dwight Merriman | System and method for determining exact location results using hash encoding of multi-dimensioned data |
| CN105488172A (en)* | 2015-11-30 | 2016-04-13 | 北京奇艺世纪科技有限公司 | Location-based data query method and device |
| Title |
|---|
| 刘娜: ""一种基于NOSQL的遥感影像数据管理与分析系统"", 《中国优秀硕士学位论文全文数据库 信息科技辑》* |
| 易显天: ""基于patricia树的空间索引结构"", 《计算机工程》* |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109783508A (en)* | 2018-12-29 | 2019-05-21 | 亚信科技（南京）有限公司 | Data query method, apparatus, computer equipment and storage medium |
| CN109783508B (en)* | 2018-12-29 | 2021-04-09 | 亚信科技（南京）有限公司 | Data query method and device, computer equipment and storage medium |
| CN110211031A (en)* | 2019-06-05 | 2019-09-06 | 山东大学 | Method, system, storage medium and device for sampling multi-class scatter plots based on recursive partitioning |
| CN110211031B (en)* | 2019-06-05 | 2020-10-02 | 山东大学 | Multi-class scatter plot sampling method, system, storage medium and device based on recursive division |
| CN112131373A (en)* | 2019-06-25 | 2020-12-25 | 杭州海康威视数字技术股份有限公司 | Information searching method and device, electronic equipment and readable storage medium |
| CN110704453A (en)* | 2019-10-15 | 2020-01-17 | 腾讯音乐娱乐科技（深圳）有限公司 | Data query method and device, storage medium and electronic equipment |
| CN112948717A (en)* | 2021-05-13 | 2021-06-11 | 北京电信易通信息技术股份有限公司 | Massive space POI searching method and system based on multi-factor constraint |
| CN114461638A (en)* | 2022-01-13 | 2022-05-10 | 杭州网易云音乐科技有限公司 | Location index construction method, user determination method, apparatus, medium and device |
| CN114880350A (en)* | 2022-05-07 | 2022-08-09 | 高德软件有限公司 | Spatial data retrieval method, device, electronic device and storage medium |
| CN115630203A (en)* | 2022-12-12 | 2023-01-20 | 杭州数梦工场科技有限公司 | Method for generating n-ary tree and method and device for determining intersection relation |
| Publication | Publication Date | Title |
|---|---|---|
| CN108446357A (en) | A kind of mass data spatial dimension querying method based on two-dimentional geographical location | |
| US7634465B2 (en) | Indexing and caching strategy for local queries | |
| CN104199860B (en) | Dataset fragmentation method based on two-dimensional geographic position information | |
| CN107798054B (en) | A Trie-based range query method and device | |
| CN107291785A (en) | A kind of data search method and device | |
| CN108182242A (en) | A kind of indexing means for the inquiry of magnanimity multi dimensional numerical data area | |
| CN108549690B (en) | Spatial Keyword Query Method and System Based on Spatial Distance Constraint | |
| CN106503223B (en) | An online housing search method and device combining location and keyword information | |
| CN102521334A (en) | Data storage and query method based on classification characteristics and balanced binary tree | |
| CN112256821B (en) | Chinese address completion method, device, equipment and storage medium | |
| US12061658B2 (en) | Business searching methods and apparatuses, electronic devices and storage media | |
| CN114048204B (en) | Beidou grid spatial indexing method and device based on database inverted index | |
| CN110825830B (en) | Data retrieval method for grid space | |
| CN104182475B (en) | A kind of positional information method for quickly retrieving of encoding based on mask technology and subdivision | |
| CN106991149B (en) | A Massive Spatial Object Storage Method Integrating Encoding and Multi-version Data | |
| CN113535803B (en) | An Efficient Retrieval and Reliability Verification Method of Blockchain Based on Keyword Index | |
| CN104699946B (en) | A kind of management method and device of scene of game | |
| CN104539750A (en) | IP locating method and device | |
| CN104346444A (en) | Optimum site selection method based on road network reverse spatial keyword query | |
| CN115443657A (en) | A nearest neighbor search method, encoder, decoder and storage medium | |
| CN106570166A (en) | Video retrieval method and apparatus based on multiple partial sensitive hash tables | |
| CN113076334A (en) | Data query method, index generation device and electronic equipment | |
| CN116775722A (en) | Space-time retrieval method, device, equipment and medium based on multivariate data fusion | |
| CN106649425B (en) | A Vector Space Data Coding Method Considering Spatial Proximity | |
| CN114491056B (en) | Method and system for improving POI search in digital policing scenarios |
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| RJ01 | Rejection of invention patent application after publication | ||
| RJ01 | Rejection of invention patent application after publication | Application publication date:20180824 |