CN113849498B - Index construction and query method - Google Patents

Abstract

One or more embodiments of this specification provide an index construction and query method, including constructing a quad-tree structure according to a spatial data set; using a Z curve to perform data dimension reduction processing on the spatial data in a cell to obtain the spatial data of the spatial data. Data representation; sort the spatial data representation according to the Z value, and construct a linked list; perform data segmentation processing based on the linked list to obtain multiple data segments; construct a local model of each data segment, and determine the unit according to the local model of each data segment Lattice query model. On the basis of the constructed quad-tree structure, the data segmentation algorithm is used to divide the data segments, and the query model is constructed to reduce the space storage cost and improve the retrieval performance. Dynamic index building for dynamically updated spatial datasets.

Description

An index construction and query method

technical field

One or more embodiments of this specification relate to the technical field of data processing, and in particular, to an index construction and query method.

Background technique

IoT devices generate large amounts of geospatial data, and in order to efficiently access and process such data, spatial data is usually stored in a tree-type index structure. However, when the amount of data reaches PB level or more, the tree-shaped index structure grows rapidly, which seriously occupies system resources; on the other hand, the traditional tree-shaped index structure has better performance on static data, but cannot support dynamic index construction and renew.

SUMMARY OF THE INVENTION

In view of this, the purpose of one or more embodiments of this specification is to provide an index construction and query method, which can realize dynamic index construction.

Based on the above purpose, one or more embodiments of this specification provide an index construction method, including:

According to the spatial data set, construct a quadtree structure including at least one cell;

The spatial data in the cell is subjected to data dimensionality reduction processing by using the Z-curve to obtain a spatial data representation corresponding to the spatial data; wherein, the spatial data representation includes the coordinates and Z values of the spatial data;

Sorting the spatial data representation according to the Z value, and saving the sorted spatial data representation in a linked list;

Perform data segmentation processing based on the linked list to obtain at least one data segment;

A local model of each data segment is constructed, and a query model of the cell is determined according to the local model of each data segment.

Optionally, each node of the linked list includes a spatial data representation and its position in the linked list.

Optionally, performing data segmentation processing based on the linked list to obtain at least one data segment is: using the FSW algorithm to perform data segmentation on the nodes in the linked list to obtain at least one data segment.

Optionally, the local model of the data segment includes the position and Z value of the start point of the data segment, the position and Z value of the end point, and the slope calculated according to the start point and the end point.

Optionally, determining the query model of the cell according to the local model of each data segment is: performing data fitting on the local model of each data segment to generate the query model.

The embodiments of this specification also provide a range query method, which performs query based on the constructed index, including:

Query the quad-tree structure according to the input query rectangle, and determine the cells that have an intersection with the query rectangle;

Dividing the query rectangle into a plurality of sub-rectangles; wherein, the sub-rectangles are divided into sub-rectangles that completely coincide with the cells and sub-rectangles that partially coincide with the cells;

For the sub-rectangle that completely coincides with the cell, use the spatial data in the completely coincident cell as the query result;

For a sub-rectangle partially overlapping with a cell, query is performed according to the query model of the partially overlapping cell, and a query result is obtained.

Optionally, query according to the query model of the partially overlapping cells to obtain query results, including:

Determine the minimum Z value and the maximum Z value of the sub-rectangle partially coincident with the cell;

determining the range of possible positions of the maximum Z value and the minimum Z value in the query model;

It is judged whether the spatial data within the range of possible positions is within the range of the query rectangle, and the spatial data within the range of the query rectangle is used as a query result.

The embodiments of this specification also provide a nearest neighbor query method, which performs query based on the constructed index, including:

Query the quad-tree structure according to the input query data point, and determine the cell where the query data point is located;

Determine the initial distance according to the spatial density of the cell and the number of data points;

determining the smaller distance between the initial distance and a preset distance threshold, and constructing an initial query rectangle according to the query data point and the distance;

Using the initial query rectangle as the query rectangle of the range query method, obtain the range query result;

The nearest neighbor query result is determined according to the range query result.

Optionally, the nearest neighbor query result is determined according to the range query result, including:

Constructing an initial query circle with the query data point as the center and the distance as the radius;

Judging whether the spatial data in the range query result is within the range of the initial query circle, and using the spatial data within the initial query circle as an intermediate query result;

judging whether the amount of data in the intermediate query result reaches a predetermined amount;

If so, arrange according to the distance from the query data point from small to large, and select the predetermined number of data points from the sorted data points as the nearest neighbor query result;

If it is not reached, expand the initial distance, construct a secondary query rectangle according to the query data points and the expanded distance, perform a query using a range query method according to the secondary query rectangle, and obtain a range query result, based on the range The query result updates the intermediate query result until the amount of data in the intermediate query result reaches the predetermined amount.

Optionally, performing a query by using a range query method according to the secondary query rectangle, including:

According to the initial query rectangle and the secondary query rectangle, determine the unsearched area;

The query is performed using the unqueried area as the query rectangle of the range query method.

It can be seen from the above that the index construction and query method provided by one or more embodiments of this specification constructs a quad-tree structure according to a spatial data set; uses Z-curve to perform data dimensionality reduction on spatial data in a cell process to obtain the spatial data representation of the spatial data; sort the spatial data representation according to the Z value, and build a linked list; perform data segmentation processing based on the linked list to obtain multiple data segments; build a local model of each data segment, according to each data segment The local model of the segment, which determines the cell's query model. The method of this embodiment, on the basis of the constructed quad-tree structure, uses the data segmentation algorithm to divide the data segments, and constructs the query model, which reduces the space storage cost, improves the retrieval performance, and can quickly build an index by one-time data traversal, and improves the Index construction efficiency, suitable for dynamic index construction of dynamically updated spatial datasets.

Description of drawings

In order to more clearly illustrate one or more embodiments of the present specification or the technical solutions in the prior art, the following briefly introduces the accompanying drawings used in the description of the embodiments or the prior art. Obviously, in the following description The accompanying drawings are only one or more embodiments of the present specification, and for those of ordinary skill in the art, other drawings can also be obtained from these drawings without any creative effort.

1 is a schematic flowchart of a construction method according to one or more embodiments of this specification;

2 is a schematic diagram of an index building process according to one or more embodiments of the present specification;

3 is a schematic diagram of data partitioning in one or more embodiments of the present specification;

4A and 4B are schematic diagrams of dimensionality reduction and ordering of data according to one or more embodiments of this specification;

FIG. 5 is a schematic diagram of data segmentation according to one or more embodiments of the present specification;

FIG. 6 is a schematic diagram of a query model according to one or more embodiments of the present specification;

FIG. 7 is a schematic diagram of a scope query process according to one or more embodiments of this specification;

8A, 8B, and 8C are exemplary diagrams of a range query in one or more embodiments of the present specification;

9 is a schematic diagram of a KNN query process according to one or more embodiments of this specification;

10A, 10B, and 10C are exemplary diagrams of KNN queries according to one or more embodiments of this specification;

11 is a schematic structural diagram of an apparatus according to one or more embodiments of the specification;

FIG. 12 is a schematic structural diagram of an electronic device according to one or more embodiments of the specification.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present disclosure clearer, the present disclosure will be further described in detail below with reference to the specific embodiments and the accompanying drawings.

It should be noted that, unless otherwise defined, the technical or scientific terms used in one or more embodiments of the present specification shall have the usual meanings understood by those with ordinary skill in the art to which this disclosure belongs. The terms "first," "second," and similar terms used in one or more embodiments of this specification do not denote any order, quantity, or importance, but are merely used to distinguish the various components. "Comprises" or "comprising" and similar words mean that the elements or things appearing before the word encompass the elements or things recited after the word and their equivalents, but do not exclude other elements or things. Words like "connected" or "connected" are not limited to physical or mechanical connections, but may include electrical connections, whether direct or indirect. "Up", "Down", "Left", "Right", etc. are only used to represent the relative positional relationship, and when the absolute position of the described object changes, the relative positional relationship may also change accordingly.

As described in the background art section, the performance of the traditional tree index structure for large amount of spatial data drops sharply. Since the distribution characteristics of the spatial data are not considered, an appropriate index structure is not selected according to the data distribution characteristics. The introduction of machine learning algorithms has fundamentally changed the traditional index structure. However, some of the existing index construction methods do not support specific operations, and some are not suitable for dynamic index construction of dynamically updated spatial data.

In view of this, an embodiment of this specification provides an index construction method, which constructs a quad-tree structure according to a spatial data set, performs data dimensionality reduction processing on the cells of the quad-tree structure by using a Z curve, and sorts the spatial data according to the Z value. , build a linked list based on the sorted spatial data, segment the data for each node in the linked list, build a local model of each data segment, and determine the query model of the cell according to each local model; can quickly build an index, suitable for dynamic update Dynamic index building of spatial datasets.

As shown in Figures 1 and 2, the embodiments of this specification provide an index construction method, including:

S101: Construct a quadtree structure including at least one cell according to the spatial data set;

In this embodiment, according to the coordinates of the spatial data in the spatial data set, a quad-tree algorithm is used to divide the spatial data set into a quad-tree structure including a plurality of cells.

As shown in Figure 3, specifically, assuming the original spatial data set Data:Data={ki | _i =0,1,...,t}, the coordinates of the spatial data _{ki are (x i , y i ) ,} using The process of dividing the spatial data set by the quadtree algorithm is as follows: map all the data points in the spatial data set to the two-dimensional data space V=[X _l ,X _u )×[Y _l ,Y _u )∈R ² , calculate The data volume V _count of the two-dimensional data space V; determine whether the data volume V _count has reached the data volume threshold, if not, construct a cell according to the two-dimensional data space V, if it has reached, carry out equidistant to the two-dimensional data space V Divide to generate four sub-data spaces {NW, NE, SW, SE}, where NW=[X _l ,(X _l +X _u )/2)×[(Y _l +Y _u )/2,Y _u ) , NE=[(X _l +X _u )/2,X _u )×[(Y _l +Y _u )/2,Y _u ), SW=[X _l ,(X _l +X _u )/2)× [Y _l ,(Y _l +Y _u )/2), SE=[(X _l +X _u )/2,X _u )×[Y _l ,(Y _l +Y _u )/2); according to data points The coordinates of k _i are divided into corresponding sub-data spaces. After all data points are divided, all data points in each sub-data space are obtained. After that, for any sub-data space V∈{NW,NE,SW,SE}, according to the data amount in the sub-data space, determine whether the data amount reaches the data amount threshold, if so, continue to divide the sub-data space until If the amount of data in the divided data space is smaller than the data amount threshold, the division is stopped, and multiple divided cells are obtained.

S102: Perform data dimensionality reduction processing on the spatial data in the cell by using the Z-curve to obtain a spatial data representation corresponding to the spatial data; wherein, the spatial data representation includes coordinates and Z values of the spatial data;

In this embodiment, a Z-curve is used to perform data dimension reduction processing on the spatial data in each cell to obtain a one-dimensional spatial data representation of the spatial data.

4A and 4B, for the spatial data k _i (x _i , y _i ) in the cell, according to the mapping function of the Z curve, the Z value is calculated, which is expressed as:

According to the calculated Z value, determine the spatial data representation of the spatial data _ki

S103: Sort the spatial data representation according to the Z value, and save the sorted spatial data representation in the linked list;

In this embodiment, after the spatial data representation of the spatial data is determined, the spatial data representation is sorted according to the Z value in the spatial data representation from small to large, and the sorted spatial data representation is obtained, which can be represented as an ordered spatial data representation set

After obtaining the sorted spatial data representation, based on the sorted spatial data representation, construct a linked list List={(i,z _i , _ki )|i=0,1,...,n}, where i is the node in the linked list. The number of the point, that is, the position of the spatial data corresponding to the node in the linked list, _zi is the Z value of the _ith node, and ki is the spatial data of the ith node.

S104: Perform data segmentation processing based on the linked list to obtain at least one data segment;

S105: Build a local model of each data segment, and determine a query model of a cell according to the local model of each data segment.

In this embodiment, after the linked list is constructed, data segments are performed on each node in the linked list according to the data distribution law to obtain multiple data segments; for each data segment, a corresponding local model is constructed, and according to the local models of all data segments Determine the query model for the cell.

In some embodiments, the FSW algorithm (feasible space window, feasible space window) is used to perform data segmentation on the nodes in the linked list. The principle of the FSW algorithm is to initialize the first node of the linked list as the starting point of the first data segment, and the second node as the initial end point of the first data segment; according to predetermined rules, determine whether the third node is It can be added to the first data segment, and if it can be added, it continues to judge whether the next node can be added to the first data segment, until the next node cannot be added to the first data segment, and the divided first data segment is obtained. Afterwards, the next node is the starting point of the second data segment, and it continues to judge whether subsequent nodes can be added according to predetermined rules, until all nodes in the linked list are traversed, data segmentation is completed, and at least one data segment is obtained.

Specifically, the process of using the FSW algorithm to segment the data of the nodes in the linked list is: initializing the feasible interval S=FSW(k ₀ , k ₁ , ε), where ε is the maximum error threshold, and initializing the first data segment d ={k ₀ ,k ₁ }, the 0th node in the linked list is the starting point of the first data segment, and the first node is the initial end point; to determine whether the second node can be added to the first data segment, Calculate the feasible interval S'=FSW(k ₁ , k ₂ , ε) of the second node, and calculate S=S′∩S;

If S is not empty, it means that the second node conforms to the linear distribution, add the second node to the first data segment, and continue to judge whether the third node can be added to the first data segment until the next node cannot. The first data segment is added, and the segment of the first data segment ends. At this time, a local model L:L={l,u,z _l ,z _u ,θ} of the first data segment is constructed according to the first data segment, where l is the position of the starting point of the first data segment, and u is The position of the end point of the first data segment, z _l is the Z value of the start point, z _u is the Z value of the end point, and θ is the slope calculated according to the coordinates of the start point and the end point.

If S is empty, the second node does not conform to the linear distribution, and the first data segment is segmented; after the first data segment is segmented, the second data segment is divided again, and the initialized feasible interval S=FSW(k ₂ ,k ₃ ,ε), initialize the second data segment d={k ₂ ,k ₃ }, take the second node as the starting point of the second data segment, and the third node as the initial end of the second data segment point, determine whether the fourth node can be added to the second data segment, calculate the feasible interval S'=FSW(k ₃ , k ₄ , ε) of the fourth node, and calculate S=S′∩S.

As shown in Figures 5 and 6, according to the above process, each node in the linked list is segmented, and finally a plurality of data segments and a local model corresponding to each data segment are obtained. Then, based on the local model of each data segment, the query model of the cell is obtained by performing data fitting on the Z value. In some ways, a linear piecewise function can be used for data fitting, which can reduce the number of intermediate nodes in the index and the number of indirect queries, reduce the cost of index storage, and improve retrieval speed compared with the traditional tree index structure.

The index construction method provided by the embodiments of this specification includes constructing a quad-tree structure including at least one cell according to a spatial data set; performing data dimension reduction processing on the spatial data in the cell by using a Z-curve to obtain an index corresponding to the spatial data. Spatial data representation; sort the spatial data representation according to the Z value to obtain the sorted spatial data representation; construct a linked list according to the sorted spatial data representation; perform data segmentation processing based on the linked list to obtain at least one data segment; construct each The local model of the data segment determines the query model of the cell according to the local model of each data segment. On the basis of the constructed quadtree structure, the data segmentation algorithm is used to divide the data segments, and the query model is constructed to reduce the space storage cost and improve the retrieval performance. Dynamic index building for dynamically updated spatial datasets.

As shown in FIGS. 7, 8A, 8B, and 8C, in some embodiments, a range query can be performed based on the constructed index, and the range query method includes:

S701: Query the quad-tree structure according to the query rectangle, and determine the cells that have an intersection with the query rectangle;

In some embodiments, when performing a range query, a given query rectangle qr=[x _l , x _u )×[y _l , _yu ), where x _l represents the minimum boundary value in the x-axis direction, and x _u represents the x-axis direction _The maximum boundary value, yl represents the minimum boundary value in the y-axis direction, and _yu represents the maximum boundary value in the y-axis direction. The quad-tree structure is searched according to the query rectangle, and the cells that have the intersection with the query rectangle are determined.

S702: Divide the query rectangle into a plurality of sub-rectangles; wherein, the sub-rectangles are divided into sub-rectangles that completely overlap with the cells, and sub-rectangles that partially overlap with the cells;

In this embodiment, the query rectangle qr can be represented by the union of multiple sub-rectangles qr' _i :

According to the positional relationship between the sub-rectangle and the cell, the query rectangle can also be expressed as:

Among them, cr _i is the sub-rectangle that completely overlaps with the cell, lr _i is the sub-rectangle that partially overlaps the cell, Qc is the number of sub-rectangles that completely overlap the cell, and Ql is the quantity.

S703: For the sub-rectangle completely overlapping with the cell, use the spatial data in the completely overlapping cell as the query result;

S704: For the sub-rectangle partially overlapping with the cell, perform a query according to the query model of the partially overlapping cell to obtain a query result.

For the sub-rectangle that partially overlaps with the cell, the query is further performed according to the query model of the partially overlapped cell. The query method is to first calculate the minimum Z value and the maximum Z value in the sub-rectangular area; according to the range of the minimum Z value Z _min and the maximum Z value Z _max in the query model, determine the possible position range in the query model [p _min -ε,p _min +ε], [p _max -ε,p _max +ε], where ε is the confidence of the query model, it can be obtained that the possible position range of the sub-rectangle in the query model is [p _min -ε, p _max +ε].

As shown in FIG. 8B , since the possible position range of the sub-rectangle in the query model is larger than the actual range of the sub-rectangle, the spatial data within the possible position range needs to be verified, and the verified data is used as the query result. During verification, it is judged whether the spatial data within the range of possible positions is within the range of the query rectangle qr, the spatial data within the range of the query rectangle is used as the query result, and the spatial data not within the range of the query rectangle is filtered out; After all spatial data is filtered, the query results are obtained.

In some embodiments, a nearest neighbor query (KNN query) is performed based on the constructed index. Among them, the principle of KNN query is: given the query data point q _knn = (x, y) and the distance threshold δ, determine a circle with the query data point q _knn as the center and δ as the radius, and the circular area of the circle is defined as B(q _knn ,δ), determine the data points contained in the circular area B(q _knn ,δ), sort them according to the distance from the query data point q _knn from small to large, and select K from the sorted data points Data points as KNN query results.

As shown in Figures 9, 10A, 10B, and 10C, the method for performing KNN query based on the constructed index includes:

S901: Query the quad-tree structure according to the query data point, and determine the cell where the query data point is located;

S902: Determine the initial distance according to the spatial density of the cell and the number of data points;

所包含的空间数据的空间密度，表示为：The initial distance is very important for KNN query, if it is too large or too small, the query performance will be degraded. The index constructed in this embodiment is a quad-tree structure, and the spatial data is divided into equal amounts as much as possible, and the amount of data contained in each cell is not greater than the threshold of the amount of data. Therefore, a reasonable assumption can be made: the spatial data within the cell is roughly evenly distributed, and the cell is calculated on this basis.

The spatial density of the contained spatial data, expressed as:

ρ _i =Cell _i _count/((u _xi -l _xi )×(u _yi -l _yi )) (4)

u _xi represents the maximum value of the cell in the x-axis direction, u _yi represents the maximum value of the cell in the y-axis direction, l _xi represents the minimum value of the cell in the x-axis direction, and l _yi represents the cell in the y-axis direction the minimum value in the direction.

When the K spatial data in the ith cell are to be selected, the initial distance δ ₀ can be estimated according to the spatial density, which is expressed as:

S903: Determine the smaller distance between the initial distance and the distance threshold, and construct an initial query rectangle according to the query data point and the distance;

In this embodiment, after the initial distance is determined, a smaller distance δ'=min(δ ₀ ,δ) is selected from the initial distance and the distance threshold, and an initial query rectangle qr'=[x -δ',x+δ']×[y-δ',y+δ'].

S904: Using the initial query rectangle as the query rectangle of the range query method, obtain the range query result;

S905: Taking the query data point as the center and the distance as the radius, construct an initial query circle, determine whether the spatial data in the range query result is within the range of the initial query circle, and take the spatial data within the initial query circle as the center search result;

In this embodiment, the initial query circle B(q _knn ,δ') is determined with the query data point q _knn as the center and the distance δ' as the radius; if the range query result is r={k _i |i=0,1, ...,m}, calculate the distance between the spatial data _ki and the query data point, if the distance between the two is less than or equal to the distance δ', the spatial data _ki is in the initial query circular area, and the spatial data _ki is in the As an intermediate query result, if the distance between the two is greater than the distance δ', the spatial data _ki is outside the initial query circular area, and the spatial data _ki is filtered out.

圆形区域B(q_knn,δ)为矩形区域的内切圆，这样就将查询圆形区域内的数据点转换为查询矩形区域内的数据点。再利用范围查询方法获得查询矩形的范围查询结果之后，再根据范围查询结果确定出在圆形区域中的查询结果。In this embodiment, a rectangular area is constructed according to the query data point q _knn =(x, y) and the distance threshold δ

The circular area B(q _knn ,δ) is the inscribed circle of the rectangular area, so that the data points in the query circular area are converted into data points in the query rectangular area. After obtaining the range query result of the query rectangle by using the range query method, the query result in the circular area is determined according to the range query result.

S906: Determine whether the amount of data in the intermediate query results reaches K, if so, arrange them according to the distance from the query data points from small to large, and select K data points from the sorted data points as the KNN query result; Reach, expand the initial distance, construct a secondary query rectangle according to the query data points and the extended distance, perform the query using the range query method according to the secondary query rectangle, obtain the range query result, and update the intermediate query result based on the range query result, until The amount of data in the intermediate query results reaches K.

Wherein, using the range query method to perform the query according to the secondary query rectangle includes: determining the unqueried area according to the initial query rectangle and the secondary query rectangle;

In this embodiment, if the amount of data K' obtained according to the initial query rectangle does not reach K, the initial distance needs to be extended. Under the condition that the spatial density remains unchanged, the Lebesgue measure of the expanded quadratic query rectangle is K/K' times that of the initial query rectangle, and the expanded distance is obtained as:

The index constructed in this embodiment supports KNN query. By converting the circular area query into a rectangular area query, the range query result of the rectangular area is obtained by using the range query method, and the KNN query result is further screened according to the range query result.

It should be noted that the methods of one or more embodiments of this specification may be executed by a single device, such as a computer or a server. The method in this embodiment can also be applied in a distributed scenario, and is completed by the cooperation of multiple devices. In the case of such a distributed scenario, one device among the multiple devices may only execute one or more steps in the method of one or more embodiments of the present specification, and the multiple devices may perform operations on each other. interact to complete the described method.

It should be noted that the above describes specific embodiments of the present specification. Other embodiments are within the scope of the appended claims. In some cases, the actions or steps recited in the claims can be performed in an order different from that in the embodiments and still achieve desirable results. Additionally, the processes depicted in the figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In some embodiments, multitasking and parallel processing are also possible or may be advantageous.

As shown in FIG. 11 , an embodiment of the present specification further provides an index building apparatus, including:

a construction tree module for constructing a quadtree structure including at least one cell according to the spatial data set;

Dimensionality reduction processing, which is used to perform data dimensionality reduction processing on the spatial data in the cell by using the Z-curve to obtain the spatial data representation corresponding to the spatial data; wherein, the spatial data representation includes the coordinates and the Z value of the spatial data;

The sorting module is used to sort the spatial data representation according to the Z value, and save the sorted spatial data representation in the linked list;

The segmentation module is used to perform data segmentation processing based on the linked list to obtain at least one data segment;

The model building module is used to construct the local model of each data segment, and determine the query model of the cell according to the local model of each data segment.

For the convenience of description, when describing the above device, the functions are divided into various modules and described respectively. Of course, when implementing one or more embodiments of this specification, the functions of each module may be implemented in one or more software and/or hardware.

The apparatuses in the foregoing embodiments are used to implement the corresponding methods in the foregoing embodiments, and have the beneficial effects of the corresponding method embodiments, which will not be repeated here.

FIG. 12 shows a schematic diagram of a more specific hardware structure of an electronic device provided in this embodiment. The device may include: a processor 1010 , a memory 1020 , an input/output interface 1030 , a communication interface 1040 and a bus 1050 . The processor 1010 , the memory 1020 , the input/output interface 1030 and the communication interface 1040 realize the communication connection among each other within the device through the bus 1050 .

The processor 1010 may be implemented by a general-purpose CPU (Central Processing Unit, central processing unit), a microprocessor, an application specific integrated circuit (Application Specific Integrated Circuit, ASIC), or one or more integrated circuits, and is used to execute related program to implement the technical solutions provided by the embodiments of this specification.

The memory 1020 may be implemented in the form of a ROM (Read Only Memory, read only memory), a RAM (Random Access Memory, random access memory), a static storage device, a dynamic storage device, and the like. The memory 1020 may store an operating system and other application programs. When implementing the technical solutions provided by the embodiments of this specification through software or firmware, the relevant program codes are stored in the memory 1020 and invoked by the processor 1010 for execution.

The input/output interface 1030 is used to connect the input/output module to realize information input and output. The input/output/module can be configured in the device as a component (not shown in the figure), or can be externally connected to the device to provide corresponding functions. The input device may include a keyboard, a mouse, a touch screen, a microphone, various sensors, etc., and the output device may include a display, a speaker, a vibrator, an indicator light, and the like.

The communication interface 1040 is used to connect a communication module (not shown in the figure), so as to realize the communication interaction between the device and other devices. The communication module may implement communication through wired means (eg, USB, network cable, etc.), or may implement communication through wireless means (eg, mobile network, WIFI, Bluetooth, etc.).

Bus 1050 includes a path to transfer information between the various components of the device (eg, processor 1010, memory 1020, input/output interface 1030, and communication interface 1040).

It should be noted that although the above-mentioned device only shows the processor 1010, the memory 1020, the input/output interface 1030, the communication interface 1040 and the bus 1050, in the specific implementation process, the device may also include necessary components for normal operation. other components. In addition, those skilled in the art can understand that, the above-mentioned device may only include components necessary to implement the solutions of the embodiments of the present specification, rather than all the components shown in the figures.

The electronic devices in the foregoing embodiments are used to implement the corresponding methods in the foregoing embodiments, and have the beneficial effects of the corresponding method embodiments, which will not be repeated here.

The computer readable medium of this embodiment includes both permanent and non-permanent, removable and non-removable media and can be implemented by any method or technology for information storage. Information may be computer readable instructions, data structures, modules of programs, or other data. Examples of computer storage media include, but are not limited to, phase-change memory (PRAM), static random access memory (SRAM), dynamic random access memory (DRAM), other types of random access memory (RAM), read only memory (ROM), Electrically Erasable Programmable Read Only Memory (EEPROM), Flash Memory or other memory technology, Compact Disc Read Only Memory (CD-ROM), Digital Versatile Disc (DVD) or other optical storage, Magnetic tape cassettes, magnetic tape magnetic disk storage or other magnetic storage devices or any other non-transmission medium that can be used to store information that can be accessed by a computing device.

It should be understood by those of ordinary skill in the art that the discussion of any of the above embodiments is only exemplary, and is not intended to imply that the scope of the present disclosure (including the claims) is limited to these examples; under the spirit of the present disclosure, the above embodiments or Technical features in different embodiments may also be combined, steps may be carried out in any order, and there are many other variations of the different aspects of one or more embodiments of this specification as described above, which are not in detail for the sake of brevity supply.

Additionally, in order to simplify illustration and discussion, and in order not to obscure one or more embodiments of this specification, the figures provided may or may not be shown in connection with integrated circuit (IC) chips and other components. Well known power/ground connection. Furthermore, devices may be shown in block diagram form in order to avoid obscuring one or more embodiments of this description, and this also takes into account the fact that details regarding the implementation of such block diagram devices are highly dependent on the implementation of the invention (ie, these details should be well within the understanding of those skilled in the art) of the platform describing one or more embodiments. Where specific details (eg, circuits) are set forth to describe exemplary embodiments of the present disclosure, it will be apparent to those skilled in the art that these specific details may be used without or with variations One or more embodiments of this specification are implemented below. Accordingly, these descriptions are to be considered illustrative rather than restrictive.

Although the present disclosure has been described in conjunction with specific embodiments thereof, many alternatives, modifications, and variations to these embodiments will be apparent to those of ordinary skill in the art from the foregoing description. For example, other memory architectures (eg, dynamic RAM (DRAM)) may use the discussed embodiments.

The embodiment or embodiments of this specification are intended to cover all such alternatives, modifications and variations that fall within the broad scope of the appended claims. Therefore, any omission, modification, equivalent replacement, improvement, etc. made within the spirit and principle of one or more embodiments of the present specification should be included within the protection scope of the present disclosure.

Claims (6)

1. A nearest neighbor query method, characterized in that, comprising: Query the quad-tree structure according to the input query data point, and determine the cell where the query data point is located; Determine the initial distance according to the spatial density of the cell and the number of data points; determining the smaller distance between the initial distance and a preset distance threshold, and constructing an initial query rectangle according to the query data point and the distance; Using the initial query rectangle as the query rectangle of the range query method, obtain the range query result; Determine the nearest neighbor query result according to the range query result; Wherein, determining the nearest neighbor query result according to the range query result includes: Constructing an initial query circle with the query data point as the center and the distance as the radius; Judging whether the spatial data in the range query result is within the range of the initial query circle, and using the spatial data within the initial query circle as an intermediate query result; judging whether the amount of data in the intermediate query result reaches a predetermined amount; If so, arrange according to the distance from the query data point from small to large, and select the predetermined number of data points from the sorted data points as the nearest neighbor query result; If it is not reached, expand the initial distance, construct a secondary query rectangle according to the query data points and the expanded distance, perform a query using a range query method according to the secondary query rectangle, and obtain a range query result, based on the range The query result updates the intermediate query result until the amount of data in the intermediate query result reaches the predetermined amount. 2. The method according to claim 1, wherein the query is performed by using a range query method according to the secondary query rectangle, comprising: According to the initial query rectangle and the secondary query rectangle, determine the unsearched area; The query is performed using the unqueried area as the query rectangle of the range query method. 3. The method according to claim 1, wherein the nearest neighbor query method performs a query based on an index constructed by the following method, comprising: According to the spatial data set, construct a quadtree structure including at least one cell; The spatial data in the cell is subjected to data dimensionality reduction processing by using the Z-curve to obtain a spatial data representation corresponding to the spatial data; wherein, the spatial data representation includes the coordinates and Z values of the spatial data; Sort the spatial data representation according to the Z value, and store the sorted spatial data representation in a linked list; Perform data segmentation processing based on the linked list to obtain at least one data segment; A local model of each data segment is constructed, and according to the local model of each data segment, data fitting is performed on the Z value by using the current piecewise function to determine the query model of the cell. 4. The method according to claim 3, wherein each node of the linked list includes a spatial data representation and its position in the linked list. 5. The method according to claim 3, wherein, performing data segmentation processing based on the linked list, and obtaining at least one data segment is: adopting FSW algorithm to perform data segmentation on the nodes in the linked list, obtaining at least one data segment. a data segment. 6. The method according to claim 3 or 5, wherein the local model of the data segment comprises the position and Z value of the starting point of the data segment, the position and Z value of the ending point, according to the starting point and the Z value. The calculated slope of the end point.

Images