KR20010109945A - RS-tree for k-nearest neighbor queries with non spatial selection predicates and method for using it - Google Patents

Abstract

The present invention discloses a method for improving the performance of the incremental nearest index method (algorithm) proposed by Jalthason and Samet, and an RS tree structure that can be applied to the query effectively.

According to the present invention, a multimedia database is used for a query in a conventional database by significantly reducing an unnecessary tuple occurrence frequency, which is a problem of an incremental close proximity method based on an R tree proposed by Hjaltason and Samet. Effective indexing of multidimensional spatial objects required by geographic information systems is possible.

Description

RS-tree for k-nearest neighbor queries with non spatial selection predicates and method for using it}

The present invention can reduce the number of tuple occurrences, which is a problem of the incremental nearest neighbor algorithm proposed by Hjaltason and Samet, which is used as an indexing method in a multimedia database or a GIS. The present invention relates to an index method that enables an efficient search on a spatial object set.

Recently, multimedia data retrieval devices such as GIS or image retrieval systems require efficient processing of "k-nearest neighbor queries" for multidimensional spatial objects. Efficient optimization techniques have been developed for these queries. Among them, the Incremental Nearest Neighbor Algorithm proposed by Hjaltason and Samet works best in k-nearest query processing requiring "distance browsing" because it operates in an interactive fashion. have. What is written below shows an example of conventional k-nearest query processing.

SELECT *

FROM DISC

WHERE artist = `Beatles'

ORDER BY distance (color, `red ')

STOP AFTER k;

The query described above expresses Fagin's multimedia query, "artist =` Beatles '∧ color = `red'" as an extended SQL statement, which means "DISC of Beatles". ) To find the k closest to the red of the album. Here, distance browsing, which can retrieve spatial objects (attribute values of color) one by one, in order of distance from the query object red, until k query results satisfying the non-spatial search condition (artist = `Beatles`) are obtained. Function is required.

Hjaltason and Samet's incremental nearest-neighbor algorithm uses hierarchical indexes such as R-trees and priority queues to identify tuple identifiers containing the next nearest spatial object in the order of distance from a given query object. Pass TIDs one by one to the parent operator (for example, the select operator to handle artist = `Beatles'). The parent operator uses the TID to access the tuple and processes other non-spatial search conditions. This process is repeated until the k query results are retrieved. The main advantage of the above algorithm is that when the parent operator requires another Tuple Identifier (TID), it provides the TID of the tuple containing the next nearest spatial object in the previous working state without restarting the query from the beginning. It can be done.

However, the cumulative nearest algorithm has a problem in that a large number of unnecessary tuples are generated until k query results are obtained. That is, it is not efficient in terms of search speed because tuples that do not satisfy the non-spatial search condition are delivered to the upper level operator. This is because the response time of the user becomes longer when there are many unnecessary tuples before obtaining k query results. The reason why unnecessary tuples occur as described above is that the incremental nearest neighbor algorithm operates regardless of the non-spatial search condition used in the query.

We will examine the incremental nearest algorithm proposed by Hjaltason and Samet in more detail, and describe the problems that occur when processing k-nearest queries with non-spatial search conditions. Hjaltason and Samet have proposed an incremental nearest neighbor algorithm using R-tree, which is called RtreeINN algorithm.

The RtreeINN algorithm searches from the root node of the R-tree, while the next search node is taken from the foremost record of the queue, and after searching for that node, inserts the node's child or spatial object into the queue. In this case, the distance between the child node and the spatial object is inserted from the query object. The cues are always kept in distance order. If the data retrieved from the front of the queue is a spatial object, the tuple identifier (TID) containing it is returned to the query processing operator for processing the non-spatial search condition. Repeat this process until you have k query results or no records in the queue. As described above, the RtreeINN algorithm can pass the next TID to the higher-level operator without rerunning the query from the beginning when k '(> k) tuples are needed.

Berchtold et al. Defined the "optimality" of the k-nearest algorithm using hierarchical indexes such as R-trees, and proved that the RtreeINN algorithm ensures optimality. The definition of optimality is as follows.

Definition 1 k-Optimality

The k-nearest algorithm is optimal when the total number of pages accessed and the number of pages intersect with SP (Q, r) are the same when processing the nearest query. Where Q and r are the distances between the query object and the spatial object O ^k located at the k-th distance from Q (r = || Q-O ^k ||). In addition, SP (Q, r) represents a sphere having a center of Q and a radius of r.

By definition 1, the RtreeINN algorithm is optimal. Therefore, the cost of the RtreeINN algorithm until we get k query results is equal to the number of pages of the R-tree that overlap with SP (Q, r). The cost here means the cost of the k-nearest query without any non-spatial search conditions.

As described above, when processing such a query using the RtreeNN algorithm, the total cost C _all = C _rtree + C _tuple is equal. Where C _rtree is the R-tree cost and C _tuple is the tuple access cost to handle non-spatial search conditions. Other overall costs include rank queue operation costs, CPU costs, and the like, but are ignored in the present invention because they are small compared to other costs.

When the query object is Q, and the k-th spatial object that satisfies the non-spatial search condition is O ^{k '} (k' ≥ k), and the radius r = || Q-O ^{k '} ||, C _rtree is the RtreeNN algorithm. It is equal to the number of R-tree nodes that overlap SP (Q, r) depending on the optimality. Next, infer k 'to obtain a C _tuple . The size of the TID set passed to the upper level operator is equal to k '. When the number of query results k is given, k' can be inferred as follows. Assume that there is no correlation between the spatial attributes (color) and the nonspatial attributes (artist), and the selectivity of the attribute values (`Beatles') used in the query is S. Then, when the spatial object satisfying the i th query result is O ⁱ , to obtain the (i + 1) th query result, d _i ≤ || Q-O || We need to access (1 / s) spatial objects O that satisfy ≤ d _{i + 1} (d _i = || Q-O ⁱ ||). therefore, Becomes It can be seen that k 'increases linearly with respect to k. Using Yao's equation to find the average number of pages accessed, Same as Where N is the number of tuples, B is the page size, and T is the tuple size.

The problems of the RtreeINN algorithm used when processing k-nearest queries with non-spatial search conditions are as follows.

In order to check the approximate value of k ', the implementation of Pagan's RtreeINN algorithm was performed several times in the form of "artist =` Beatles' ∧ color = `red'" to obtain a result as shown in FIG. As shown in FIG. 1, the graph representing the prediction result increases linearly. However, it can be seen that the number of tuples (k ') to be approached is too large compared to the small number (k) of query results satisfying the non-spatial search condition. This indicates that the set of k 'candidate tuples contains too many unnecessary tuples. As a result, the larger k ', the higher the cost of C _tuple and the longer the user response time. In conclusion, the RtreeINN algorithm is suitable for processing k-nearest queries with non-spatial search conditions, but it is inefficient because many candidate tuples must be accessed. This is because the R-tree used by the RtreeINN algorithm does not have the ability to partially remove unnecessary tuples.

For example, as shown in Figure 2, each R-tree node from the query object Query Distance to Street order Assume that According to the RtreeINN algorithm, , to the next When processing Each child node of the node will be inserted into the queue with a precomputed distance. here, and Suppose no tuples satisfy the non-spatial search conditions in the subtree of. According to home and Although is a useless node, the RtreeINN algorithm enqueues the nodes without considering that they create many unnecessary tuples in the future. Therefore, there is a problem that unnecessary tuples increase.

The present invention has been made to solve the above problems, and an object of the present invention is to provide a new type of RS tree effective for the removal of tuples.

Another object of the present invention is to provide an indexing method using an incremental nearest neighbor algorithm based on an RS-tree rather than an R-tree.

Another object of the present invention is to provide an indexing method for a K-nearest query including a non-spatial search condition that can perform a search more efficiently by reducing the number of unnecessary tuples.

1 is a conventional RtreeINN Graph of execution result for query using algorithm,

2 is a conventional RtreeINN A graph representing the search space by the algorithm,

3 is a conceptual diagram illustrating generation and structure of an RS tree of the present invention;

4 is a conceptual diagram illustrating a signature split state according to the present invention;

5 to 6 are code examples showing an algorithm based on the RS tree of the present invention;

7 is a graph showing an experimental result according to the query result according to the present invention;

8 is a graph showing an experimental result in a state divided by the signature division function;

9 is a graph showing the results of the performance evaluation experiment according to the data size;

10 is a graph showing a performance evaluation test result according to the dimension (d) of spatial data;

11 is a graph showing experimental results in a real world dataset.

According to the present invention for achieving the above object, there is provided an RS tree structure, a removal effect of the S-tree, a signature division method for increasing it, and an incremental nearest neighbor algorithm using the RS-tree.

The RS tree of the present invention is a tree structure for a K-nearest query with non-spatial search conditions, wherein the tree structure is composed of a combination of an R tree and an S tree, and the R tree has a spatial attribute. It is used as an index for the S tree, and the S tree is used as an index for a non-spatial attribute. The tree is composed of a set of nodes of the same hierarchical structure as the R tree, and each node is composed of a plurality of entries. Each entry constituting the s corresponds to a node of the R tree and the entry one-to-one, and has only an index node level.

The S-tree according to the present invention has the following properties.

♥ As a "signature set", each signature is a set value representing a set of non-spatial attribute values.

♥ S-trees are based on hierarchical signature files, so they support the same hierarchical structure as R-trees.

♥ S-trees have data structures that are independent of R-trees, and have independent storage structures.

♥ S-trees also support hierarchical inclusion relationships as well as MBRs in R-trees.

♥ Small size signature saves S-tree storage.

The signature of the ♥ -S-tree is a bit stream of zeros or ones, so the operation cost such as AND or OR is low.

However, the R tree has essentially the same structure as that used conventionally.

Hereinafter, the present invention will be described in detail with reference to the accompanying drawings.

The RS-tree according to the present invention is composed of a combination of an R-tree and an S-tree having a hierarchical signature file structure. The R-tree is used as an index for spatial attributes such as color, and the S-tree is used as an index for non-spatial attributes such as artist. In general, one tuple can be composed of several non-spatial attributes, so the RS-tree can be extended with an index for one spatial attribute and m non-spatial attributes, that is, the RS ^m -tree. New index The following description will focus on the RS-tree.

Since the R-tree constituting the RS-tree is the same as the existing structure, the entire index will be described based on the S-tree. An S-tree consists of a set of hierarchical nodes like an R-tree, with each node filled with a number of entries. Each node of the S-tree and the entry constituting the node correspond one-to-one to the nodes and entries of the R-tree, respectively. However, unlike the R-tree, the S-tree has only the index node level. The reason is that since the R-tree has a higher ratio of storage space to the data nodes compared to the index nodes, the storage space overhead becomes too large when the data nodes of the S-tree correspond one-to-one with the R-tree data nodes. to be. Of course, putting data nodes in an S-tree can increase overall performance, but it is unrealistic because of the storage space overhead.

The j th entry of the S-tree node is a set value representing the set of all non-spatial attribute values (eg, artist's 'Beatles') contained in the subtree of the j th entry of the R-tree node. value). The reason why an entry of an S-tree node has a value of a set form is to easily remove the "R-tree node which does not satisfy the non-spatial search condition".

S-trees are assumed to be created at the same time that the R-trees are created in a bulk-loading manner. At this time, the signature generation of the entry of the S-tree node is largely the level of the S-tree. (At the bottom of the S-tree) Separated by. level The signature of an entry of an S-tree node in S1 is obtained by 1) obtaining a set of all non-spatial attribute values that a subtree of an entry of the R-tree node entry corresponding to the entry itself may have, and 2) each belonging to the set. It converts the non-spatial attribute value into a fixed-length bit stream, that is, a signature using a hash function, and 3) sums the bitwise OR of all elements of the generated signature set. At other levels, the sum of all the signatures of the child nodes indicated by the entry of the S-tree node is used as the signature of the entry.

In FIG. 3 (a), the table DISC has color as a spatial attribute and artist as a non-spatial attribute, and is used as a key of an R-tree and an S-tree, respectively. Figure 3 (b) shows a fixed-length signature table converted using a hash function for each artist attribute value of the DISC table. When the d-dimensional space for the color attribute is shown in Figure 3 (c), the corresponding R-tree is the tree in the left part of Figure 3 (d). One-to-one correspondence to each R-tree index node (for example, ↔ Is a S-tree. level in Node The process of generating a signature may include a corresponding R-tree node. Entry Looking up, The data node pointed to The attribute values {`Beatles ',` Sting'} of the artist are obtained from the table DISC through TID = 1, 2, and the signatures are converted into signatures {01101010, 00111001} using a hash function, and then the two signatures are combined. (01101010 ∧ 00111001 = 01111011). Signature Wow Degree Is made in the same way. level If, signature Has its own child node All signatures , , The sum of 01111011 ∧ 01111010 ∧ 00111011 = 01111011. In this way the signature of the top S-tree node is generated, and the entire S-tree is created.

The following describes how unnecessary R-tree nodes and objects (or TIDs) are removed by the S-tree in terms of the RtreeINN algorithm with the S-tree added.

Next target node in the front of the queue , The child of that node In this regard, the new algorithm according to the present invention Before calculating the distance from to the query object S-tree node corresponding to Signature Using First check whether the subtree of contains non-spatial query values (eg `Beatles'). That is, the signature of a non-spatial query value (for example, the signature 01101010 of `Beatles') is a query signature. Speaking of Check if it satisfies. Here, the operator 의미 means a bitwise multiplication (AND), and this check is called a signature check. Passing the signature check means that any data node that a child node of that R-tree can have, may have a tuple with non-spatial attribute values (eg `Beatles') used in the query, otherwise The case has the opposite meaning. Thus, nodes in the S-tree Which passes the signature among all signatures included in Insert a child node of the R-tree corresponding to the queue. Of course, S-tree node I / O occurs for signature checking, but it can be seen that the benefit of node removal of the S-tree is actually greater than this cost.

Referring again to Figure 3, the search node taken out of the current queue is RIN2, entry , , Each of these child nodes , , , The distance from the query object to each child node , , , Distance relationship Let's satisfy. And the signature of the query is the signature of the Beatles, Assume that = 01101010. For algorithms using S-trees, entry of RIN2 Child nodes pointed to The signature check using S-tree is performed before inserting into the queue. In signature check (= 01111010) is Does not satisfy Is not inserted into the queue. On the other hand, in the RtreeINN algorithm Because no consideration is given to whether a nonspatial attribute value equal to the nonspatial query value exists in the subtree of Will be inserted into the queue as is. after Nodes such as will generate many unnecessary tuples.

At higher levels, the signature of the S-tree may reach a "signature saturation" state where all bits are filled with `1 '. This is because, as described above, as the level increases in the generation of the S-tree, the number of child signatures that are combined to generate the signature increases. The problem with this is that a lot of "false drop" occurs. If a tuple is false drop, it means that even though it passes the signature check, it eventually does not satisfy the query condition. The problem of false drop is caused by the "phantom effect" that occurs when multiple signatures are combined. For example, in Figure 3 (d) When = 01101010 The tuple of TID = 3, 4 This signature check passes, but eventually drops because it does not satisfy artist = `Beatles'. Signature here silver This is what caused the phantom effect. This tuple will eventually turn out to be an unnecessary tuple. Later, the "signature splitting method" will be described to reduce the number of large false drops caused by signature saturation.

The signature "saturation saturation" can be confirmed. The probability that the i th bit value of each child and parent signature is '1' is respectively , , The number of child signatures belonging to the group when, Is given by Relatively small For Is small In spite of this, it can be estimated that it is almost '1'. It can be seen from this that the signature saturation is reached rapidly as the level of the S-tree increases. Because as the level of the S-tree increases, Because also increases. Thus, the phantom effect will cause more false drops. We are or By making the smaller, we can delay the signature saturation rate. small Selecting it will definitely slow down its speed, but small Despite the need for a very large signature, the effect is not so great. instead, We propose a method called "signature chopping," which can make.

The goal of the signature split is to split each signature of the S-tree node into a signature split function. (For example, By dividing into several signatures, Make it as small as possible, and furthermore, reduce the phantom effect. The signature of each S-tree node on level l about, Is Chopped-signatures, Divided by (if level l is high May occur because of this Becomes). At the time of creation of the S-tree, The C signatures of the child nodes of Buckets It is distributed by each. Then, by concatenating all the signatures contained in the j-th bucket Is generated. here, Is called the OR operator Satisfies Thus, the phantom effect is roughly comparable to before signature division. Decreases by a factor In Figure 4 ego Assume that Is doggy , , , Divided by In the case of Because of Divided into dogs). Before the signature split Has four child nodes , , , Generated by concatenating, while Is divided into four signatures, each of which is Only one of the child nodes of has the signature as the child signature.

In signature splitting, signature checking Is performed on each of the partition signatures. Remove the queue from the navigation node To Defined as the S-node, Is Suppose that is the j-th signature of. of For two split signatures, if no split signature passes the signature check, then the signature split is not applied. The child node of the j-th entry of (= ) Is removed. That is, it is not inserted into the queue. Otherwise, Is inserted into the queue with additional hints, for example, a bitmap. Here the hints are assigned to each split signature that does not pass the signature check. Node All subtrees of entries have to be removed because they no longer need to be accessed. here, Each split signature of Node Responsible for entries. In FIG. 4, the signature that passed the signature check is indicated by a dark area, and the S-tree node is shown. R-tree node corresponding to Let's say Split signature If none passes the signature check, then the R-tree node Is not inserted into the queue. On the other hand, Of the split signatures and Passes the signature check, so that R-tree node To the queue. At this time, Wow Did not pass the signature check, Inserts a bitmap into the queue indicating that there is no need to perform any operations (eg, calculate distance) on the second and third entries of the.

RS-tree based incremental nearest algorithm (hereinafter referred to as RStreeINN algorithm) that complements the RtreeINN algorithm is described as follows. Algorithms 1 and 2 shown in FIGS. 5 and 6 respectively represent an RStreeINN algorithm and a signature check routine. An additional part of the RStreeINN algorithm is taking the queue out and checking which of the child nodes the search node has removed (steps 9 and 21 of Algorithm 1), and performing signature checking before inserting them into the queue ( Step 10 of Algorithm 1). In Algorithm 2, AllocSize (l) refers to the number of entries of R-tree nodes on level l, allocated to each split signature. The RStreeINN algorithm is not suitable for queries containing non-spatial search conditions with comparison operators (> or <). However, this query can be processed by applying the RtreeINN algorithm using the R-tree of the RS-tree as it is. This is because the R-tree in the RS-tree has a storage structure independent of the S-tree. 5 and 6 show the source code of the detailed algorithm.

The results of the performance experiment applying the method of the present invention as described above are described below. A base table DISC was created for the experiment, and the schema is the same as DISC (artist, type, country, color). color is a spatial attribute, expressed as a d-dimensional point; otherwise, it is a non-spatial attribute with a 30-byte text value. The color attribute value was tested by dividing the artificial data and the real-world data along the uniform distribution. Attributes other than the color attribute have attribute values according to the Zipfian distribution, and each attribute has a discrete value corresponding to 0.5% of the total tuple number. The page size when storing the DISC table is 4K bytes.

R ^* -tree [2] is used as an index structure to store color attribute values, and the node size of R ^* -tree is 4K bytes. The S-tree for the experiment of the RStreeINN algorithm was created at the same time when the R ^* -tree was created in a batch-loading manner, and various signature splitting functions f (l) were applied (for example, ). If the number of signatures divided by f (l) is large or the dimension of the spatial object is low and the effective capacity C of the node becomes large, the remaining signatures are stored in the overflow page of the S-tree. The hash function for signature generation for non-spatial attribute values follows [8], and the signature size F = 64 bits (= 8 bytes) was used in each experiment. The rank queues used by both algorithms are implemented to run in main memory.

Experimental measurements are divided into query execution time, page accesses, and tuple accesses. In all experiments, experimental queries consist of (d-dimensional point, non-spatial property values), and each experimental result performs 50 experimental queries. The mean value of one result. The d-dimensional points were randomly selected and the top 50 attribute values with the highest selectivity according to the Zipfian distribution were selected. The reason for this is that a high selectivity increases the number of tuples having the same attribute value, and therefore, the possibility of using spatial indexes is higher than that of a sequential scan method, which has a high sort cost in query optimization. The query result k has a range of 1, ..., 35, and k is relatively small because sequential search is advantageous when k is relatively large and a practically small k is used [11]. The cache size of the R ^* -tree is one page, and the size of the cache used for table access is 1% of the size of the entire table. In order to minimize the impact of the system's OS cache on every query, file scans larger than the system's memory are performed first. To run the implementation of the two algorithms, we used a system and operating system PowerLinux 6.0 with a Pentium 133MHz processor, 128MB of memory and a 6GB disk drive.

The experiment used artificial data, and the experimental results indicate that the R * -tree is efficient This is done based on spatial data. Performance Evaluation According to Query Result k: Dimension of Color Attribute Value of Table DISC , the Zipfian variable z = 0.5 for the attribute value of the artist, the total number of tuples , Signature split function When the number of bits of the signature F = 64, the query execution time, the number of page accesses, and the number of tuple accesses are shown in FIGS. 7A, 7B, and 7C, respectively.

In FIG. 7A, the tuple access number is equal to the total number of candidate tuples until k query results are obtained. Both algorithms linearly increase the number of tuples that need to be approached as k increases, but differ greatly in the slope of the straight line. This is because the RStreeINN algorithm has the above-described elimination effect of the S-tree. In FIG. 7B, the number of page accesses of the two algorithms is slightly larger than the number of tuple accesses in FIG. 7A. This is because the two algorithms additionally access pages of the R-tree or S-tree. Both algorithms increase linearly as the number of access pages increases, k, and remains almost similar to the graph of FIG. 7A. The reason is that the number of pages accessed is more affected by the tuple access cost than the spatial index when the experimental data is relatively small. The difference in the number of page accesses of FIG. 7B is reflected in the query execution time of FIG. 7C. However, it can be seen from FIG. 7C that the width of the performance difference of the two algorithms that can be expected from the difference in the number of page accesses of FIG. 7B is reduced. The reason is that the RStreeINN algorithm requires the R-tree and the S-tree to be accessed alternately, resulting in additional cost due to random disk I / O.

Signature split function The performance evaluation according to the following description is as follows.

In the RStreeINN algorithm, the overall performance may vary depending on the number of signatures that each entry of an S-tree node can have. It can be expected that the overall performance is proportional to the number of signatures. The experiment was performed according to the signature division function f (l) within the range of no overflow page, and the result is shown in FIG. 8.

In FIG. 8A, it can be seen that the number of page accesses decreases significantly as the number of signature divisions increases, and the difference is large compared to the RtreeINN technique. This difference is reflected in the query execution time of FIG. 8B. But, RStreeINN algorithm performs worse than RtreeINN algorithm. The reason is that the RStreeINN algorithm suffers more damage from random disk I / O due to S-tree access than the benefit from S-tree. Figure 8c shows the queue size according to f (l) when k = 10. NoSign corresponds to the RtreeINN algorithm, and base> 2 corresponds to the RStreeINN algorithm. The numbers in the bottom and top boxes in the figure represent the number of R-tree nodes inserted into the queue and the total queue size, respectively, and the difference between the two values represents the number of objects (or TIDs) inserted in the queue. In FIG. 8C, as the number of signature partitions increases, the number of R-tree nodes and objects inserted into a queue decreases, indicating that signature saturation and phantom effects in the S-tree are alleviated by signature partitioning. In addition, it can be seen that the difference in queue size is represented by a difference in performance. This is shown in Figures 8A-8B.

Performance evaluation results according to the data size are as follows.

In the above experiment, the experimental variable value is Bit was used. Referring to FIG. 9, as the data size increases, the RStreeINN algorithm performs better than the RtreeINN algorithm. In the RtreeINN algorithm, as the data size increases, the query execution time also increases with a relatively large slope, whereas in the RStreeINN algorithm, the slope of the graph is gentle. This fact shows that the RStreeINN algorithm guarantees its performance regardless of the data size.

In the performance evaluation experiment according to the dimension (d) of the spatial data, Bit is used, and when d = 2, one overflow page is generated for each node in the S-tree. 10, it can be seen that RStreeINN is superior to RtreeINN for each dimension. However, as the dimension increases, the difference in performance decreases. The reason for this is that in high-dimensional R-trees, unlike low-level data nodes, the capacity of data nodes is small, so that the non-spatial attribute values of a query are evenly distributed across all data nodes, which increases the probability of passing the "signature check". This is because the number of tree nodes increases

The experimental results in the real world dataset are as follows.

In this experiment, the spatial data uses 16-dimensional, high-dimensional Fourier points used in the CAD model as real-world data, and the non-spatial data follows a distribution having a Zipfian variable z = 0.5 as artificial data. Other experimental variable values Like a bit. The performance of the R ^* -tree is not efficient when the dimension d = 16, but there is no problem in comparing the performance of the two algorithms. In the higher dimension, since the capacity of the R-tree node is smaller, the two algorithms do not show the same performance as the lower and lower dimensions, but RStreeINN is superior to RtreeINN. This is shown in FIG.

As described above, according to the present invention, it is used in a query in a conventional database, and by significantly reducing the number of unnecessary tuple occurrences, which is a problem of the incremental nearest method based on the R tree proposed by Hjaltason and Samet. Effective querying for multidimensional spatial object sets required by multimedia databases or geographic information systems is possible.

Claims (7)

In the tree structure for K-nearest query of a database with non-spatial search conditions, A tree structure in which the tree structure is composed of a combination of an R tree and an S tree, The R tree is used as an index for the space attribute, The S tree is used as an index for a non-spatial attribute, and is composed of a node set having the same hierarchical structure as the R tree, each node is composed of a plurality of entries, and each node of the S tree and an entry constituting the node. RS tree structure for a K-nearest query of a database including a non-spatial search condition, wherein each corresponds to a node and an entry of the R tree one-to-one, and has only an index node level. The method of claim 1, At the same time as generating the R tree, an S tree is generated. The S tree is based on a hierarchical signature file, and the non-spatial search condition is included in that the generation of the signature of the entry of the S tree node is divided into levels (l = 1) and l> 1. RS-tree structure for K-nearest query. The method of claim 2, The signature, at level l = 1) obtains the set of all non-spatial attribute values that the subtree of the entry of the R-tree node corresponding to the entry itself can have, and 2) each non-spatial attribute belonging to the set. The value is converted into a signature that is a fixed-length bit stream using a hash function, and 3) it is generated by bitwise ORing all elements of the generated signature set, and at the remaining levels ℓ> 1 RS tree structure for K-nearest query with non-spatial search conditions, which is generated by combining all signatures of child nodes indicated by entries of tree nodes. The method according to claim 1, wherein For each of the signature S _i (1≤i≤C) any S- tree nodes existing in the level ℓ has the S _i is, S _i, f satisfying _j (1≤j≤C) RS tree structure for K-nearest query with non-spatial search conditions characterized by being divided into (ℓ) signatures. The method of claim 4, wherein The next navigation node at the forefront of the queue , The child of that node La, each Before calculating the distance from to the query object S-tree node corresponding to Signature Wow, The subtree of is a query signature for nonspatial query values. When I say RS tree structure for k-nearest query with non-spatial search conditions characterized by checking whether In an incremental nearest method based on an R tree that indexes according to a query to search a database, This method, Checking which of the child nodes the search node has had been removed from the queue; And incrementally performing a signature check before inserting a child node into the queue. The method of claim 6, The signature check checks the next search node at the forefront of the queue. , The child of that node La, each Before calculating the distance from to the query object S-tree node corresponding to Signature Wow, The subtree of is a query signature for nonspatial query values. When I say Incremental closest method, characterized in that the test to satisfy.