CN118673195A - Data searching method, device, computer equipment and storage medium - Google Patents

Abstract

The present invention relates to a data search method, device, computer equipment and storage medium. The method comprises: determining a target grid where the target point is located from multiple grids according to the coordinates of the target point; determining a target hash value corresponding to the target point according to the location information of the target grid; when the target hash value is less than or equal to the parameter value of the maximum hash value parameter, determining multiple first neighboring bucket hash values of the target hash value according to the target hash value and the first hash value offset of each preset direction; determining at least one target first neighboring bucket hash value from the multiple first neighboring bucket hash values, and searching for the nearest neighbor point corresponding to the target point from a first bucket set, the first bucket set comprising: a target bucket corresponding to the target hash value, a first neighboring bucket corresponding to each target first neighboring bucket hash value, and the target bucket corresponding to the target hash value and the first neighboring bucket corresponding to the target first neighboring bucket hash value in the target hash table.

Description

Data search method, device, computer equipment and storage medium

Technical Field

The present invention relates to the field of computer technology, and in particular to a data search method, device, computer equipment and storage medium.

Background Art

Nearest neighbor search, i.e. searching for other points closest to a given point, is a common operation in some software systems such as autonomous driving systems. In related technologies, a tree structure is established, and each point is regarded as a node in the tree structure. The nearest neighbor search needs to traverse a large number of nodes, and sometimes the entire tree structure, resulting in low efficiency of the nearest neighbor search. How to improve the efficiency of the nearest neighbor search has become a problem that needs to be solved.

Summary of the invention

One of the purposes of the present invention is to provide a data search method, apparatus, computer device and storage medium to solve the problem of how to improve the efficiency of nearest neighbor search.

In order to achieve the above object, the technical solution adopted by the present invention is as follows:

According to the coordinates of the target point, a target grid where the target point is located is determined from multiple grids;

According to the location information of the target grid, determine the target hash value corresponding to the target point;

When the target hash value is less than or equal to the parameter value of the maximum hash value parameter, determining a plurality of first adjacent bucket hash values of the target hash value according to the target hash value and the first hash value offset in each preset direction;

At least one target first neighboring bucket hash value is determined from the multiple first neighboring bucket hash values, and the nearest neighbor point corresponding to the target point is searched from the first bucket set, wherein the first bucket set includes: a target bucket corresponding to the target hash value, and a first neighboring bucket corresponding to each target first neighboring bucket hash value, wherein the target bucket corresponding to the target hash value and the first neighboring bucket corresponding to the target first neighboring bucket hash value are in a target hash table.

According to the above technical means, the target bucket corresponding to the target hash value corresponds to the target grid where the target point is located, and the first neighboring bucket corresponding to the target first neighboring bucket hash value corresponds to the grid surrounding the target grid. Searching for the nearest neighbor point corresponding to the target point from the first bucket set consisting of the target bucket corresponding to the target hash value and the first neighboring bucket corresponding to each target first neighboring bucket hash value is equivalent to searching for the nearest neighbor point corresponding to the target point from the points stored in the target hash table of a small number of grids consisting of the target grid and the grids surrounding the target grid. Reduce the number of points involved in the nearest neighbor search and improve the efficiency of the nearest neighbor search.

Furthermore, it also includes:

When the nearest neighbor point corresponding to the target point is not found from the first bucket set, determining multiple second neighboring bucket hash values of the target hash value according to the target hash value corresponding to the target point and the second hash value offset in each preset direction;

At least one target second neighboring bucket hash value is determined from the multiple second neighboring bucket hash values, and the nearest neighbor point corresponding to the target point is searched from the second bucket set, the second bucket set including: a second neighboring bucket corresponding to each target second neighboring bucket hash value, wherein the second neighboring bucket corresponding to the target second neighboring bucket hash value is in the target hash table.

Further, before determining at least one target first adjacent bucket hash value from the plurality of first adjacent bucket hash values, the method further includes:

Determine whether the target bucket exists in the target hash table;

If not, create the target bucket and store the target bucket in the target hash table.

Furthermore, it also includes:

When the target hash value is greater than the parameter value of the maximum hash value parameter, the parameter value of the maximum hash value parameter is updated to the target hash value.

Furthermore, it also includes:

The maximum hash value offset of each preset direction is determined according to the target hash value and the parameter value of the maximum hash value parameter, wherein for each preset direction, the maximum hash value offset of the preset direction is used to determine the corresponding hash value offset of the preset direction.

A data search device, characterized in that the data search device comprises:

A first determining unit, configured to determine a target grid where the target point is located from a plurality of grids according to the coordinates of the target point;

A second determining unit, configured to determine a target hash value corresponding to the target point according to the location information of the target grid;

A third determining unit, configured to determine a plurality of first adjacent bucket hash values of the target hash value according to the target hash value and the first hash value offset in each preset direction when the target hash value is less than or equal to the parameter value of the maximum hash value parameter;

A fourth determination unit is used to determine at least one target first neighboring bucket hash value from the multiple first neighboring bucket hash values, and to search for the nearest neighbor point corresponding to the target point from the first bucket set, wherein the first bucket set includes: a target bucket corresponding to the target hash value, and a first neighboring bucket corresponding to each target first neighboring bucket hash value, wherein the target bucket corresponding to the target hash value and the first neighboring bucket corresponding to the target first neighboring bucket hash value are in the target hash table.

Furthermore, the data search device also includes:

A continuing search unit is used to determine multiple second neighboring bucket hash values of the target hash value according to the target hash value corresponding to the target point and the second hash value offset of each preset direction when the nearest neighbor point corresponding to the target point is not found from the first bucket set; determine at least one target second neighboring bucket hash value from the multiple second neighboring bucket hash values, and search for the nearest neighbor point corresponding to the target point from the second bucket set, the second bucket set including: a second neighboring bucket corresponding to each target second neighboring bucket hash value, wherein the second neighboring bucket corresponding to the target second neighboring bucket hash value is in the target hash table.

Furthermore, the data search device also includes:

The fifth determining unit is used to determine whether the target bucket exists in the target hash table before determining at least one target first adjacent bucket hash value from the multiple first adjacent bucket hash values; if not, create the target bucket and store the target bucket in the target hash table.

Furthermore, the data search device also includes:

An updating unit is configured to update the parameter value of the maximum hash value parameter to the target hash value when the target hash value is greater than the parameter value of the maximum hash value parameter.

Furthermore, the data search device also includes:

The sixth determining unit is used to determine the maximum hash value offset of each preset direction according to the target hash value and the parameter value of the maximum hash value parameter, wherein for each preset direction, the maximum hash value offset of the preset direction is used to determine the corresponding hash value offset of the preset direction.

A computer device comprising:

A memory and a processor, wherein the memory and the processor are communicatively connected to each other, the memory stores computer instructions, and the processor executes the above method by executing the computer instructions.

A computer-readable storage medium stores computer instructions, and the computer instructions are used to enable a computer to execute the above method.

A computer program product, characterized in that it includes computer instructions, wherein the computer instructions are used to enable a computer to execute the above method.

Beneficial effects of the present invention:

The target bucket corresponding to the target hash value corresponds to the target grid where the target point is located, and the first neighboring bucket corresponding to the target first neighboring bucket hash value corresponds to the grids around the target grid. Searching for the nearest neighbor point corresponding to the target point from the first bucket set consisting of the target bucket corresponding to the target hash value and the first neighboring bucket corresponding to each target first neighboring bucket hash value is equivalent to searching for the nearest neighbor point corresponding to the target point from the points stored in the target hash table of a small number of grids consisting of the target grid and the grids around the target grid. Reduce the number of points involved in the nearest neighbor search and improve the efficiency of the nearest neighbor search.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a schematic diagram of a flow chart of a data search method provided by an embodiment of the present invention;

FIG2 is a schematic diagram of multiple grids and hash values corresponding to the multiple grids;

FIG3 is a schematic diagram of a plurality of first neighboring bucket hash values of a target hash value;

FIG4 is a schematic diagram of a flow chart of another data search method provided by an embodiment of the present invention;

FIG5 is a schematic diagram of the hardware structure of a computer device provided in an embodiment of the present invention.

DETAILED DESCRIPTION

The following will describe the embodiments of the present invention with reference to the accompanying drawings and preferred embodiments. Those skilled in the art can easily understand other advantages and effects of the present invention from the contents disclosed in this specification. The present invention can also be implemented or applied through other different specific embodiments, and the details in this specification can also be modified or changed in various ways based on different viewpoints and applications without departing from the spirit of the present invention. It should be understood that the preferred embodiments are only for illustrating the present invention, not for limiting the scope of protection of the present invention.

It should be noted that the illustrations provided in the following embodiments are only schematic illustrations of the basic concept of the present invention, and thus the drawings only show components related to the present invention rather than being drawn according to the number, shape and size of components in actual implementation. In actual implementation, the type, quantity and proportion of each component may be changed arbitrarily, and the component layout may also be more complicated.

Referring to FIG. 1 , there is shown a schematic flow chart of a data search method provided by an embodiment of the present invention.

In step S101, according to the coordinates of the target point, a target grid where the target point is located is determined from a plurality of grids.

The coordinates of the target point are the coordinates in the pre-established two-dimensional coordinate system. The point to which the coordinates of the target point belong is in the pre-established two-dimensional coordinate system.

As an example, the positioning function in the autonomous driving function needs to search for the nearest neighbor point corresponding to the target point. The pre-established two-dimensional coordinate system is established based on the road surface. The coordinates of the target point can represent the position of an object on the road surface, and the coordinates of the nearest neighbor point corresponding to the target point represent the position of the object on the road surface that is closest to the object.

In the embodiment of the present invention, the grid where the target point is located is called the target grid.

In the embodiment of the present invention, the plurality of grids are obtained by dividing a region in a pre-established two-dimensional coordinate system.

The shape of each grid may be a square, and each grid may have the same side length.

In the embodiment of the present invention, the position information of the target grid where the target point is located can be determined according to the side length of the grid, thereby determining the target grid.

A plurality of grids may form a grid array. The location information of the target grid may be represented by: the row of the grid array where the target grid is located, and the column of the grid array where the target grid is located.

The location information of the target grid may include: the serial number of the row of the grid array where the target grid is located, and the serial number of the column of the grid array where the target grid is located.

The location information of the target grid can be determined using the following formula:

hx=floor(abs(x)/bucketWidth_);

hy=floor(abs(y)/bucketWidth_).

Among them, hx represents the row number of the grid array where the target grid is located, hy represents the column number of the grid array where the target grid is located, bucketWidth is the side length of the grid, x is the coordinate value of the horizontal axis of the coordinate system of the target point in the two-dimensional coordinate system, that is, the px axis, y is the coordinate value of the vertical axis of the coordinate system of the target point in the two-dimensional coordinate system, that is, the py axis, and floor() means rounding down.

In step S102, a target hash value corresponding to the target point is determined according to the position information of the target grid.

In the embodiment of the present invention, the hash value corresponding to the target point is called the target hash value.

The target hash value corresponding to the target point is: the hash value corresponding to the target grid.

The target hash value corresponding to the target point, that is, the hash value corresponding to the target grid, can be calculated using the following formula:

hash_value=hx*factor+hy.

Among them, hash_value is the target hash value, factor is a preset large constant, hx represents the serial number of the row of the grid array where the target grid is located, and hy represents the serial number of the column of the grid array where the target grid is located.

In the embodiment of this specification, the target hash table includes: a bucket.

Each bucket in the target hash table has a different storage location in the target hash table. Each bucket in the target hash table corresponds to a different hash value.

For a bucket in the target hash table, the bucket is at a storage location corresponding to the hash value corresponding to the bucket.

Each bucket in the target hash table corresponds to a different grid.

Each grid corresponds to a different hash value.

For a bucket in the target hash table, the hash value corresponding to the bucket is: the hash value of the grid corresponding to the bucket.

For a grid, the hash value corresponding to the grid is: the hash value corresponding to the point in the grid.

For a grid, each point in the grid corresponds to the same hash value, and the coordinates of each point in the grid are stored in a bucket located at a storage position corresponding to the same hash value, and the bucket located at the storage position corresponding to the same hash value is the bucket corresponding to the grid.

Refer to FIG2 , which shows a schematic diagram of multiple grids and hash values corresponding to the multiple grids.

FIG. 2 shows the horizontal coordinate axis of the two-dimensional coordinate system, i.e., the px axis, and the vertical coordinate axis, i.e., the py axis. FIG. 2 shows a plurality of grids, which constitute a grid array. Each grid is a square. The number in the grid is the hash value corresponding to the grid, i.e., the hash value corresponding to the point in the grid. For example, the hash value corresponding to the grid with the number 4005 in the grid is 4005, and the hash value corresponding to each point in the grid with the number 4005 in the grid is 4005. The hash value corresponding to the grid with the number 5005 in the grid is 5005, and the hash value corresponding to each point in the grid with the number 5005 in the grid is 5005. The hash value corresponding to the grid with the number 6005 in the grid is 6005, and the hash value corresponding to each point in the grid with the number 6005 in the grid is 6005. If the grid with the number 5005 in the grid is the target grid, the maximum hash value offset in the left direction is 5, the maximum hash value offset in the right direction is 4, the maximum hash value offset in the lower direction is 5, and the maximum hash value offset in the upper direction is 4.

In a possible implementation, before determining at least one target first neighboring bucket hash value from a plurality of first neighboring bucket hash values, the method further includes: determining whether a target bucket exists in a target hash table; if it is determined that the target bucket does not exist in the target hash table, creating a target bucket, and storing the target bucket in the target hash table. Thus, it is not necessary to create buckets of all storage locations in the target hash table in order to perform a nearest neighbor search, thereby improving the convenience of the nearest neighbor search.

In step S103, when the target hash value is less than or equal to the parameter value of the maximum hash value parameter, a plurality of first adjacent bucket hash values of the target hash value are determined according to the target hash value and the first hash value offset in each preset direction.

The parameter value of the maximum hash value parameter indicates the maximum hash value corresponding to the bucket in the target hash table. That is, the parameter value of the maximum hash value parameter indicates the maximum hash value in the hash value set composed of the hash values corresponding to each bucket in the target hash table.

It should be noted that the maximum hash value corresponding to the bucket in the target hash table should be understood as a variable.

In step S103, the target hash value is compared with the parameter value of the maximum hash value parameter. When the target hash value is less than or equal to the parameter value of the maximum hash value parameter, multiple first adjacent bucket hash values of the target hash value are determined according to the target hash value and the first hash value offset in each preset direction.

In the embodiment of the present invention, the preset direction is a horizontal direction or a vertical direction. There are four preset directions, namely, up, down, left, and right.

It should be noted that the left direction can be called the negative direction of the X axis in the two-dimensional coordinate system. The right direction can be called the positive direction of the X axis in the two-dimensional coordinate system. The upper direction can be called the positive direction of the Y axis in the two-dimensional coordinate system. The lower direction can be called the negative direction of the Y axis in the two-dimensional coordinate system.

The first Hash value offset of each preset direction may be determined according to the preset first Hash value offset of each preset direction.

For each preset direction, whether the preset first hash value offset of the preset direction is a positive integer or a negative integer is preset.

For each preset direction, the preset first hash value offset of the preset direction is preset.

In the embodiment of the invention, the absolute value of the preset first hash value offset in each preset direction may be the same value.

As an example, the absolute value of the preset first hash value offset in each preset direction is 1.

For each preset direction, whether the preset first hash value offset of the preset direction is a positive integer or a negative integer is preset.

In the embodiment of the invention, the absolute value of the preset first hash value offset in each preset direction may be the same value.

As an example, the absolute value of the preset first hash value offset in each preset direction is 1.

The preset first Hash value offset in the left direction is a negative integer, the preset first Hash value offset in the right direction is a positive integer, the preset first Hash value offset in the downward direction is a negative integer, and the preset first Hash value offset in the upward direction is a positive integer.

In the embodiment of the present invention, for a preset direction, if the preset first hash value offset of the preset direction is less than or equal to the maximum hash value offset of the preset direction, the preset first hash value offset of the preset direction may be determined as the first hash value offset of the preset direction.

In the embodiment of the present invention, for a preset direction, if the preset first hash value offset of the preset direction is greater than the maximum hash value offset of the preset direction, the maximum hash value offset of the preset direction may be determined as the first hash value offset of the preset direction.

In an embodiment of the present invention, for a preset direction, the maximum hash value offset of the preset direction may be: the sequence number of the last grid in the preset direction in the grid array minus the sequence number of the target grid in the preset direction. The sequence number of the last grid in the preset direction is i, indicating that the last grid in the preset direction is the i+1th grid in the preset direction. The sequence number of the target grid in the preset direction is j, indicating that the target grid is the j+1th grid in the preset direction.

In a possible implementation, the method further includes: determining a maximum hash value offset of each preset direction according to the target hash value and the parameter value of the maximum hash value parameter, wherein for each preset direction, the maximum hash value offset of the preset direction is used to determine a corresponding hash value offset of the preset direction. Thus, the maximum hash value offset of the preset direction can be quickly determined.

The maximum hash value offset in the left direction can be calculated using the following formula:

expend_x_l=floor(hash_value/factor_)*-1.

Among them, expend_x_l is the maximum hash value offset in the left direction, hash_value is the target hash value, and factor is a preset large constant.

The maximum hash value offset in the right direction can be calculated using the following formula:

expend_x_r=floor((max_hash-hash_value)/factor);

Among them, expend_x_l represents the maximum hash value offset in the right direction, hash_value is the target hash value, factor is a preset large constant, and max_hash is the parameter value of the maximum hash value parameter.

The maximum hash value offset in the downward direction can be calculated using the following formula and recorded as expend_y_d:

expend_y_d=(hash_value%factor)*-1;

Among them, expend_y_d is the maximum hash value offset in the downward direction, hash_value is the target hash value, and factor is a preset large constant.

The maximum hash value offset in the upward direction can be calculated using the following formula:

expend_y_u=(max_hash-hash_value)%factor.

Among them, expend_y_u is the maximum hash value offset in the upward direction, hash_value is the target hash value, and factor is a preset large constant.

In step S103, a first interval with the first hash value offset in the right direction as the right endpoint and the first hash value offset in the left direction as the left endpoint can be determined. Each positive integer in the first interval is used as a first hash value offset in the first interval. A second interval with the first hash value offset in the upper direction as the right endpoint and the first hash value offset in the lower direction as the left endpoint can be determined. Each positive integer in the second interval is used as a first hash value offset in the second interval. The first hash value offset in the first interval can be combined with the first hash value offset in the second interval to obtain multiple first hash value offset combinations. The first neighboring bucket hash value corresponding to each first hash value offset combination is calculated, and the first neighboring bucket hash value corresponding to each first hash value offset combination is used as multiple first neighboring bucket hash values of the target hash value.

In the embodiment of the present invention, the following formula may be used to calculate the first adjacent bucket hash value corresponding to a first hash value offset combination:

neighborHash＝hash_value+dx*factor+dy

Among them, neighborHash is the first neighboring bucket hash value corresponding to the first hash value offset combination, hash_value is the target hash value, dx is the first hash value offset in the first interval of the first hash value offset combination, and dy is the first hash value offset in the second interval of the first hash value offset combination.

As an example, the first hash value offset in the upward direction is 1, the first hash value offset in the downward direction is -1, the first hash value offset in the left direction is -1, and the first hash value offset in the right direction is 1. Determine a first interval with the first hash value offset in the right direction as the right endpoint and the first hash value offset in the left direction as the left endpoint, and the first interval is [-1, 1]. Determine a second interval with the first hash value offset in the upward direction as the right endpoint and the first hash value offset in the downward direction as the left endpoint, and the second interval is [-1, 1]. Take each positive integer in the first interval, i.e., -1, 0, 1, as a first hash value offset in a first interval. Take each positive integer in the second interval, i.e., -1, 0, 1, as a first hash value offset in a second interval. The first hash value offset in the first interval can be combined with the first hash value offset in the second interval to obtain multiple first hash value offset combinations. The plurality of first hash value offset combinations include: a first hash value offset combination consisting of a first hash value offset in a first interval of -1 and a first hash value offset in a second interval of -1, a first hash value offset combination consisting of a first hash value offset in a first interval of -1 and a first hash value offset in a second interval of 0, and a first hash value offset combination consisting of a first hash value offset in a first interval of -1 and a first hash value offset in a second interval of 1. The plurality of first hash value offset combinations also include: a first hash value offset combination consisting of a first hash value offset in a first interval of 0 and a first hash value offset in a second interval of -1, a first hash value offset combination consisting of a first hash value offset in a first interval of 0 and a first hash value offset in a second interval of 0, and a first hash value offset combination consisting of a first hash value offset in a first interval of 0 and a first hash value offset in a second interval of 1. The multiple first hash value offset combinations also include: a first hash value offset combination consisting of a first hash value offset in a first interval of 1 and a first hash value offset in a second interval of -1, a first hash value offset combination consisting of a first hash value offset in a first interval of 1 and a first hash value offset in a second interval of 0, and a first hash value offset combination consisting of a first hash value offset in a first interval of 1 and a first hash value offset in a second interval of 1.

If the first hash value offset in the upward direction is 1, the first hash value offset in the downward direction is -1, the first hash value offset in the left direction is -1, and the first hash value offset in the right direction is 1, the process of calculating the first adjacent bucket hash value corresponding to each first hash value offset combination can be expressed by the following pseudo code:

for(intdx＝1;dx<=1;x++){

for(intdy＝-1; dy＝1; y++)

{

intneighborHash=(hash_value+dx*factor+dy)

}

}

Referring to FIG. 3 , it shows a schematic diagram of multiple first neighboring bucket hash values of a target hash value.

In this example, the first hash value offset in the upward direction is 1, the first hash value offset in the downward direction is -1, the first hash value offset in the left direction is -1, and the first hash value offset in the right direction is 1. The target hash value is 5005, and the factor is 1000. The target hash value is 5005. FIG. 3 shows a target grid and grids around the target grid. FIG. 3 shows a target hash value corresponding to the target grid, i.e., 5005. FIG. 3 shows multiple first neighboring bucket hash values of the target hash value calculated by calculating the target hash value corresponding to a target point according to the above formula for calculating the hash value corresponding to a point. The multiple first neighboring bucket hash values of the target hash value include: 5005+0*1000+1, i.e., 5006, 5005+0*1000-1, i.e., 5004, 5005-1*1000+1, i.e., 4006, 5005-1*1000+0, i.e., 4005, 5005-1*1000-1, i.e., 4004, 5005+1*1000+1, i.e., 6006, 5005+1*1000+0, i.e., 6005, 5005+1*1000-1, i.e., 6004. The grid corresponding to the first neighboring bucket hash value is the grid around the target grid. The point to which the coordinates in the first neighboring bucket corresponding to the first neighboring bucket hash value belong is the point in the grid corresponding to the first neighboring bucket hash value. For example, the grid whose corresponding first neighboring bucket hash value is 5006 is the grid closest to the target grid in the upper direction. The grid whose corresponding first neighboring bucket hash value is 5004 is the grid closest to the target grid in the downward direction. The grid whose corresponding first neighboring bucket hash value is 4005 is the grid closest to the target grid in the left direction. The grid whose corresponding first neighboring bucket hash value is 6005 is the grid closest to the target grid in the right direction.

In a possible implementation, the method further includes: when the target hash value is greater than the parameter value of the maximum hash value parameter, updating the parameter value of the maximum hash value parameter to the target hash value. Thus, the target hash value can be used for subsequent nearest neighbor searches for the nearest neighbor points corresponding to other points.

In step S104, at least one target first neighboring bucket hash value is determined from the plurality of first neighboring bucket hash values, and the nearest neighbor point corresponding to the target point is searched from the first bucket set.

In step S104, for a first neighboring bucket hash value, it can be determined whether there is a bucket at the storage location corresponding to the first neighboring bucket hash value in the target hash table. If there is a bucket at the storage location corresponding to the first neighboring bucket hash value, the first neighboring bucket hash value can be determined as the target first neighboring bucket hash value.

The first bucket set includes: a target bucket corresponding to the target hash value, and a first adjacent bucket corresponding to each target first adjacent bucket hash value.

The target bucket corresponding to the target hash value is stored in the storage location corresponding to the target hash value in the target hash table.

For a target first-neighboring bucket hash value, the first neighboring bucket corresponding to the target first-neighboring bucket hash value is stored in the storage location corresponding to the target first-neighboring bucket hash value in the target hash table.

In step S104 , in order to find the nearest neighbor point corresponding to the target point from the first bucket set, a point set of the first bucket set may be determined.

The point set of the first bucket set includes: the point to which each coordinate in the target bucket corresponding to the target hash value belongs, and the point set of the first neighboring bucket corresponding to each target first neighboring bucket hash value.

For a target first neighboring bucket hash value, the point set of the first neighboring bucket corresponding to the target first neighboring bucket hash value includes: the point to which each coordinate in the first neighboring bucket corresponding to the target first neighboring bucket hash value belongs.

In step S104, if the point set of the first bucket set is an empty set, it can be determined that no nearest neighbor point corresponding to the target point is found in the first bucket set.

In step S104, if the point set of the first bucket set is not an empty set, the Euclidean distance between each point in the point set of the first bucket set and the target point can be calculated. The point in the point set of the first bucket set with the smallest Euclidean distance to the target point can be determined, and the point with the smallest Euclidean distance to the target point is determined as the nearest neighbor point corresponding to the target point.

Referring to FIG. 4 , there is shown a schematic flow chart of another data search method provided by an embodiment of the present invention.

In step S401, according to the coordinates of the target point, a target grid where the target point is located is determined from multiple grids.

The process of step S401 refers to the process of step S101.

In step S402, a target hash value corresponding to the target point is determined according to the location information of the target grid.

The process of step S402 refers to the process of step S102.

In step S403, when the target hash value is less than or equal to the parameter value of the maximum hash value parameter, a plurality of first adjacent bucket hash values of the target hash value are determined according to the target hash value and the first hash value offset in each preset direction.

The process of step S403 refers to the process of step S103.

In step S404, at least one target first neighboring bucket hash value is determined from the plurality of first neighboring bucket hash values, and the nearest neighbor point corresponding to the target point is searched from the first bucket set.

The process of step S404 refers to the process of step S104.

In step S405, when the nearest neighbor point corresponding to the target point is not found from the first bucket set, multiple second neighboring bucket hash values of the target hash value are determined according to the target hash value corresponding to the target point and the second hash value offset in each preset direction.

As an example, the second Hash value offset in the upward direction is 2, the second Hash value offset in the downward direction is -2, the second Hash value offset in the left direction is -2, and the second Hash value offset in the right direction is 2.

It should be noted that, in the embodiment of the present invention, multiple k-th neighboring bucket hash values of the target hash value can be determined according to the target hash value corresponding to the target point and the k-th hash value offset of each preset direction. The k-th hash value offset of each preset direction can be determined according to the preset k-th hash value offset of each preset direction.

For each preset direction, the absolute value of the preset kth hash value offset of the preset direction is greater than the absolute value of the preset k-1th hash value offset of the preset direction, and the result of subtracting the absolute value of the preset k-1th hash value offset of the preset direction from the absolute value of the preset k-1th hash value offset of the preset direction is the preset search radius increment value.

For each preset direction, whether the preset second hash value offset of the preset direction is a positive integer or a negative integer is preset.

For each preset direction, the preset second hash value offset of the preset direction is preset.

In the embodiment of the invention, the absolute value of the preset second hash value offset in each preset direction may be the same value.

As an example, the absolute value of the preset second hash value offset in each preset direction is 2.

For each preset direction, the absolute value of the preset second Hash value offset of the preset direction is greater than the absolute value of the preset first Hash value offset of the preset direction, and the result of subtracting the absolute value of the preset first Hash value offset of the preset direction from the absolute value of the preset second Hash value offset of the preset direction is the preset search radius increment value. As an example, the preset search radius increment value is 1.

In the embodiment of the present invention, for a preset direction, if the preset second hash value offset of the preset direction is less than or equal to the maximum hash value offset of the preset direction, the preset second hash value offset of the preset direction may be used as the second hash value offset of the preset direction.

In the embodiment of the present invention, for a preset direction, if the preset second hash value offset of the preset direction is greater than the maximum hash value offset of the preset direction, the maximum hash value offset of the preset direction may be used as the second hash value offset of the preset direction.

In step S405, a first set consisting of a second hash value offset in the right direction and a second hash value offset in the left direction may be determined. A second set consisting of a second hash value offset in the upper direction and a second hash value offset in the lower direction may be determined. The second hash value offset in the first set is combined with the second hash value offset in the second set to obtain a plurality of second hash value offset combinations. The second adjacent bucket hash value corresponding to each second hash value offset combination is calculated, and the second adjacent bucket hash value corresponding to each second hash value offset combination is used as a plurality of second adjacent bucket hash values of the target hash value.

In the embodiment of the present invention, the following formula may be used to calculate the second adjacent bucket hash value corresponding to a second hash value offset combination:

neighborHash’=hash_value+dx’*factor+dy’

Among them, neighborHash’ is the second neighbor bucket hash value corresponding to the second hash value offset combination, hash_value is the target hash value, dx’ is the second hash value offset belonging to the first set in the second hash value offset combination, and dy’ is the second hash value offset belonging to the second set in the second hash value offset combination.

In step S406, at least one target second neighboring bucket hash value is determined from the plurality of second neighboring bucket hash values, and the nearest neighbor point corresponding to the target point is searched from the second bucket set.

The second bucket set includes: a second adjacent bucket corresponding to each target second adjacent bucket hash value.

The second adjacent bucket corresponding to the target second adjacent bucket hash value is in the target hash table.

In step S406, for a second adjacent bucket hash value, it can be determined whether there is a bucket at the storage location corresponding to the second adjacent bucket hash value in the target hash table. If there is a bucket at the storage location corresponding to the second adjacent bucket hash value, the second adjacent bucket hash value can be determined as the target second adjacent bucket hash value.

For a target second-neighboring bucket hash value, the second-neighboring bucket corresponding to the target second-neighboring bucket hash value is stored in the target hash table at a storage location corresponding to the target second-neighboring bucket hash value.

In step S406 , in order to find the nearest neighbor point corresponding to the target point from the second bucket set, a point set of the second bucket set may be determined.

The point set of the second bucket set includes: the point set of the second neighboring bucket corresponding to each target second neighboring bucket hash value.

For a target second neighboring bucket hash value, the point set of the second neighboring bucket corresponding to the target second neighboring bucket hash value includes: the point to which each coordinate in the second neighboring bucket corresponding to the target second neighboring bucket hash value belongs.

In step S406, if the point set of the second bucket set is an empty set, it can be determined that no nearest neighbor point corresponding to the target point is found in the second bucket set.

In step S406, if the point set of the second bucket set is not an empty set, the Euclidean distance between each point in the point set of the second bucket set and the target point can be calculated. The point in the point set of the second bucket set with the smallest Euclidean distance to the target point can be determined, and the point with the smallest Euclidean distance to the target point is determined as the nearest neighbor point corresponding to the target point.

Through step S405 to step S406, when the nearest neighbor point corresponding to the target point is not found from the first bucket set, the nearest neighbor point corresponding to the target point can be continuously searched.

A data search device is also provided in an embodiment of the present invention, and the device is used to implement the above-mentioned method embodiment and preferred implementation mode, which have been described and will not be repeated here. As used below, the term "unit" can implement a combination of software and/or hardware of a predetermined function. Although the device described in the following embodiments is preferably implemented in software, the implementation of hardware, or a combination of software and hardware, is also possible and conceived. The device in the embodiment of the present invention is presented in the form of a functional unit, where the functional unit refers to an ASIC (Application Specific Integrated Circuit) circuit, a processor and memory that executes one or more software or fixed programs, and/or other devices that can provide the above-mentioned functions.

A data search device, characterized in that the data search device comprises:

A first determining unit, configured to determine a target grid where the target point is located from a plurality of grids according to the coordinates of the target point;

A second determining unit, configured to determine a target hash value corresponding to the target point according to the location information of the target grid;

A third determining unit, configured to determine a plurality of first adjacent bucket hash values of the target hash value according to the target hash value and the first hash value offset in each preset direction when the target hash value is less than or equal to the parameter value of the maximum hash value parameter;

A fourth determination unit is used to determine at least one target first neighboring bucket hash value from the multiple first neighboring bucket hash values, and to search for the nearest neighbor point corresponding to the target point from the first bucket set, wherein the first bucket set includes: a target bucket corresponding to the target hash value, and a first neighboring bucket corresponding to each target first neighboring bucket hash value, wherein the target bucket corresponding to the target hash value and the first neighboring bucket corresponding to the target first neighboring bucket hash value are in the target hash table.

Furthermore, the data search device also includes:

A continuing search unit is used to determine multiple second neighboring bucket hash values of the target hash value according to the target hash value corresponding to the target point and the second hash value offset in each preset direction when the nearest neighboring point corresponding to the target point is not found from the first bucket set; determine at least one target second neighboring bucket hash value from the multiple second neighboring bucket hash values, and search for the nearest neighboring point corresponding to the target point from the second bucket set, the second bucket set including: a second neighboring bucket corresponding to each target second neighboring bucket hash value, wherein the second neighboring bucket corresponding to the target second neighboring bucket hash value is in the target hash table.

Furthermore, the data search device also includes:

The fifth determining unit is used to determine whether the target bucket exists in the target hash table before determining at least one target first adjacent bucket hash value from the multiple first adjacent bucket hash values; if not, create the target bucket and store the target bucket in the target hash table.

Furthermore, the data search device also includes:

An updating unit is configured to update the parameter value of the maximum hash value parameter to the target hash value when the target hash value is greater than the parameter value of the maximum hash value parameter.

Furthermore, the data search device also includes:

The sixth determining unit is used to determine the maximum hash value offset of each preset direction according to the target hash value and the parameter value of the maximum hash value parameter, wherein for each preset direction, the maximum hash value offset of the preset direction is used to determine the corresponding hash value offset of the preset direction.

Referring to FIG. 5 , FIG. 5 is a schematic diagram of the hardware structure of a computer device provided by an embodiment of the present invention. The computer device includes: one or more processors 10, a memory 20, and interfaces for connecting various components, including high-speed interfaces and low-speed interfaces. The various components communicate with each other using different buses and can be installed on a common motherboard or installed in other ways as needed. The processor can process instructions executed in the computer device, including instructions stored in or on the memory to display graphical information of the GUI on an external input/output device (such as a display device coupled to the interface). In some optional embodiments, if necessary, multiple processors and/or multiple buses can be used with multiple memories and multiple memories. Similarly, multiple vehicles can be connected, and each device provides some necessary operations (for example, as a server array, a group of blade servers, or a multi-processor system). The processor 10 can be a central processing unit, a network processor, or a combination thereof. Among them, the processor 10 can further include a hardware chip. The above-mentioned hardware chip can be a dedicated integrated circuit, a programmable logic device, or a combination thereof. The above-mentioned programmable logic device can be a complex programmable logic device, a field programmable gate array, a general array logic, or any combination thereof. The memory 20 stores instructions executable by at least one processor 10 so that the at least one processor 10 executes the method shown in the above embodiment. The memory 20 may include a program storage area and a data storage area, wherein the program storage area may store an operating system, an application required by at least one function; the data storage area may store data created according to the use of the vehicle, etc. In addition, the memory 20 may include a high-speed random access memory, and may also include a non-transient memory, such as at least one disk storage device, a flash memory device, or other non-transient solid-state storage devices. In some optional embodiments, the memory 20 may optionally include a memory remotely arranged relative to the processor 10, and these remote memories may be connected to the computer device via a network. Examples of the above network include, but are not limited to, the Internet, an intranet, a local area network, a mobile communication network, and combinations thereof. The memory 20 may include a volatile memory, such as a random access memory; the memory may also include a non-volatile memory, such as a flash memory, a hard disk or a solid-state hard disk; the memory 20 may also include a combination of the above-mentioned types of memory. The computer device also includes an input device 30 and an output device 40. The processor 10, the memory 20, the input device 30, and the output device 40 may be connected via a bus or in other ways. The input device 30 can receive input digital or character information, and generate key signal input related to the user settings and function control of the computer device, such as a touch screen, a keypad, a mouse, a track pad, a touch pad, an indicator bar, one or more mouse buttons, a trackball, a joystick, etc. The output device 40 may include a display device, an auxiliary lighting device (e.g., an LED) and a tactile feedback device (e.g., a vibration motor), etc. The above-mentioned display device includes but is not limited to a liquid crystal display, a light emitting diode, a display and a plasma display. In some optional embodiments, the display device can be a touch screen.

The embodiment of the present invention also provides a computer-readable storage medium. The method according to the embodiment of the present invention can be implemented in hardware, firmware, or can be implemented as a computer code that can be recorded in a storage medium, or can be implemented as a computer code that is originally stored in a remote storage medium or a non-temporary machine-readable storage medium and will be stored in a local storage medium through network download, so that the method described herein can be stored in such software processing on a storage medium using a general-purpose computer, a dedicated processor, or programmable or dedicated hardware. Among them, the storage medium can be a magnetic disk, an optical disk, a read-only storage memory, a random access memory, a flash memory, a hard disk or a solid-state hard disk, etc.; further, the storage medium can also include a combination of the above types of memories. It can be understood that a computer, a processor, a microprocessor controller or programmable hardware includes a storage component that can store or receive software or computer code. When the software or computer code is accessed and executed by a computer, a processor or hardware, the method shown in the above embodiment is implemented.

A portion of the embodiments of the present invention may be applied as a computer program product, such as a computer program instruction, which, when executed by a computer, can call or provide the method and/or technical solution according to the present invention through the operation of the computer. Those skilled in the art should understand that the existence of computer program instructions in computer-readable media includes, but is not limited to, source files, executable files, installation package files, etc., and accordingly, the way in which computer program instructions are executed by a computer includes, but is not limited to: the computer directly executes the instruction, or the computer compiles the instruction and then executes the corresponding compiled program, or the computer reads and executes the instruction, or the computer reads and installs the instruction and then executes the corresponding installed program. Here, the computer-readable medium may be any available computer-readable storage medium or communication medium accessible to the computer.

The above embodiments are only preferred embodiments for fully illustrating the present invention, and the protection scope of the present invention is not limited thereto. Any equivalent substitution or change made by a person skilled in the art based on the present invention is within the protection scope of the present invention.

Claims (10)

1. A data search method, characterized in that: the method comprises: According to the coordinates of the target point, a target grid where the target point is located is determined from multiple grids; According to the location information of the target grid, determine the target hash value corresponding to the target point; When the target hash value is less than or equal to the parameter value of the maximum hash value parameter, determining a plurality of first adjacent bucket hash values of the target hash value according to the target hash value and the first hash value offset in each preset direction; At least one target first neighboring bucket hash value is determined from the multiple first neighboring bucket hash values, and the nearest neighbor point corresponding to the target point is searched from the first bucket set, wherein the first bucket set includes: a target bucket corresponding to the target hash value, and a first neighboring bucket corresponding to each target first neighboring bucket hash value, wherein the target bucket corresponding to the target hash value and the first neighboring bucket corresponding to the target first neighboring bucket hash value are in a target hash table. 2. The method according to claim 1, characterized in that: the method further comprises: When the nearest neighbor point corresponding to the target point is not found from the first bucket set, determining multiple second neighboring bucket hash values of the target hash value according to the target hash value corresponding to the target point and the second hash value offset in each preset direction; At least one target second neighboring bucket hash value is determined from the multiple second neighboring bucket hash values, and the nearest neighbor point corresponding to the target point is searched from the second bucket set, the second bucket set including: a second neighboring bucket corresponding to each target second neighboring bucket hash value, wherein the second neighboring bucket corresponding to the target second neighboring bucket hash value is in the target hash table. 3. The method according to claim 1, characterized in that before determining at least one target first adjacent bucket hash value from the plurality of first adjacent bucket hash values, the method further comprises: Determine whether the target bucket exists in the target hash table; If not, create the target bucket and store the target bucket in the target hash table. 4. The method according to claim 1, characterized in that: the method further comprises: When the target hash value is greater than the parameter value of the maximum hash value parameter, the parameter value of the maximum hash value parameter is updated to the target hash value. 5. The method according to any one of claims 1 to 4, characterized in that: the method further comprises: The maximum hash value offset of each preset direction is determined according to the target hash value and the parameter value of the maximum hash value parameter, wherein for each preset direction, the maximum hash value offset of the preset direction is used to determine the corresponding hash value offset of the preset direction. 6. A data search device, characterized in that: the device comprises: A first determining unit, configured to determine a target grid where the target point is located from a plurality of grids according to the coordinates of the target point; A second determining unit, configured to determine a target hash value corresponding to the target point according to the location information of the target grid; A third determining unit, configured to determine a plurality of first adjacent bucket hash values of the target hash value according to the target hash value and the first hash value offset in each preset direction when the target hash value is less than or equal to the parameter value of the maximum hash value parameter; A fourth determination unit is used to determine at least one target first neighboring bucket hash value from the multiple first neighboring bucket hash values, and to search for the nearest neighbor point corresponding to the target point from the first bucket set, wherein the first bucket set includes: a target bucket corresponding to the target hash value, and a first neighboring bucket corresponding to each target first neighboring bucket hash value, wherein the target bucket corresponding to the target hash value and the first neighboring bucket corresponding to the target first neighboring bucket hash value are in the target hash table. 7. The device according to claim 6, characterized in that the device further comprises: A continuing search unit is used to determine multiple second neighboring bucket hash values of the target hash value according to the target hash value corresponding to the target point and the second hash value offset in each preset direction when the nearest neighboring point corresponding to the target point is not found from the first bucket set; determine at least one target second neighboring bucket hash value from the multiple second neighboring bucket hash values, and search for the nearest neighboring point corresponding to the target point from the second bucket set, the second bucket set including: a second neighboring bucket corresponding to each target second neighboring bucket hash value, wherein the second neighboring bucket corresponding to the target second neighboring bucket hash value is in the target hash table. 8. A computer device, comprising: A memory and a processor, wherein the memory and the processor are communicatively connected to each other, the memory stores computer instructions, and the processor executes the method according to any one of claims 1 to 5 by executing the computer instructions. 9. A computer-readable storage medium, characterized in that computer instructions are stored on the computer-readable storage medium, and the computer instructions are used to enable a computer to execute any one of the methods of claims 1 to 5. 10 . A computer program product, comprising computer instructions, wherein the computer instructions are used to cause a computer to execute the method according to claim 1 .