# Skyline-Like Query in Three-Dimensional Obstacle Space

Authors: Yongshan Liu; Tianbao Hao; Xiang Gong; Dehan Kong; Jianjun Wang
Journal: Scientific Programming
 (2022)

---

## Abstract

Skyline query, as a query method to solve typical multiobjective optimization problems, has a wide range of applications in market analysis and data mining. Many scholars’ attention has been attracted since it was proposed. However, the correct result set cannot be obtained easily by traditional skyline query when nonspatial and spatial attributes of the data set need to be considered at the same time, and there are differences in the importance of each attribute. To solve this problem, a skyline-like query was proposed in three-dimensional obstacle space based on the traditional skyline query. In the skyline-like query algorithm, nonspatial skyline-like points were obtained according to the traditional algorithm. The spatial attribute dominated region of the obtained points was used to filter the data set, and then the shielding of obstacles was considered in the three-dimensional obstacle space. By constructing a three-dimensional visible graph, the Dijkstra algorithm was used to obtain the skyline-like points of spatial attribute. After sorting, the skyline-like point set was obtained based on the value of user’s preference. Compared with B2S2 algorithm, the experimental results show that the skyline-like algorithm had a better performance. Then, the comparative experiments within three-dimensional obstacle skyline query were carried out by setting different sizes of data sets and different numbers of obstacles. According to the results, it is shown that the algorithm had a great performance.


---

## Body

## 1. Introduction

With the improvement of people’s requirements for location-based services, there is continuous development as well as innovation in information technology. There are more and more types of spatial database queries, such ask-nearest neighbor query, anti-k-nearest neighbor query, visual range query, and skyline query. These queries are developed in response to the different needs of users. The k-nearest neighbor query is proposed to search several data objects which are close to a certain query location, such as the problem of finding the nearest gas station. The anti-k-nearest neighbor query is proposed to find all the objects in which k-nearest neighbors contain the query object. For example, we choose a location to build a supermarket that is relatively close to the surrounding communities. When the visibility of a certain location is important for users, such as the billboard placement problem, the visual range query is proposed. The skyline query is more favorable to the users who are more concerned about the attributes of the data point and want to select the most advantageous data point in the entire data set. In order to meet the higher query requirements of users, more and more methods are proposed to solve practical problems. Various query methods provide support for spatial knowledge extraction and spatial data analysis, making spatial database technology play an increasingly important role in life. However, with the rapid development of computer technology in recent years, the research on spatial databases has gradually transformed from low-dimensional to three-dimensional or even high-dimensional. As an objective response of the real world, three-dimensional space has more practical significance to study, but the increase in dimensionality inevitably leads to an increase in the amount of data, and the issues that need to be considered would be more complex, so mining useful information among the many kinds of data points in the data set has become a difficult problem for many queries in spatial databases.Among those queries, skyline query, as an optimized technology to solve typical multiobjective problems, has a wide range of applications in knowledge mining, market analysis, and decision-making. Consider the following scenario: the user needs to pay attention to the nonspatial attributes of the data set first, such as price and score; then he pays attention to the location of each query point in the query set, and finally the data that meet the user’s needs best are returned first. In the scenario of the above requirements, the traditional skyline query cannot meet the needs of users, as the distance of space objects requires a lot of calculations to be obtained, and the calculation is very complicated and time-consuming. Researchers need to improve the skyline query algorithm. The three-dimensional obstacle space is a reflection of the real world. Applying the improved skyline query to this space makes the result set more accurate and practical. In response to the above-mentioned problems, this paper improves the traditional skyline query and applies the improved query algorithm to the three-dimensional obstacle space.


## 2. Related Works

The traditional skyline query was first proposed by Kung et al. [1]. The main solution was to find the largest element in each dimension in an n-dimensional vector. The concept of “dominance” that was proposed was standardized on this basis. Later, Bentley [2] studied further; he proposed a linear query algorithm to solve the optimal solution problem in the vector under the independent data distribution in each dimension. However, the previous research works were all aimed at the small amount of data, and the algorithms proposed were all running in the memory. The situation where skyline queried a large amount of data and the data could not be stored in memory began to be considered by scholars. In response to this problem, Borzsonyi et al. proposed BNL algorithm and D&C algorithm [3], SFS algorithm [4], Bitmap algorithm [5], and LESS algorithm [6]. The problem had been solved further by the above algorithm, but there were further requirements for the query running time in the later period. Therefore, the index began to be introduced into skyline queries. Scholars had studied the skyline algorithm with index to solve the query problems, including index algorithm based on B+ tree index [5, 7] and NN algorithm based on R tree and BBS algorithm [8]. In the above algorithms, after the data set was stored by adding an index, the data set was pruned with the unique attributes of the index during the query process, which reduced the comparison process and improved the query efficiency. Zhang et al. [9] studied an algorithm that used the minimum bounding rectangle of the R tree to perform an MBR skyline query. By judging the dominance of MBR, the minimum bounding rectangle that was not dominated by other MBRs is returned, which reduced the search space for judgment and improved the efficiency of skyline query’s process. However, the algorithms proposed in the above papers were all aimed at the situation where the user cared about the same metrics for all attributes. Therefore, when there was a difference in the priority relationship between users and attributes, the above algorithm could not solve this problem. For this reason, Shao Luyi et al. proposed a preference skyline query [10], and Stefanidis and Koutrik used soft standards to study the proposed preference and conducted research on this [11]. However, it was still an arduous task to design a preference model and an extended processing method suitable for the mentioned queries above.As users cared more and more about the attributes of objects, skyline queries were applied to high-dimensional spaces. However, the size of the query result set was too large to find useful information in the high-dimensional space of skyline query application, which would lose the meaning of query for users. To solve those problems, top-k skyline query, k-dominant skyline query, and redefining new metrics to sort the result set were proposed. Research on top-k skyline query included the work of D. Papadias et al. [12] who proposed top-k RSP query, which returned the smallest value of the top k functions by specifying parameter k and the monotonic preference function f on each attribute skyline point set. Liang Wei et al. proposed a top-k skyline query DFTS algorithm [13] to find the best top k points in a large data set. Research on k-dominant skyline query was also processed. “k-dominant” referred to the attribute space that dominated k dimensions. It was proposed first by Chan et al. [14]. At the same time, an effective algorithm was proposed to retrieve the data set to satisfy the skyline point of k-dominant. Later, Anuradha Awasthi et al. proposed a KSJQ algorithm [15], which extended the k-dominant skyline query to enable it to handle connection relationships and so on. There were also many research works on redefining new metrics to sort the result set. Chee-Yong Chan et al. [16] proposed a new metric “skyline frequency,” which referred to the subordinates that each skyline data point dominated. At the same time, an algorithm was proposed to return the first k skyline points based on the skyline frequency index value. Mohamed et al. [17] proposed the concept of “satisfaction rate.” When the result set was too large, the first k skyline objects with high satisfaction rate were returned, where k was defined by the user.In the process of studying the traditional skyline query, many common problems were solved, but the geometric problems in the spatial region were ignored. Later, the spatial skyline query was proposed. It was first proposed by Sharifzadeh and Shahabi [18], and they gave the B2S2 algorithm based on R tree and the VS2 algorithm based on Voronoi diagram to solve this problem. Geng et al. [19] proposed a combination of Voronoi diagram and R tree to obtain skyline points from query points based on multiple locations. In order to solve the spatial skyline query problems in high-dimensional space, a new index structure Hilbert R tree [20] was proposed, which combined R tree and Hilbert curve. Li Song et al. made full use of the advantages of both and proposed a spatial skyline query algorithm based on single query point and multiple query points. At the single query point, the pruning strategy and filtering process were proposed to obtain the skyline result set, and, at multiple query points, the topological relationship between the data points and the dominant decision circle were used to obtain the skyline result set, but the applicable scenario was static surroundings. In recent years, various forms of space skyline queries had appeared. For example, Das et al. [21] used the convex distance function to weight the Voronoi diagram to solve the spatial skyline query further. Fort et al. [22] considered Euclidean distance weighting to determine the closest and the furthest skyline query and established a distance limit relative to the set of data and returned the skyline points within the range.Although there had been many research works on skyline query and spatial skyline query, it had not been proposed clearly that a query algorithm would fully consider the nonspatial attributes and the spatial attributes of the query set. In the spatial skyline query, only the Euclidean distance between the query point and the data point was considered in the query process. Later, Song et al. [23] proposed the SOS algorithm to solve the skyline query in the two-dimensional obstacle space using the rapid positioning feature of the R+ tree to prune out a large number of dominated data points effectively, narrow the query range, and improve the efficiency of the algorithm. Then, based on the obstacle distance and the topological relationship between the data point and the query point, the data points were screened twice in the candidate set, and the skyline set was obtained finally. However, only two-dimensional space is considered, and it is not extended to three-dimensional space. The application of the query results to real life had certain inaccuracies.In the study of this paper, the skyline query was applied to the three-dimensional obstacle space, and the distance in the space was the three-dimensional obstacle distance. In terms of obstacle distance, the Euclidean distance was first used as the distance in the spatial database, followed by the road network distance and then the obstacle distance. For obstacle distance, it had been studied widely in computational geometry, but, in the field of spatial database, it started recently. Lozano-Pérez and Wesley [24] first proposed their calculation method. In the calculation process, it is necessary to construct a graph, whose distance was the set of the smallest edges in the graph. Kung et al. [25] continued their study and proposed an algorithm for calculating the shortest path in the visible graph. After that, researchers applied obstacle distance to various queries in spatial database, including obstacle range query and obstacle nearest neighbor query [26], the reverse k nearest neighbor query of obstacle distance [27], and group obstacle nearest neighbor query based on obstacle distance neighbor query [28]. However, there were few studies on the obstacle distance in the three-dimensional obstacle space. For the three-dimensional obstacle space, Liu and Kong [29] conducted research on the visual query of the object. A three-dimensional object visibility test method based on horizontal angle (HA) and vertical projection angle (VPA) was proposed, and a continuous visibility range query processing based on the visibility test method was proposed. Regarding the calculation of the three-dimensional obstacle distance in the spatial database, few relevant papers had been found, and the spatial skyline has not been applied to the three-dimensional obstacle space.It could be seen from the above description of the related work that the inquiry of skyline had been studied for a long time. However, the skyline query still had the problems of low query efficiency and multifactor interaction (including nonspatial and spatial attributes) in the three-dimensional obstacle space. This paper conducted in-depth research and the algorithm was found to solve these problems.


## 3. Definitions and Theorems

Suppose that a certain class of graduates intend to hold a class reunion. When choosing a meeting place, the distance of the participants should be considered as much as possible, and, in the selection of the place, attention should be paid to two dimensions, price and rating. Among the three requirements for the meeting place, perhaps the most important thing is distance, followed by price and rating in no particular order. In this scenario, the data setP is various meeting places for selection, and the query set Q is the location of the party members. Based on this situation, a skyline-like query is proposed. The results of the query are the meeting places that meet the requirements above, and the result set is sorted based on the degree of attribute importance for users to choose.Figure1 is the scenario of choosing a meeting place. In the figure, the data set Pra,rb,…rn is the meeting places (indicated by black dots), each of which has spatial and nonspatial attributes, query set Qs1,s2,s3 is the location information of the party members (represented by a black star), and each of si only has spatial attributes. Not only can the result set S {ri} returned by the skyline-like query guarantee the advantage in nonspatial attribute set but also the distance from S {ri} to s1,s2,s3 is close relatively in the three-dimensional obstacle space.Figure 1
Scenario of choosing a meeting place.


### 3.1. Definitions

#### 3.1.1. Definitions of Skyline-Like Queries

Definition 1.
Data object: All data objects have information of spatial location attribute and information of nonspatial attributes. Each data object is represented byp (A, B, C). Among them, A in object p represents the position information (x, y, z) of point p in three-dimensional space, and B represents the values of nonspatial attribute of object p. For example, in the above scene, B = {C, D}, where C represents the price of the meeting place and D represents the rating of the meeting place. C represents the attribute preference value of object p; its default value is 0. The definition of the attribute preference value is Definition 3.
The query object in the query is a data point with spatial location information only; each query object is represented byq (x, y, z). (x, y, z) means the information of position in the three-dimensional space.Definition 2.
Attribute preference: Attribute preference is an additional attribute of a data object, which needs to be calculated later. It is an estimate of the user’s preference based on the data object. The weightwi is used for quantification of the preference, which represents the value of weight of the i-th attribute. The smaller the value, the higher the user’s preference for the attribute. For all the attribute sets D = {d1, d2, …, dd}, the corresponding attribute preference weight W = {w1, w2, …, wd}, with ∑i=1dwi.Definition 3.
Attribute preference value is the corresponding value after quantifying the degree of preference of each data object. It is calculated according to the attribute preference weight. Assuming that the attribute preference weight set isW = {w1, w2, …, wd} and the value of each attribute of a certain object pi is pi = {pi1, pi2, …, pid}, the attribute preference value of object p can be expressed as follows:(1)APValue=pi⊗w.
The operator⊗ means that the corresponding items are multiplied and then added; that is, the APValue = ∑i=1dAPValuei the object pi, where APValuei =  pij × wi. We initialize it to 1/d; when the object is selected as a skyline-like point, the attribute preference value of the point is reassigned.Definition 4.
Dominance: Given a set of data objectsP in a d-dimensional space and a set of query points Q, data object p∈P. For any p’ ∈P, if p’ is dominated by p, one of the following conditions needs to be met:(a)
pi≤pi′1≤i≤d,∃pi<pi′1≤j≤d(b)
∀qi∈Q,Distp,qi≤Distp′,qi∃Distp,qi<Distp′,qi
If the query point is a single point, one of the following conditions needs to be met when judging whetherp’ is dominated by p:(a)
pi≤pi′1≤i≤d,∃pi<pi′1≤j≤d(b)
Distp,q≤Distp′,q,∃Distp,q<Distp′,q
Among them, Dist (p, q) is the function to obtain the distance between the two points p and q.Definition 5.
Skyline-like point (SP): The point is selected from the object setP in the given d-dimensional space. If the point is not dominated by any other point in P, then the point is a skyline-like point.
The skyline-like point set returns a collection of data objects that are not dominated by any other data object inP. The set contains the skyline-like point set with dominant nonspatial attributes and spatial attributes.Definition 6.
Dominated region: The region is constructed on the basis of the skyline-like point setS1. It is the smallest outer box of S (p, Q), which represents the region that is dominated by the skyline-like points. Among them, S (p, Q) represents a sphere with the center qi of the sphere in the query set Q and the distance from qi to a skyline-like point p as the radius. When the query set Q contains multiple query points, S (p, Q) is a set of balls. As shown in Figure 2, the query set Q = {q1, q2, q3} is given; it shows that p2 is a skyline-like point in the data set P; the dominated region B can be obtained by it. The points outside the dominated region B are definitely not skyline-like points.Figure 2
The dominated region.


#### 3.1.2. Definitions in the Three-Dimensional Obstacle Space

It is assumed that the data set in this paper is the point set with spatial attributes and nonspatial attributes, the query set is the point set with spatial attributes, and the obstacles are all irregular three-dimensional objects.Definition 7.
Obstacle: Obstacles in the three-dimensional space are all cuboids perpendicular to the ground, with default random rotation angles. Each cuboid is represented byO (C,R,θ); C and R are three-dimensional coordinate points, where C = (XC,YC,ZC). Among them, C represents the center point of the cuboid, R is the distance between the center point and each coordinate plane of the cuboid, and θ is the rotation angle of the space object on the horizontal plane. The projection of the cuboid on the XOY plane is a random rectangle, and the rotation angle is the angle between the projected rectangle axis and the x-axis, as is shown in Figure 3.
In the three-dimensional obstacle space, the distance between two points is no longer Euclidean distance, and its calculation method needs to be redefined.Figure 3
The representation of obstacle in 3D space.Definition 8.
Three-dimensional obstacles visibility graph: The graph is similar to the graph in two-dimensional space; both of them include the vertex setV and the edge set E. In the visual graph based on point p and q, set V has the vertices in the intersection obstacle set of the line segment pq. Set E refers to the distance between the vertices in Set V. Assuming that set V contains n vertices, the size of set E is a square matrix of n × n, and the matrix is symmetric. If there is connectivity between the two points, the distance between the two points is recorded; otherwise, N is recorded, indicating that there is no connectivity between the two points. It is stipulated that the elements on the diagonal are all N in the graph; that is, each point has no connectivity to itself. The biggest difference between this graph and the two-dimensional graph is that the obstacles in this graph are all represented by a three-dimensional volume.Definition 9.
Obstacle distance in three-dimensional space: Obstacle distance in three-dimensional space refers to the shortest distance between any two pointsp and q calculated in the three-dimensional obstacle space. When there is no obstacle between p and q, the obstacle distance is equal to the Euclidean distance.Definition 10.
Obstacle skyline-like query: A set of objects in ad-dimensional space P = {p1,…,pn} and a query point q or a set of query points Q = {q1,…,qm} and the preference weight of each attribute W = {w1,…,wd} are given; the attribute preference value APValue of each skyline-like point is obtained by algorithm calculation. The 3D obstacle skyline query returns the skyline-like points sorted based on the attribute preference value in the 3D obstacle space set, which is called obstacle skyline-like query for short.


### 3.2. Theorems

Theorem 1.
If the data point setS1 is not dominated by nonspatial attributes, when judging whether the data point set S2 is dominated by spatial attributes, there is no need to consider the data point set S1.
Proof: The data point setS1 has been determined to be skyline-like points by Definition 4, and there is no need to repeat the comparison.Theorem 2.
All data points located outside the dominated region are dominated by the skyline-like points inside.Proof: The dominated region is constructed on the basis of the skyline-like point setS1. There must be a point p∈ S1; point p’ outside the dominated region is dominated by p through Definition 6.Theorem 3.
Suppose that there is a pointo on a line segment L, the direction vector of the line segment is d⟶, o and d⟶ are both known quantities, and any point p∈ L is taken; then the equation of the line segment L is defined as(2)p=o+td⟶,t∈tA,tB.Theorem 4.
If line segmentL intersects plane P, t=p0−o⋅n⟶/d⟶⋅n⟶ is satisfied.Proof.
The point method equationp−p0⋅n⟶=0 is used to define a certain plane P, and equation (2) is used to define the equations of the line segment of p and q. When the line segment intersects plane P, it must intersect at a certain point; that is, o+td⟶−p0⋅n⟶=0. Simplification leads to Theorem 4.Theorem 5.
Suppose that the intermediate node of the R tree is entry, the skyline-like result set is SP, and the Euclidean distance from the entry to the query pointq is EurDis. All the data points under the intermediate node entry could be filtered out directly, where ObsDis is the obstacle distance between the query point q and the node entry. The calculation process is shown in the next section.Proof.
If the Euclidean distance from the middle node entry of the R tree to the query pointq is EurDis, the distance must be less than or equal to the obstacle distance from all data points in the entry to q. If EurDis is greater than the obstacle distance ObsDis from all skyline-like points to q in the skyline-like result set, it means that the obstacle distance of all data points in this node is always greater than ObsDis; that is, there is no possibility of generating skyline-like points in this node; the theorem is proved.


## 3.1. Definitions

### 3.1.1. Definitions of Skyline-Like Queries

Definition 1.
Data object: All data objects have information of spatial location attribute and information of nonspatial attributes. Each data object is represented byp (A, B, C). Among them, A in object p represents the position information (x, y, z) of point p in three-dimensional space, and B represents the values of nonspatial attribute of object p. For example, in the above scene, B = {C, D}, where C represents the price of the meeting place and D represents the rating of the meeting place. C represents the attribute preference value of object p; its default value is 0. The definition of the attribute preference value is Definition 3.
The query object in the query is a data point with spatial location information only; each query object is represented byq (x, y, z). (x, y, z) means the information of position in the three-dimensional space.Definition 2.
Attribute preference: Attribute preference is an additional attribute of a data object, which needs to be calculated later. It is an estimate of the user’s preference based on the data object. The weightwi is used for quantification of the preference, which represents the value of weight of the i-th attribute. The smaller the value, the higher the user’s preference for the attribute. For all the attribute sets D = {d1, d2, …, dd}, the corresponding attribute preference weight W = {w1, w2, …, wd}, with ∑i=1dwi.Definition 3.
Attribute preference value is the corresponding value after quantifying the degree of preference of each data object. It is calculated according to the attribute preference weight. Assuming that the attribute preference weight set isW = {w1, w2, …, wd} and the value of each attribute of a certain object pi is pi = {pi1, pi2, …, pid}, the attribute preference value of object p can be expressed as follows:(1)APValue=pi⊗w.
The operator⊗ means that the corresponding items are multiplied and then added; that is, the APValue = ∑i=1dAPValuei the object pi, where APValuei =  pij × wi. We initialize it to 1/d; when the object is selected as a skyline-like point, the attribute preference value of the point is reassigned.Definition 4.
Dominance: Given a set of data objectsP in a d-dimensional space and a set of query points Q, data object p∈P. For any p’ ∈P, if p’ is dominated by p, one of the following conditions needs to be met:(a)
pi≤pi′1≤i≤d,∃pi<pi′1≤j≤d(b)
∀qi∈Q,Distp,qi≤Distp′,qi∃Distp,qi<Distp′,qi
If the query point is a single point, one of the following conditions needs to be met when judging whetherp’ is dominated by p:(a)
pi≤pi′1≤i≤d,∃pi<pi′1≤j≤d(b)
Distp,q≤Distp′,q,∃Distp,q<Distp′,q
Among them, Dist (p, q) is the function to obtain the distance between the two points p and q.Definition 5.
Skyline-like point (SP): The point is selected from the object setP in the given d-dimensional space. If the point is not dominated by any other point in P, then the point is a skyline-like point.
The skyline-like point set returns a collection of data objects that are not dominated by any other data object inP. The set contains the skyline-like point set with dominant nonspatial attributes and spatial attributes.Definition 6.
Dominated region: The region is constructed on the basis of the skyline-like point setS1. It is the smallest outer box of S (p, Q), which represents the region that is dominated by the skyline-like points. Among them, S (p, Q) represents a sphere with the center qi of the sphere in the query set Q and the distance from qi to a skyline-like point p as the radius. When the query set Q contains multiple query points, S (p, Q) is a set of balls. As shown in Figure 2, the query set Q = {q1, q2, q3} is given; it shows that p2 is a skyline-like point in the data set P; the dominated region B can be obtained by it. The points outside the dominated region B are definitely not skyline-like points.Figure 2
The dominated region.


### 3.1.2. Definitions in the Three-Dimensional Obstacle Space

It is assumed that the data set in this paper is the point set with spatial attributes and nonspatial attributes, the query set is the point set with spatial attributes, and the obstacles are all irregular three-dimensional objects.Definition 7.
Obstacle: Obstacles in the three-dimensional space are all cuboids perpendicular to the ground, with default random rotation angles. Each cuboid is represented byO (C,R,θ); C and R are three-dimensional coordinate points, where C = (XC,YC,ZC). Among them, C represents the center point of the cuboid, R is the distance between the center point and each coordinate plane of the cuboid, and θ is the rotation angle of the space object on the horizontal plane. The projection of the cuboid on the XOY plane is a random rectangle, and the rotation angle is the angle between the projected rectangle axis and the x-axis, as is shown in Figure 3.
In the three-dimensional obstacle space, the distance between two points is no longer Euclidean distance, and its calculation method needs to be redefined.Figure 3
The representation of obstacle in 3D space.Definition 8.
Three-dimensional obstacles visibility graph: The graph is similar to the graph in two-dimensional space; both of them include the vertex setV and the edge set E. In the visual graph based on point p and q, set V has the vertices in the intersection obstacle set of the line segment pq. Set E refers to the distance between the vertices in Set V. Assuming that set V contains n vertices, the size of set E is a square matrix of n × n, and the matrix is symmetric. If there is connectivity between the two points, the distance between the two points is recorded; otherwise, N is recorded, indicating that there is no connectivity between the two points. It is stipulated that the elements on the diagonal are all N in the graph; that is, each point has no connectivity to itself. The biggest difference between this graph and the two-dimensional graph is that the obstacles in this graph are all represented by a three-dimensional volume.Definition 9.
Obstacle distance in three-dimensional space: Obstacle distance in three-dimensional space refers to the shortest distance between any two pointsp and q calculated in the three-dimensional obstacle space. When there is no obstacle between p and q, the obstacle distance is equal to the Euclidean distance.Definition 10.
Obstacle skyline-like query: A set of objects in ad-dimensional space P = {p1,…,pn} and a query point q or a set of query points Q = {q1,…,qm} and the preference weight of each attribute W = {w1,…,wd} are given; the attribute preference value APValue of each skyline-like point is obtained by algorithm calculation. The 3D obstacle skyline query returns the skyline-like points sorted based on the attribute preference value in the 3D obstacle space set, which is called obstacle skyline-like query for short.


## 3.1.1. Definitions of Skyline-Like Queries

Definition 1.
Data object: All data objects have information of spatial location attribute and information of nonspatial attributes. Each data object is represented byp (A, B, C). Among them, A in object p represents the position information (x, y, z) of point p in three-dimensional space, and B represents the values of nonspatial attribute of object p. For example, in the above scene, B = {C, D}, where C represents the price of the meeting place and D represents the rating of the meeting place. C represents the attribute preference value of object p; its default value is 0. The definition of the attribute preference value is Definition 3.
The query object in the query is a data point with spatial location information only; each query object is represented byq (x, y, z). (x, y, z) means the information of position in the three-dimensional space.Definition 2.
Attribute preference: Attribute preference is an additional attribute of a data object, which needs to be calculated later. It is an estimate of the user’s preference based on the data object. The weightwi is used for quantification of the preference, which represents the value of weight of the i-th attribute. The smaller the value, the higher the user’s preference for the attribute. For all the attribute sets D = {d1, d2, …, dd}, the corresponding attribute preference weight W = {w1, w2, …, wd}, with ∑i=1dwi.Definition 3.
Attribute preference value is the corresponding value after quantifying the degree of preference of each data object. It is calculated according to the attribute preference weight. Assuming that the attribute preference weight set isW = {w1, w2, …, wd} and the value of each attribute of a certain object pi is pi = {pi1, pi2, …, pid}, the attribute preference value of object p can be expressed as follows:(1)APValue=pi⊗w.
The operator⊗ means that the corresponding items are multiplied and then added; that is, the APValue = ∑i=1dAPValuei the object pi, where APValuei =  pij × wi. We initialize it to 1/d; when the object is selected as a skyline-like point, the attribute preference value of the point is reassigned.Definition 4.
Dominance: Given a set of data objectsP in a d-dimensional space and a set of query points Q, data object p∈P. For any p’ ∈P, if p’ is dominated by p, one of the following conditions needs to be met:(a)
pi≤pi′1≤i≤d,∃pi<pi′1≤j≤d(b)
∀qi∈Q,Distp,qi≤Distp′,qi∃Distp,qi<Distp′,qi
If the query point is a single point, one of the following conditions needs to be met when judging whetherp’ is dominated by p:(a)
pi≤pi′1≤i≤d,∃pi<pi′1≤j≤d(b)
Distp,q≤Distp′,q,∃Distp,q<Distp′,q
Among them, Dist (p, q) is the function to obtain the distance between the two points p and q.Definition 5.
Skyline-like point (SP): The point is selected from the object setP in the given d-dimensional space. If the point is not dominated by any other point in P, then the point is a skyline-like point.
The skyline-like point set returns a collection of data objects that are not dominated by any other data object inP. The set contains the skyline-like point set with dominant nonspatial attributes and spatial attributes.Definition 6.
Dominated region: The region is constructed on the basis of the skyline-like point setS1. It is the smallest outer box of S (p, Q), which represents the region that is dominated by the skyline-like points. Among them, S (p, Q) represents a sphere with the center qi of the sphere in the query set Q and the distance from qi to a skyline-like point p as the radius. When the query set Q contains multiple query points, S (p, Q) is a set of balls. As shown in Figure 2, the query set Q = {q1, q2, q3} is given; it shows that p2 is a skyline-like point in the data set P; the dominated region B can be obtained by it. The points outside the dominated region B are definitely not skyline-like points.Figure 2
The dominated region.


## 3.1.2. Definitions in the Three-Dimensional Obstacle Space

It is assumed that the data set in this paper is the point set with spatial attributes and nonspatial attributes, the query set is the point set with spatial attributes, and the obstacles are all irregular three-dimensional objects.Definition 7.
Obstacle: Obstacles in the three-dimensional space are all cuboids perpendicular to the ground, with default random rotation angles. Each cuboid is represented byO (C,R,θ); C and R are three-dimensional coordinate points, where C = (XC,YC,ZC). Among them, C represents the center point of the cuboid, R is the distance between the center point and each coordinate plane of the cuboid, and θ is the rotation angle of the space object on the horizontal plane. The projection of the cuboid on the XOY plane is a random rectangle, and the rotation angle is the angle between the projected rectangle axis and the x-axis, as is shown in Figure 3.
In the three-dimensional obstacle space, the distance between two points is no longer Euclidean distance, and its calculation method needs to be redefined.Figure 3
The representation of obstacle in 3D space.Definition 8.
Three-dimensional obstacles visibility graph: The graph is similar to the graph in two-dimensional space; both of them include the vertex setV and the edge set E. In the visual graph based on point p and q, set V has the vertices in the intersection obstacle set of the line segment pq. Set E refers to the distance between the vertices in Set V. Assuming that set V contains n vertices, the size of set E is a square matrix of n × n, and the matrix is symmetric. If there is connectivity between the two points, the distance between the two points is recorded; otherwise, N is recorded, indicating that there is no connectivity between the two points. It is stipulated that the elements on the diagonal are all N in the graph; that is, each point has no connectivity to itself. The biggest difference between this graph and the two-dimensional graph is that the obstacles in this graph are all represented by a three-dimensional volume.Definition 9.
Obstacle distance in three-dimensional space: Obstacle distance in three-dimensional space refers to the shortest distance between any two pointsp and q calculated in the three-dimensional obstacle space. When there is no obstacle between p and q, the obstacle distance is equal to the Euclidean distance.Definition 10.
Obstacle skyline-like query: A set of objects in ad-dimensional space P = {p1,…,pn} and a query point q or a set of query points Q = {q1,…,qm} and the preference weight of each attribute W = {w1,…,wd} are given; the attribute preference value APValue of each skyline-like point is obtained by algorithm calculation. The 3D obstacle skyline query returns the skyline-like points sorted based on the attribute preference value in the 3D obstacle space set, which is called obstacle skyline-like query for short.


## 3.2. Theorems

Theorem 1.
If the data point setS1 is not dominated by nonspatial attributes, when judging whether the data point set S2 is dominated by spatial attributes, there is no need to consider the data point set S1.
Proof: The data point setS1 has been determined to be skyline-like points by Definition 4, and there is no need to repeat the comparison.Theorem 2.
All data points located outside the dominated region are dominated by the skyline-like points inside.Proof: The dominated region is constructed on the basis of the skyline-like point setS1. There must be a point p∈ S1; point p’ outside the dominated region is dominated by p through Definition 6.Theorem 3.
Suppose that there is a pointo on a line segment L, the direction vector of the line segment is d⟶, o and d⟶ are both known quantities, and any point p∈ L is taken; then the equation of the line segment L is defined as(2)p=o+td⟶,t∈tA,tB.Theorem 4.
If line segmentL intersects plane P, t=p0−o⋅n⟶/d⟶⋅n⟶ is satisfied.Proof.
The point method equationp−p0⋅n⟶=0 is used to define a certain plane P, and equation (2) is used to define the equations of the line segment of p and q. When the line segment intersects plane P, it must intersect at a certain point; that is, o+td⟶−p0⋅n⟶=0. Simplification leads to Theorem 4.Theorem 5.
Suppose that the intermediate node of the R tree is entry, the skyline-like result set is SP, and the Euclidean distance from the entry to the query pointq is EurDis. All the data points under the intermediate node entry could be filtered out directly, where ObsDis is the obstacle distance between the query point q and the node entry. The calculation process is shown in the next section.Proof.
If the Euclidean distance from the middle node entry of the R tree to the query pointq is EurDis, the distance must be less than or equal to the obstacle distance from all data points in the entry to q. If EurDis is greater than the obstacle distance ObsDis from all skyline-like points to q in the skyline-like result set, it means that the obstacle distance of all data points in this node is always greater than ObsDis; that is, there is no possibility of generating skyline-like points in this node; the theorem is proved.


## 4. Skyline-Like Query in Three-Dimensional Obstacle Space

When a skyline-like query is performed in the three-dimensional obstacle space, we could follow the steps below. Firstly, we obtain the skyline-like point setS1 that is not dominated by nonspatial attributes in the data set. According to the point set S1, the dominated region is constructed and the data set is filtered. Secondly, the preference weight of each attribute is obtained according to the degree of importance that the user places on each attribute. Finally, the point set S2 with advantages in spatial attributes in the data set is obtained and merged with the point set S1 with advantages in nonspatial attributes to form a complete skyline-like result set S3. According to the attribute preference weight, the attribute preference value of each data point is obtained, and the result set S is returned to the user in order according to preference value.Before the whole process, the data structure is designed first of all for the query, including data object, object in query, and obstacle object in the three-dimensional obstacle space.


### 4.1. Data Structure Design

In the three-dimensional obstacle space, the structure of the data object is designed as follows using Java language.DataObject = {id,x, y, z, rank, price}. Assume that the data object is the same as the object in the scene of the previous section; it is consistent with the description of the data object in Definition 1, and each data object has spatial attributes and nonspatial attributes. The spatial attribute is the location information (x, y, z), and the nonspatial attribute is the price and rating rank of the meeting place.The query object only has spatial attribute information, and the data structure is designed as QueryObject. QueryObject = {id,x, y, z}.Obstacles are represented by OBB bounding box in the three-dimensional obstacle space. The data structure of obstacle is expressed as Obstacle. Obstacle = {Center, Extend, GetCenter(), GetExtend(), GetX(), GetY(), GetZ()}. The definition of OBB bounding box here is consistent with the representation of obstacles in Definition7, where Center represents O in the definition, and Extend represents R in the definition. The methods GetCenter() and GetExtend() could obtain O and R of each obstacle, respectively. The methods GetX(), GetY(), and GetZ() could obtain distance R between the center point and each coordinate plane of the OBB.


### 4.2. Constructing Dominated Region Based on Nonspatial Attribute Skyline-Like Point Set

When constructing the dominated region in Definition6, it is necessary to obtain the skyline-like point set S1 that is not dominated by the nonspatial attributes in the data set. The traditional BBS algorithm is used to get the point set S1. In this process, the R tree is used to assist the query, and the special nature of the R tree is used to reduce the number of comparisons and improve the efficiency of the query. In order to obtain the skyline-like result set conveniently, we use R tree rTree1 and R tree rTree2 to store the nonspatial attribute value and spatial attribute value of each data point in the data set, and the id of the data point in rTree1 and rTree2 is the same.After the BBS algorithm is executed, a set of data pointsS1 that are not dominated by nonspatial attributes are obtained in data set P. The dominated region is constructed by S1. We use the dominated region to filter the rTree2 nodes that store data set P to improve the efficiency of the algorithm.The execution process of Algorithm1 is as follows. Firstly, the method Distance is used to calculate the distance between each query point q in the query set Q and each s in the skyline-like data point set S1. Secondly, we take q as the center of the sphere and Distance(q, s) as the radius to construct sphere S (q, s) in Definition 6. When there are multiple data points in Q, a set of balls are constructed. In this process, we use xmin and ymin to record the minimum of x-axis and y-axis coordinate values of all balls and xmax and ymax to record the maximum of x-axis and y-axis coordinate values (lines 3–16). Finally, the smallest outer box B of this group of balls is returned. B is the dominated region of the data point set.Algorithm 1: ConstructDominatedRegion algorithm.
Input: data point set S1, query set Q;Output: Area BBEGIN(1)
xmin =ymin = +∞;(2)
xmax = ymax =−∞;(3)
for eachs in S1 do(4)
for eachq in Q do(5)
if((q.x - Distance(q, s)) < xmin) then(6)
xmin = q-Distance(q, s);(7)
end(8)
if ((q.x + Distance(q, s)) > xmax) then(9)
xmax =q.x + Distance(q, s);(10)
end(11)
if((q.y - Distance(q, s)) < ymin) then(12)
ymin = Distance(q, s);(13)
end(14)
if((q.y + Distance(q, s)) > ymax) then(15)
ymax =q.y + Distance(q, s);(16)
end(17)
B = new Rect(xmin,ymin, xmax, ymax);(18)
return BEND


#### 4.2.1. 3D Obstacle Distance Calculation

Before obtaining data setS2 that is not dominated by the other points of spatial attributes, the distance between the data point and the query point needs to be calculated in the three-dimensional obstacle space, which can be divided into two steps. Firstly, a viewable graph (VG) should be constructed. Secondly, the shortest path is calculated by the viewable graph (VG).


#### 4.2.2. Construct the Three-Dimensional Viewable Graph

When constructing a three-dimensional viewable graph, the intersecting obstacles of the line segments need to be found in the scene, so it is necessary to determine the intersection of the line segment and the OBB bounding box. In this process, there are the following rules.Suppose that there is a line segmentL, the equation of which is shown in (2), and the rectangular parallelepiped represented by the OBB bounding box is expressed as OBox = [leftPoint, rightPoint]. Line segment L is shadowed onto the three axes where the OBB cube is located, and we calculate the corresponding intersection points of line segment L after shadowing according to the boundary value. If the value t overlaps corresponding to each coordinate axis direction determined by each intersection point, it means that line segment L intersects the OBox.Therefore, on the basis of the data structure Obstacle which represents the obstacle in three-dimensional space, the intersection obstacle set betweenPstart and Pend is obtained. As is shown in Figure 4, Pstart = (170, 30, 30) and Pend = (92, 109, 5); the obstacle set is distributed randomly. Through the overall view of the entire scene as Figure 4(a) and the top view as Figure 4(b), the obstacles o1, o2, and o3 that intersect with line segment PstartPend can be found directly. When we ascertain the intersection obstacle set with the line segment connected to the data point Pstart and the query point Pend, the above-mentioned rule of judging the line segment and the OBB bounding box is used to solve the problem.Figure 4
Obstacles in 3D space. (a) Overall view. (b) Top view.
(a)(b)After obtaining the set of intersecting obstacles, a three-dimensional viewable graph is constructed by Definition8. The graph contains the vertex set V and the edge set E. Set V is determined after the set of intersecting obstacles is obtained. As is shown in Figure 5, V = {Pstart, a, … h, i, …, o, Pend}. However, when we construct the edge set E, the visibility between the vertices needs to be detected, and the connectivity between the vertices is counted. The visible graph is obtained after the corresponding construction. There are two intersecting obstacles in this scene; the edge set E should be a matrix of 18 × 18, and the connectivity of the edge set is the same as that in Figure 5.Figure 5
The viewable graph in 3D space.


#### 4.2.3. The Calculation of the Shortest Obstacle Distance

After the three-dimensional viewable graph is constructed, the Dijkstra algorithm is used to obtain the shortest path. As is shown in Figure6, with the help of the viewable graph constructed by Figure 5, the shortest path from Pstart = (170, 30, 30) to Pend = (92, 109, 5) is obtained finally. It is concluded that we get 3 edges in set E as the shortest path, and the obstacle distance is obtained.Figure 6
The shortest path of the viewable graph.


### 4.3. The Attribute Preference Weight

In Algorithm2, the input of the function is the degree to which users value each attribute RankOfAtt1, RankOfAtt2, and RankOfAtt3, and these values are collected from the interface that interacts with the user. The degree of preference is divided into 3 levels {1, 2, 3}. When the value is 1, it means that the attribute is valued the most. For the degree of preference, the default is not to distinguish; that is, the skyline-like algorithm returns the data objects in the dataset that is not dominated by any other data point sets, and we do not sort them according to the attribute preference value. After collecting the user’s values of each attribute, we add and normalize them (lines 1–3). The method NormalMethod realizes the normalization of the degree of preference into the weight value of the attribute according to the proportion of each attribute; ∑i=1dwi = 1.Algorithm 2: SetUserWeights algorithm.
Input: RankOfAtt1, RankOfAtt2, RankOfAtt3;Output: attribute preference weight set WBEGIN(1)
W = ∅;(2)
RankOfSum = RankOfAtt1+RankOfAtt2 + RankOfAtt3;(3)
W = NormalMethod(RankOfSum);(4)
return W;ENDTake the above scenario as an example. The preference of each user’s distance from the meeting place is set to 1, the score of the meeting place is set to 2, and the price of the meeting place is set to 3. In this scenario, the attribute weight setW = {0.66,0.33,0.01} (line 4) is returned for the skyline-like query to sort the obtained points SP subsequently.


### 4.4. Skyline-Like Query in Obstacle Space

#### 4.4.1. Get the Skyline-Like Point Set of Spatial Attributes

When obtaining a data set that is not dominated by spatial attributes, rTree2 that stores data setP is processed according to Theorem 1, and the filtered rTree2 is input into the algorithm. The dominated region B of the R tree nodes in the algorithm is processed according to Theorem 2. The nodes that do not intersect with B are filtered out directly. When a new skyline-like point is obtained, B is updated to a new dominated region, which satisfies the preprocessing accuracy of the node continuously. By increasing the dominated region B, the iteration of nodes can be greatly reduced, and the workload can be reduced.The process of algorithm starts from rTree2. Firstly, the root node of rTree2 is stored in the ordered heapH. When H is not empty, the algorithm judges whether the root node being processed currently (including intermediate nodes and leaf nodes) is in region B. The initial value of B is the dominated region based on the construction of S1. When it is outside region B, it jumps out of this cycle directly; that is, the node must be dominated by the middle point set S1 or S2. Secondly, the algorithm continues. When H is not empty, the top element of H is processed as the next node. Otherwise, continue to process the node of rTree2. If the node is an intermediate node, the child nodes of the node are processed. If the above processing is consistent, we judge whether each child node intersects with B in turn. The child node that intersects with B is added to the ordered heap H. If the node is a leaf node, the data point is added to the result set directly when the data point is stored, and the size of B is recalculated. In the process of continuously adding result points to S2, B shrinks gradually. Finally, when H is empty, the loop ends and the whole process is completed.


#### 4.4.2. Skyline-Like Query Algorithm in Obstacle Space

After completing all the key algorithms mentioned above, we obtain the attribute preference weightW, the dominated region B, and the result set S1 and S2. Based on these parameters, the overall algorithm of the skyline-like query in obstacle space is given as Algorithm 3.Algorithm 3: OASQ algorithm.
Input: query set Q, R tree index rTree1, rTree2;Output: Obstacle skyline-like result set OSBEGIN(1)
OS =∅;(2)
OS1 = BBS(rTree1);(3)
B = ConstructDominanceBox(OS1, Q);(4)
for each dataPoint in rTree2 do(5)
if datapoint is in O or is not in B(6)
delete datapoint from rTree2;(7)
end if(8)
end for(9)
W = SetUserWeights();(10)
OS2 = 3DSkyline(Q, rTree2, B);(11)
OS.add(OS1, OS2);(12)
for eachs in OS do(13)
weight = CalculateWeight(W, s);(14)
s.SetAPValue(weight);(15)
end for(16)
OS = SOrderByWeight(OS);(17)
return OS;ENDThe arrayW and the set OS are defined and initialized in the algorithm, where W records the weight of each attribute and OS records the skyline-like points in data set P (line 1). The algorithm BBS is called to obtain the skyline-like points that are not dominated by points of nonspatial attributes in the skyline-like result set (line 2). The method ConstructDominanceBox is used to construct the dominated region of set S1. The realization algorithm is shown in Algorithm 1. According to Theorem 1, the determined skyline-like points and the data points outside region B in rTree2 are deleted (lines 4–8). Then, the method SetUserWeights is used to make statistics of the user’s preference value for each attribute and store it in array W (line 9). Algorithm 2 is the specific implementation. The filtered rTree2, query set Q, and candidate region B are passed into 3DSkyline to obtain the data point set S2 that is not dominated by points of spatial attributes in the data set (line 10). The sum of S1 and S2 obtained together constitutes the result set OS of the skyline-like query. According to the calculated attribute preference weight array W, all the skyline-like points in set OS are traversed, and the attribute preference values of the skyline-like points in OS are assigned (lines 11–15). Finally, all points in OS are sorted according to the attribute preference values and returned to the user (lines 16-17).


## 4.1. Data Structure Design

In the three-dimensional obstacle space, the structure of the data object is designed as follows using Java language.DataObject = {id,x, y, z, rank, price}. Assume that the data object is the same as the object in the scene of the previous section; it is consistent with the description of the data object in Definition 1, and each data object has spatial attributes and nonspatial attributes. The spatial attribute is the location information (x, y, z), and the nonspatial attribute is the price and rating rank of the meeting place.The query object only has spatial attribute information, and the data structure is designed as QueryObject. QueryObject = {id,x, y, z}.Obstacles are represented by OBB bounding box in the three-dimensional obstacle space. The data structure of obstacle is expressed as Obstacle. Obstacle = {Center, Extend, GetCenter(), GetExtend(), GetX(), GetY(), GetZ()}. The definition of OBB bounding box here is consistent with the representation of obstacles in Definition7, where Center represents O in the definition, and Extend represents R in the definition. The methods GetCenter() and GetExtend() could obtain O and R of each obstacle, respectively. The methods GetX(), GetY(), and GetZ() could obtain distance R between the center point and each coordinate plane of the OBB.


## 4.2. Constructing Dominated Region Based on Nonspatial Attribute Skyline-Like Point Set

When constructing the dominated region in Definition6, it is necessary to obtain the skyline-like point set S1 that is not dominated by the nonspatial attributes in the data set. The traditional BBS algorithm is used to get the point set S1. In this process, the R tree is used to assist the query, and the special nature of the R tree is used to reduce the number of comparisons and improve the efficiency of the query. In order to obtain the skyline-like result set conveniently, we use R tree rTree1 and R tree rTree2 to store the nonspatial attribute value and spatial attribute value of each data point in the data set, and the id of the data point in rTree1 and rTree2 is the same.After the BBS algorithm is executed, a set of data pointsS1 that are not dominated by nonspatial attributes are obtained in data set P. The dominated region is constructed by S1. We use the dominated region to filter the rTree2 nodes that store data set P to improve the efficiency of the algorithm.The execution process of Algorithm1 is as follows. Firstly, the method Distance is used to calculate the distance between each query point q in the query set Q and each s in the skyline-like data point set S1. Secondly, we take q as the center of the sphere and Distance(q, s) as the radius to construct sphere S (q, s) in Definition 6. When there are multiple data points in Q, a set of balls are constructed. In this process, we use xmin and ymin to record the minimum of x-axis and y-axis coordinate values of all balls and xmax and ymax to record the maximum of x-axis and y-axis coordinate values (lines 3–16). Finally, the smallest outer box B of this group of balls is returned. B is the dominated region of the data point set.Algorithm 1: ConstructDominatedRegion algorithm.
Input: data point set S1, query set Q;Output: Area BBEGIN(1)
xmin =ymin = +∞;(2)
xmax = ymax =−∞;(3)
for eachs in S1 do(4)
for eachq in Q do(5)
if((q.x - Distance(q, s)) < xmin) then(6)
xmin = q-Distance(q, s);(7)
end(8)
if ((q.x + Distance(q, s)) > xmax) then(9)
xmax =q.x + Distance(q, s);(10)
end(11)
if((q.y - Distance(q, s)) < ymin) then(12)
ymin = Distance(q, s);(13)
end(14)
if((q.y + Distance(q, s)) > ymax) then(15)
ymax =q.y + Distance(q, s);(16)
end(17)
B = new Rect(xmin,ymin, xmax, ymax);(18)
return BEND


### 4.2.1. 3D Obstacle Distance Calculation

Before obtaining data setS2 that is not dominated by the other points of spatial attributes, the distance between the data point and the query point needs to be calculated in the three-dimensional obstacle space, which can be divided into two steps. Firstly, a viewable graph (VG) should be constructed. Secondly, the shortest path is calculated by the viewable graph (VG).


### 4.2.2. Construct the Three-Dimensional Viewable Graph

When constructing a three-dimensional viewable graph, the intersecting obstacles of the line segments need to be found in the scene, so it is necessary to determine the intersection of the line segment and the OBB bounding box. In this process, there are the following rules.Suppose that there is a line segmentL, the equation of which is shown in (2), and the rectangular parallelepiped represented by the OBB bounding box is expressed as OBox = [leftPoint, rightPoint]. Line segment L is shadowed onto the three axes where the OBB cube is located, and we calculate the corresponding intersection points of line segment L after shadowing according to the boundary value. If the value t overlaps corresponding to each coordinate axis direction determined by each intersection point, it means that line segment L intersects the OBox.Therefore, on the basis of the data structure Obstacle which represents the obstacle in three-dimensional space, the intersection obstacle set betweenPstart and Pend is obtained. As is shown in Figure 4, Pstart = (170, 30, 30) and Pend = (92, 109, 5); the obstacle set is distributed randomly. Through the overall view of the entire scene as Figure 4(a) and the top view as Figure 4(b), the obstacles o1, o2, and o3 that intersect with line segment PstartPend can be found directly. When we ascertain the intersection obstacle set with the line segment connected to the data point Pstart and the query point Pend, the above-mentioned rule of judging the line segment and the OBB bounding box is used to solve the problem.Figure 4
Obstacles in 3D space. (a) Overall view. (b) Top view.
(a)(b)After obtaining the set of intersecting obstacles, a three-dimensional viewable graph is constructed by Definition8. The graph contains the vertex set V and the edge set E. Set V is determined after the set of intersecting obstacles is obtained. As is shown in Figure 5, V = {Pstart, a, … h, i, …, o, Pend}. However, when we construct the edge set E, the visibility between the vertices needs to be detected, and the connectivity between the vertices is counted. The visible graph is obtained after the corresponding construction. There are two intersecting obstacles in this scene; the edge set E should be a matrix of 18 × 18, and the connectivity of the edge set is the same as that in Figure 5.Figure 5
The viewable graph in 3D space.


### 4.2.3. The Calculation of the Shortest Obstacle Distance

After the three-dimensional viewable graph is constructed, the Dijkstra algorithm is used to obtain the shortest path. As is shown in Figure6, with the help of the viewable graph constructed by Figure 5, the shortest path from Pstart = (170, 30, 30) to Pend = (92, 109, 5) is obtained finally. It is concluded that we get 3 edges in set E as the shortest path, and the obstacle distance is obtained.Figure 6
The shortest path of the viewable graph.


## 4.2.1. 3D Obstacle Distance Calculation

Before obtaining data setS2 that is not dominated by the other points of spatial attributes, the distance between the data point and the query point needs to be calculated in the three-dimensional obstacle space, which can be divided into two steps. Firstly, a viewable graph (VG) should be constructed. Secondly, the shortest path is calculated by the viewable graph (VG).


## 4.2.2. Construct the Three-Dimensional Viewable Graph

When constructing a three-dimensional viewable graph, the intersecting obstacles of the line segments need to be found in the scene, so it is necessary to determine the intersection of the line segment and the OBB bounding box. In this process, there are the following rules.Suppose that there is a line segmentL, the equation of which is shown in (2), and the rectangular parallelepiped represented by the OBB bounding box is expressed as OBox = [leftPoint, rightPoint]. Line segment L is shadowed onto the three axes where the OBB cube is located, and we calculate the corresponding intersection points of line segment L after shadowing according to the boundary value. If the value t overlaps corresponding to each coordinate axis direction determined by each intersection point, it means that line segment L intersects the OBox.Therefore, on the basis of the data structure Obstacle which represents the obstacle in three-dimensional space, the intersection obstacle set betweenPstart and Pend is obtained. As is shown in Figure 4, Pstart = (170, 30, 30) and Pend = (92, 109, 5); the obstacle set is distributed randomly. Through the overall view of the entire scene as Figure 4(a) and the top view as Figure 4(b), the obstacles o1, o2, and o3 that intersect with line segment PstartPend can be found directly. When we ascertain the intersection obstacle set with the line segment connected to the data point Pstart and the query point Pend, the above-mentioned rule of judging the line segment and the OBB bounding box is used to solve the problem.Figure 4
Obstacles in 3D space. (a) Overall view. (b) Top view.
(a)(b)After obtaining the set of intersecting obstacles, a three-dimensional viewable graph is constructed by Definition8. The graph contains the vertex set V and the edge set E. Set V is determined after the set of intersecting obstacles is obtained. As is shown in Figure 5, V = {Pstart, a, … h, i, …, o, Pend}. However, when we construct the edge set E, the visibility between the vertices needs to be detected, and the connectivity between the vertices is counted. The visible graph is obtained after the corresponding construction. There are two intersecting obstacles in this scene; the edge set E should be a matrix of 18 × 18, and the connectivity of the edge set is the same as that in Figure 5.Figure 5
The viewable graph in 3D space.


## 4.2.3. The Calculation of the Shortest Obstacle Distance

After the three-dimensional viewable graph is constructed, the Dijkstra algorithm is used to obtain the shortest path. As is shown in Figure6, with the help of the viewable graph constructed by Figure 5, the shortest path from Pstart = (170, 30, 30) to Pend = (92, 109, 5) is obtained finally. It is concluded that we get 3 edges in set E as the shortest path, and the obstacle distance is obtained.Figure 6
The shortest path of the viewable graph.


## 4.3. The Attribute Preference Weight

In Algorithm2, the input of the function is the degree to which users value each attribute RankOfAtt1, RankOfAtt2, and RankOfAtt3, and these values are collected from the interface that interacts with the user. The degree of preference is divided into 3 levels {1, 2, 3}. When the value is 1, it means that the attribute is valued the most. For the degree of preference, the default is not to distinguish; that is, the skyline-like algorithm returns the data objects in the dataset that is not dominated by any other data point sets, and we do not sort them according to the attribute preference value. After collecting the user’s values of each attribute, we add and normalize them (lines 1–3). The method NormalMethod realizes the normalization of the degree of preference into the weight value of the attribute according to the proportion of each attribute; ∑i=1dwi = 1.Algorithm 2: SetUserWeights algorithm.
Input: RankOfAtt1, RankOfAtt2, RankOfAtt3;Output: attribute preference weight set WBEGIN(1)
W = ∅;(2)
RankOfSum = RankOfAtt1+RankOfAtt2 + RankOfAtt3;(3)
W = NormalMethod(RankOfSum);(4)
return W;ENDTake the above scenario as an example. The preference of each user’s distance from the meeting place is set to 1, the score of the meeting place is set to 2, and the price of the meeting place is set to 3. In this scenario, the attribute weight setW = {0.66,0.33,0.01} (line 4) is returned for the skyline-like query to sort the obtained points SP subsequently.


## 4.4. Skyline-Like Query in Obstacle Space

### 4.4.1. Get the Skyline-Like Point Set of Spatial Attributes

When obtaining a data set that is not dominated by spatial attributes, rTree2 that stores data setP is processed according to Theorem 1, and the filtered rTree2 is input into the algorithm. The dominated region B of the R tree nodes in the algorithm is processed according to Theorem 2. The nodes that do not intersect with B are filtered out directly. When a new skyline-like point is obtained, B is updated to a new dominated region, which satisfies the preprocessing accuracy of the node continuously. By increasing the dominated region B, the iteration of nodes can be greatly reduced, and the workload can be reduced.The process of algorithm starts from rTree2. Firstly, the root node of rTree2 is stored in the ordered heapH. When H is not empty, the algorithm judges whether the root node being processed currently (including intermediate nodes and leaf nodes) is in region B. The initial value of B is the dominated region based on the construction of S1. When it is outside region B, it jumps out of this cycle directly; that is, the node must be dominated by the middle point set S1 or S2. Secondly, the algorithm continues. When H is not empty, the top element of H is processed as the next node. Otherwise, continue to process the node of rTree2. If the node is an intermediate node, the child nodes of the node are processed. If the above processing is consistent, we judge whether each child node intersects with B in turn. The child node that intersects with B is added to the ordered heap H. If the node is a leaf node, the data point is added to the result set directly when the data point is stored, and the size of B is recalculated. In the process of continuously adding result points to S2, B shrinks gradually. Finally, when H is empty, the loop ends and the whole process is completed.


### 4.4.2. Skyline-Like Query Algorithm in Obstacle Space

After completing all the key algorithms mentioned above, we obtain the attribute preference weightW, the dominated region B, and the result set S1 and S2. Based on these parameters, the overall algorithm of the skyline-like query in obstacle space is given as Algorithm 3.Algorithm 3: OASQ algorithm.
Input: query set Q, R tree index rTree1, rTree2;Output: Obstacle skyline-like result set OSBEGIN(1)
OS =∅;(2)
OS1 = BBS(rTree1);(3)
B = ConstructDominanceBox(OS1, Q);(4)
for each dataPoint in rTree2 do(5)
if datapoint is in O or is not in B(6)
delete datapoint from rTree2;(7)
end if(8)
end for(9)
W = SetUserWeights();(10)
OS2 = 3DSkyline(Q, rTree2, B);(11)
OS.add(OS1, OS2);(12)
for eachs in OS do(13)
weight = CalculateWeight(W, s);(14)
s.SetAPValue(weight);(15)
end for(16)
OS = SOrderByWeight(OS);(17)
return OS;ENDThe arrayW and the set OS are defined and initialized in the algorithm, where W records the weight of each attribute and OS records the skyline-like points in data set P (line 1). The algorithm BBS is called to obtain the skyline-like points that are not dominated by points of nonspatial attributes in the skyline-like result set (line 2). The method ConstructDominanceBox is used to construct the dominated region of set S1. The realization algorithm is shown in Algorithm 1. According to Theorem 1, the determined skyline-like points and the data points outside region B in rTree2 are deleted (lines 4–8). Then, the method SetUserWeights is used to make statistics of the user’s preference value for each attribute and store it in array W (line 9). Algorithm 2 is the specific implementation. The filtered rTree2, query set Q, and candidate region B are passed into 3DSkyline to obtain the data point set S2 that is not dominated by points of spatial attributes in the data set (line 10). The sum of S1 and S2 obtained together constitutes the result set OS of the skyline-like query. According to the calculated attribute preference weight array W, all the skyline-like points in set OS are traversed, and the attribute preference values of the skyline-like points in OS are assigned (lines 11–15). Finally, all points in OS are sorted according to the attribute preference values and returned to the user (lines 16-17).


## 4.4.1. Get the Skyline-Like Point Set of Spatial Attributes

When obtaining a data set that is not dominated by spatial attributes, rTree2 that stores data setP is processed according to Theorem 1, and the filtered rTree2 is input into the algorithm. The dominated region B of the R tree nodes in the algorithm is processed according to Theorem 2. The nodes that do not intersect with B are filtered out directly. When a new skyline-like point is obtained, B is updated to a new dominated region, which satisfies the preprocessing accuracy of the node continuously. By increasing the dominated region B, the iteration of nodes can be greatly reduced, and the workload can be reduced.The process of algorithm starts from rTree2. Firstly, the root node of rTree2 is stored in the ordered heapH. When H is not empty, the algorithm judges whether the root node being processed currently (including intermediate nodes and leaf nodes) is in region B. The initial value of B is the dominated region based on the construction of S1. When it is outside region B, it jumps out of this cycle directly; that is, the node must be dominated by the middle point set S1 or S2. Secondly, the algorithm continues. When H is not empty, the top element of H is processed as the next node. Otherwise, continue to process the node of rTree2. If the node is an intermediate node, the child nodes of the node are processed. If the above processing is consistent, we judge whether each child node intersects with B in turn. The child node that intersects with B is added to the ordered heap H. If the node is a leaf node, the data point is added to the result set directly when the data point is stored, and the size of B is recalculated. In the process of continuously adding result points to S2, B shrinks gradually. Finally, when H is empty, the loop ends and the whole process is completed.


## 4.4.2. Skyline-Like Query Algorithm in Obstacle Space

After completing all the key algorithms mentioned above, we obtain the attribute preference weightW, the dominated region B, and the result set S1 and S2. Based on these parameters, the overall algorithm of the skyline-like query in obstacle space is given as Algorithm 3.Algorithm 3: OASQ algorithm.
Input: query set Q, R tree index rTree1, rTree2;Output: Obstacle skyline-like result set OSBEGIN(1)
OS =∅;(2)
OS1 = BBS(rTree1);(3)
B = ConstructDominanceBox(OS1, Q);(4)
for each dataPoint in rTree2 do(5)
if datapoint is in O or is not in B(6)
delete datapoint from rTree2;(7)
end if(8)
end for(9)
W = SetUserWeights();(10)
OS2 = 3DSkyline(Q, rTree2, B);(11)
OS.add(OS1, OS2);(12)
for eachs in OS do(13)
weight = CalculateWeight(W, s);(14)
s.SetAPValue(weight);(15)
end for(16)
OS = SOrderByWeight(OS);(17)
return OS;ENDThe arrayW and the set OS are defined and initialized in the algorithm, where W records the weight of each attribute and OS records the skyline-like points in data set P (line 1). The algorithm BBS is called to obtain the skyline-like points that are not dominated by points of nonspatial attributes in the skyline-like result set (line 2). The method ConstructDominanceBox is used to construct the dominated region of set S1. The realization algorithm is shown in Algorithm 1. According to Theorem 1, the determined skyline-like points and the data points outside region B in rTree2 are deleted (lines 4–8). Then, the method SetUserWeights is used to make statistics of the user’s preference value for each attribute and store it in array W (line 9). Algorithm 2 is the specific implementation. The filtered rTree2, query set Q, and candidate region B are passed into 3DSkyline to obtain the data point set S2 that is not dominated by points of spatial attributes in the data set (line 10). The sum of S1 and S2 obtained together constitutes the result set OS of the skyline-like query. According to the calculated attribute preference weight array W, all the skyline-like points in set OS are traversed, and the attribute preference values of the skyline-like points in OS are assigned (lines 11–15). Finally, all points in OS are sorted according to the attribute preference values and returned to the user (lines 16-17).


## 5. Experimental Results and Analysis

The operating system of this experiment is based on the 64-bit Microsoft Windows 10 system, the development environment uses IntelliJ IDEA 2018, and the Java language is used to code the experiment. The hardware environment is Intel (R) Core (TM) i7-7500U CPU @2.70 GHz, quad-core, 8 GB RAM.The interface of the system for skyline-like query in obstacle space is shown in Figure7. First of all, we generate the data set required in the entire experiment mainly referring to storing the data set and obstacles in the table output_obj and output_obs of the database, respectively. When performing subsequent queries, the information in the above tables needs to be loaded into the program. Next, we make the skyline-like query in obstacle space and determine the location and number of query points required according to the user’s needs. By default, this query is based on the input interface of multiple query points. If a query point needs to be added, we can do it by clicking the button Add. As mentioned in the above scenario, the data points in the data set have nonspatial attributes and spatial attributes. The nonspatial attributes of the data set in this experimental system are price and rating, and the spatial attribute is the position from each query point. Users have different values for each attribute which is divided into 1, 2, and 3 levels; when the value is set to 1, it indicates that the user values the attribute the most, and the preference of each attribute is the same by default. Next, we perform obstacle skyline query, and the result information is displayed directly on the interface. As is shown in Figure 8, it is a visual display result set of the skyline-like query in obstacle space. Left and right parts of the figure represent the results set of nonspatial attributes and spatial attributes. Among them, the highlighted red points represent the skyline-like point set, and the gray points represent the points dominated by the skyline-like point in the data set.Figure 7
Interface of skyline-like query.Figure 8
Nonspatial and spatial skyline-like points.


### 5.1. Comparative Experiments with B2S2 Algorithm

This section mainly compares the proposed skyline-like query algorithm (SLQ) and B2S2 algorithm (B2S2) for experimental comparison and analysis. The data set and query points required in the experiment are all in the space of [0, 5000]∗ [0, 5000] ∗ [0, 5000], and each data point is distributed arbitrarily in the space. The environment of traditional B2S2 algorithm is in the two-dimensional European space, so, in this process, 5000 and 10000 data sets are chosen for comparison of the value of z-axis of all data sets which is set to 0. By setting different number of query points, the two algorithms are analyzed and compared without involving obstacles.Comparing and analyzing the results of the algorithms are as shown in Figures9(a) and 9(b); both of them have the same results. As the number of data sets increases, the query time of the two algorithms increases, but the growth rate of SLQ is slower than that of the B2S2 algorithm. When the size of the data set is determined, as the number of query points increases, the query times of the SLQ algorithm and the B2S2 algorithm also increase accordingly. But, compared with the B2S2 algorithm, the growth rate of the SLQ algorithm is relatively flat.Figure 9
Results of the algorithms. (a) Under 5000 data sets. (b) Under 10000 data sets.
(a)(b)


### 5.2. Comparative Experiments within the SLQ Algorithm

This section compares internal experiments with different numbers of data points and obstacles in the data set and analyzes the impact on the efficiency of skyline-like queries.We analyze the impact of the size of the data set on the query time and the number of result sets. Under the principle of unity, we observe the influence on the query result when the numbers of data points and query points change. In the meantime, the number of obstacles is the same. Therefore, data setsS1 and S2 are set, and the numbers of data points and obstacles corresponding to each data set are shown in Table 1. Different query points are set for the above two data sets to perform the queries. Among them, the data points and obstacles in the experiment are all in the space of [0,10000] ∗ [0,10000] ∗ [0,10000], and each data point is distributed randomly in the space.Table 1
Data set of experiments.
Data setNumber of data pointsNumber of obstaclesS11000100S23000100Figure10 shows the impact of the number of query points on the running time based on the data set in Table 1. The two lines represent changes of the runtime for the experiment under different numbers of query points for data sets S1 and S2. In general, as the orders of magnitude of data points and query points increase, the results of the runtime increase. However, when one query point is set in data sets s1 and s2, it is found that the running time is not much different. For line S1, it is relatively flat, indicating that the runtime does not increase much when the number of query points increases and the data set is small. Therefore, the size of the data set and the number of query points increase the runtime.Figure 10
Line chart under different data sets and different query points.Figure11 shows the influence of the number of query points on the quantity of skyline-like points in the query result set based on the data set shown in Table 1. The bar graph under each color represents the comparison of the number of skyline-like points. These points were obtained under the condition of different query points in the same data set. Each group of bar graphs based on the horizontal axis represents comparison of the number of skyline-like points under the different data sets, but the number of query points is the same. It can be seen that, under the same number of query points, as the data set increases, the number of skyline-like result sets increases. With the increase of the data set’s magnitude, the growth of the skyline-like result set becomes greater. When the magnitude of the data set is the same, as the number of query points increases, the number of skyline-like result sets increases. In short, the increase of the magnitude of the data set leads to the increase of the skyline-like result sets, but it can be seen from the figure that the increase of the data set has a greater impact on the number of skyline-like result sets.Figure 11
Time comparison bar chart of different skyline-like points.


## 5.1. Comparative Experiments with B2S2 Algorithm

This section mainly compares the proposed skyline-like query algorithm (SLQ) and B2S2 algorithm (B2S2) for experimental comparison and analysis. The data set and query points required in the experiment are all in the space of [0, 5000]∗ [0, 5000] ∗ [0, 5000], and each data point is distributed arbitrarily in the space. The environment of traditional B2S2 algorithm is in the two-dimensional European space, so, in this process, 5000 and 10000 data sets are chosen for comparison of the value of z-axis of all data sets which is set to 0. By setting different number of query points, the two algorithms are analyzed and compared without involving obstacles.Comparing and analyzing the results of the algorithms are as shown in Figures9(a) and 9(b); both of them have the same results. As the number of data sets increases, the query time of the two algorithms increases, but the growth rate of SLQ is slower than that of the B2S2 algorithm. When the size of the data set is determined, as the number of query points increases, the query times of the SLQ algorithm and the B2S2 algorithm also increase accordingly. But, compared with the B2S2 algorithm, the growth rate of the SLQ algorithm is relatively flat.Figure 9
Results of the algorithms. (a) Under 5000 data sets. (b) Under 10000 data sets.
(a)(b)


## 5.2. Comparative Experiments within the SLQ Algorithm

This section compares internal experiments with different numbers of data points and obstacles in the data set and analyzes the impact on the efficiency of skyline-like queries.We analyze the impact of the size of the data set on the query time and the number of result sets. Under the principle of unity, we observe the influence on the query result when the numbers of data points and query points change. In the meantime, the number of obstacles is the same. Therefore, data setsS1 and S2 are set, and the numbers of data points and obstacles corresponding to each data set are shown in Table 1. Different query points are set for the above two data sets to perform the queries. Among them, the data points and obstacles in the experiment are all in the space of [0,10000] ∗ [0,10000] ∗ [0,10000], and each data point is distributed randomly in the space.Table 1
Data set of experiments.
Data setNumber of data pointsNumber of obstaclesS11000100S23000100Figure10 shows the impact of the number of query points on the running time based on the data set in Table 1. The two lines represent changes of the runtime for the experiment under different numbers of query points for data sets S1 and S2. In general, as the orders of magnitude of data points and query points increase, the results of the runtime increase. However, when one query point is set in data sets s1 and s2, it is found that the running time is not much different. For line S1, it is relatively flat, indicating that the runtime does not increase much when the number of query points increases and the data set is small. Therefore, the size of the data set and the number of query points increase the runtime.Figure 10
Line chart under different data sets and different query points.Figure11 shows the influence of the number of query points on the quantity of skyline-like points in the query result set based on the data set shown in Table 1. The bar graph under each color represents the comparison of the number of skyline-like points. These points were obtained under the condition of different query points in the same data set. Each group of bar graphs based on the horizontal axis represents comparison of the number of skyline-like points under the different data sets, but the number of query points is the same. It can be seen that, under the same number of query points, as the data set increases, the number of skyline-like result sets increases. With the increase of the data set’s magnitude, the growth of the skyline-like result set becomes greater. When the magnitude of the data set is the same, as the number of query points increases, the number of skyline-like result sets increases. In short, the increase of the magnitude of the data set leads to the increase of the skyline-like result sets, but it can be seen from the figure that the increase of the data set has a greater impact on the number of skyline-like result sets.Figure 11
Time comparison bar chart of different skyline-like points.


## 6. Conclusion

The traditional skyline query cannot give the result set well when we need to consider nonspatial attributes of the dataset, spatial attributes of the dataset, and user’s preferences comprehensively in 3D obstacle space. The traditional skyline query is not applied to the three-dimensional obstacle space. Aiming at the above problem, an improved skyline query algorithm for obstacles was proposed. Firstly, new definitions of the problem were defined in the skyline-like query, including the attribute preference value, the dominated region, the obstacle distance, and the skyline-like query in obstacle space. Secondly, the obstacle distance used in the query was described in detail, including its definition in the three-dimensional obstacle space and the algorithm and description of the solution. Finally, the calculated distance was applied to the skyline-like query, and the skyline-like points that met the requirements were returned. On this basis, these points were sorted according to the value of the user attribute. Experimental results showed that the algorithm had good query performance. However, the algorithm still had certain limitations. The distribution of nonspatial attributes of the skyline-like points would have been scattered relatively in practice. In that case, the pruning effect on the data set would be weakened, and the query efficiency would be reduced. Therefore, in-depth study will be conducted on this issue in the future.



---

*Source: 3978601-2022-05-11.xml*