Spatial relationships are core components in the design and definition of spatial queries.A spatial relationship determines how two or more spatial objects are related or connected in space.Hence,given a spatial datas...Spatial relationships are core components in the design and definition of spatial queries.A spatial relationship determines how two or more spatial objects are related or connected in space.Hence,given a spatial dataset,users can retrieve spatial objects in a given relationship with a search object.Different interpretations of spatial relationships are conceivable,leading to different types of relationships.The main types are(i)topological relationships(e.g.overlap,meet,inside),(ii)metric relationships(e.g.nearest neighbors),and(iii)direction relationships(e.g.cardinal directions).Although spatial information retrieval has been extensively studied in the literature,it is unclear which types of spatial queries can be defined using spatial relationships.In this article,we introduce a taxonomy for naming,describing,and classifying types of spatial queries frequently found in the literature.This taxonomy is based on the types of spatial relationships that are employed by spatial queries.By using this taxonomy,we discuss the intuitive descriptions,formal definitions,and possible implementation techniques of several types of spatial queries.The discussions lead to the identification of correspondences between types of spatial queries.Further,we identify challenges and open research topics in the spatial information retrieval area.展开更多
The construction of oceanographic ontologies is fundamental to the ＂digital ocean＂. Therefore, on the basis of introduction of new concept of oceanographic ontology, an oceanographic ontology-based spatial knowledge...The construction of oceanographic ontologies is fundamental to the ＂digital ocean＂. Therefore, on the basis of introduction of new concept of oceanographic ontology, an oceanographic ontology-based spatial knowledge query （OOBSKQ） method was proposed and developed. Because the method uses a natural language to describe query conditions and the query result is highly integrated knowledge, it can provide users with direct answers while hiding the complicated computation and reasoning processes, and achieves intelligent, automatic oceanographic spatial information query on the level of knowledge and semantics. A case study of resource and environmental application in bay has shown the implementation process of the method and its feasibility and usefulness.展开更多
Since web based GIS processes large size spatial geographic information on internet, we should try to improve the efficiency of spatial data query processing and transmission. This paper presents two efficient metho...Since web based GIS processes large size spatial geographic information on internet, we should try to improve the efficiency of spatial data query processing and transmission. This paper presents two efficient methods for this purpose: division transmission and progressive transmission methods. In division transmission method, a map can be divided into several parts, called “tiles”, and only tiles can be transmitted at the request of a client. In progressive transmission method, a map can be split into several phase views based on the significance of vertices, and a server produces a target object and then transmits it progressively when this spatial object is requested from a client. In order to achieve these methods, the algorithms, “tile division”, “priority order estimation” and the strategies for data transmission are proposed in this paper, respectively. Compared with such traditional methods as “map total transmission” and “layer transmission”, the web based GIS data transmission, proposed in this paper, is advantageous in the increase of the data transmission efficiency by a great margin.展开更多
Spatial selectivity estimation is crucial to choose the cheapest execution plan for a given query in a query optimizer.This article proposes an accurate spatial selectivity estimation method based on the cumulative de...Spatial selectivity estimation is crucial to choose the cheapest execution plan for a given query in a query optimizer.This article proposes an accurate spatial selectivity estimation method based on the cumulative density(CD)histograms,which can deal with any arbitrary spatial query window.In this method,the selectivity can be estimated in original logic of the CD histogram,after the four corner values of a query window have been accurately interpolated on the continuous surface of the elevation histogram.For the interpolation of any corner points,we first identify the cells that can affect the value of point(x,y)in the CD histogram.These cells can be categorized into two classes:ones within the range from(0,0)to(x,y)and the other overlapping the range from(0,0)to(x,y).The values of the former class can be used directly,whereas we revise the values of any cells falling in the latter class by the number of vertices in the corresponding cell and the area ratio covered by the range from(0,0)to(x,y).This revision makes the estimation method more accurate.The CD histograms and estimation method have been implemented in INGRES.Experiment results show that the method can accurately estimate the selectivity of arbitrary query windows and can help the optimizer choose a cheaper query plan.展开更多
A novel technique called the bitmap lattice index(BLI) is proposed, which combines the advantages of a wireless broadcasting environment with a road network. Existing road networks are based on the on-demand method: a...A novel technique called the bitmap lattice index(BLI) is proposed, which combines the advantages of a wireless broadcasting environment with a road network. Existing road networks are based on the on-demand method: a server's workload increases as the query request increases when a server sends a client information. To solve this problem, we propose the BLI. The BLI denotes an object and a node as 0 and 1 in the Hilbert curve(HC) map. The BLI can identify the position of a node and an object through bit information; it can also reduce the broadcasting frequency of a server by reducing the size of the index, thereby decreasing the access latency and query processing times. Moreover, the BLI is highly effective for data filtering, as it can identify the positions of both an object and a node. In a road network, if filtering is done via the Euclidean distance, it may result in an error. To prevent this, we add another validation procedure. The experiment is conducted by applying the BLI to kNN query, and the technique is assessed by a performance evaluation experiment.展开更多
In the era of abundant location-based data,an increasing number of mobile users seek access to timely local information tailored to their individual interests.Consequently,the development of an efficient publish/subsc...In the era of abundant location-based data,an increasing number of mobile users seek access to timely local information tailored to their individual interests.Consequently,the development of an efficient publish/subscribe system becomes pivotal,allowing a vast user base to seamlessly receive geo-textual objects based on their specific preferences from data streams.However,a notable challenge arises as mobile users often hesitate to disclose their personal interests,requirements,and locations to service providers in location-based publish/subscribe systems,giving rise to substantial data privacy concerns.In this light,we propose a privacy-preserving publish/subscribe framework,which not only facilitates real-time delivery of geo-textual objects to a large-scale audience of location-based subscribers,but also ensures the utmost privacy of subscribers'locations and query keywords.Through experiments conducted on two real-life datasets,our proposed privacy-preserving publish/subscribe system demonstrates its capability to produce real-time matching results.The system can simultaneously handle millions of privacy-enhanced subscription queries over a stream of geo-textual objects.展开更多
Nowadays,location-based services are widely used,requiring instant responses to a large volume of multiple spatial queries over massive road networks,i.e.,single-pair shortest path(SPSP)query,k-nearest neighbor(kNN)qu...Nowadays,location-based services are widely used,requiring instant responses to a large volume of multiple spatial queries over massive road networks,i.e.,single-pair shortest path(SPSP)query,k-nearest neighbor(kNN)query,and range query.Creating index-based structure for each kind of query is costly,hence it is important to handle multiple spatial queries within one efficient structure.Partition-based hierarchical approaches show promising potential to meet the requirement.However,existing approaches require large search space on massive road networks especially for long-distance queries,which is inefficient and hard to scale.To overcome the drawbacks,we propose the shortcut-enhanced graph hierarchy tree(SCG-tree),which leverages shortcuts to effectively prune the search space over a hierarchical structure.With the SCG-tree,a pruned shortcut-based method is designed to answer SPSP query,and a two-phase expansion strategy is proposed to leverage shortcuts for kNN and range queries.Theoretical analyses show the superiority of proposed shortcut-based query algorithms.Extensive experiments demonstrate that our approach can achieve three times speedup for kNN query and an order of magnitude speedup for SPSP and range queries over existing methods on real road networks that scale up to 24 million nodes and 58 million edges.展开更多
基金financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior-Brasil(CAPES)-Finance Code 001.Anderson C.Carniel was supported by Google as a recipient of the 2022 Google Research Scholar program.
文摘Spatial relationships are core components in the design and definition of spatial queries.A spatial relationship determines how two or more spatial objects are related or connected in space.Hence,given a spatial dataset,users can retrieve spatial objects in a given relationship with a search object.Different interpretations of spatial relationships are conceivable,leading to different types of relationships.The main types are(i)topological relationships(e.g.overlap,meet,inside),(ii)metric relationships(e.g.nearest neighbors),and(iii)direction relationships(e.g.cardinal directions).Although spatial information retrieval has been extensively studied in the literature,it is unclear which types of spatial queries can be defined using spatial relationships.In this article,we introduce a taxonomy for naming,describing,and classifying types of spatial queries frequently found in the literature.This taxonomy is based on the types of spatial relationships that are employed by spatial queries.By using this taxonomy,we discuss the intuitive descriptions,formal definitions,and possible implementation techniques of several types of spatial queries.The discussions lead to the identification of correspondences between types of spatial queries.Further,we identify challenges and open research topics in the spatial information retrieval area.
基金This study was supported by the“863”Marine Monitor of High-tech Research and Development Program of China under contracts Nos 2003AA604040 and 2003AA637030.
文摘The construction of oceanographic ontologies is fundamental to the ＂digital ocean＂. Therefore, on the basis of introduction of new concept of oceanographic ontology, an oceanographic ontology-based spatial knowledge query （OOBSKQ） method was proposed and developed. Because the method uses a natural language to describe query conditions and the query result is highly integrated knowledge, it can provide users with direct answers while hiding the complicated computation and reasoning processes, and achieves intelligent, automatic oceanographic spatial information query on the level of knowledge and semantics. A case study of resource and environmental application in bay has shown the implementation process of the method and its feasibility and usefulness.
文摘Since web based GIS processes large size spatial geographic information on internet, we should try to improve the efficiency of spatial data query processing and transmission. This paper presents two efficient methods for this purpose: division transmission and progressive transmission methods. In division transmission method, a map can be divided into several parts, called “tiles”, and only tiles can be transmitted at the request of a client. In progressive transmission method, a map can be split into several phase views based on the significance of vertices, and a server produces a target object and then transmits it progressively when this spatial object is requested from a client. In order to achieve these methods, the algorithms, “tile division”, “priority order estimation” and the strategies for data transmission are proposed in this paper, respectively. Compared with such traditional methods as “map total transmission” and “layer transmission”, the web based GIS data transmission, proposed in this paper, is advantageous in the increase of the data transmission efficiency by a great margin.
基金This work was supported by the National Natural Science Foundation of China[grant numbers 41222009,41271405].
文摘Spatial selectivity estimation is crucial to choose the cheapest execution plan for a given query in a query optimizer.This article proposes an accurate spatial selectivity estimation method based on the cumulative density(CD)histograms,which can deal with any arbitrary spatial query window.In this method,the selectivity can be estimated in original logic of the CD histogram,after the four corner values of a query window have been accurately interpolated on the continuous surface of the elevation histogram.For the interpolation of any corner points,we first identify the cells that can affect the value of point(x,y)in the CD histogram.These cells can be categorized into two classes:ones within the range from(0,0)to(x,y)and the other overlapping the range from(0,0)to(x,y).The values of the former class can be used directly,whereas we revise the values of any cells falling in the latter class by the number of vertices in the corresponding cell and the area ratio covered by the range from(0,0)to(x,y).This revision makes the estimation method more accurate.The CD histograms and estimation method have been implemented in INGRES.Experiment results show that the method can accurately estimate the selectivity of arbitrary query windows and can help the optimizer choose a cheaper query plan.
基金supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (NRF2013R1A1A1004593, 2013R1A1A1A05012348)
文摘A novel technique called the bitmap lattice index(BLI) is proposed, which combines the advantages of a wireless broadcasting environment with a road network. Existing road networks are based on the on-demand method: a server's workload increases as the query request increases when a server sends a client information. To solve this problem, we propose the BLI. The BLI denotes an object and a node as 0 and 1 in the Hilbert curve(HC) map. The BLI can identify the position of a node and an object through bit information; it can also reduce the broadcasting frequency of a server by reducing the size of the index, thereby decreasing the access latency and query processing times. Moreover, the BLI is highly effective for data filtering, as it can identify the positions of both an object and a node. In a road network, if filtering is done via the Euclidean distance, it may result in an error. To prevent this, we add another validation procedure. The experiment is conducted by applying the BLI to kNN query, and the technique is assessed by a performance evaluation experiment.
基金supported by National Natural Science Foundation of China under Grant No.72131001
文摘In the era of abundant location-based data,an increasing number of mobile users seek access to timely local information tailored to their individual interests.Consequently,the development of an efficient publish/subscribe system becomes pivotal,allowing a vast user base to seamlessly receive geo-textual objects based on their specific preferences from data streams.However,a notable challenge arises as mobile users often hesitate to disclose their personal interests,requirements,and locations to service providers in location-based publish/subscribe systems,giving rise to substantial data privacy concerns.In this light,we propose a privacy-preserving publish/subscribe framework,which not only facilitates real-time delivery of geo-textual objects to a large-scale audience of location-based subscribers,but also ensures the utmost privacy of subscribers'locations and query keywords.Through experiments conducted on two real-life datasets,our proposed privacy-preserving publish/subscribe system demonstrates its capability to produce real-time matching results.The system can simultaneously handle millions of privacy-enhanced subscription queries over a stream of geo-textual objects.
基金supported by the Frontier Technology R&D Project of Jiangsu(BF2024059)the National Natural Science Foundation of China(Grant No.6240071854)+1 种基金the Natural Science Foundation of Jiangsu Province(BK20241381)the Jiangsu Association for Science and Technology Youth Science and Technology Talent Support Project(JSTJ-2023-XH055).
文摘Nowadays,location-based services are widely used,requiring instant responses to a large volume of multiple spatial queries over massive road networks,i.e.,single-pair shortest path(SPSP)query,k-nearest neighbor(kNN)query,and range query.Creating index-based structure for each kind of query is costly,hence it is important to handle multiple spatial queries within one efficient structure.Partition-based hierarchical approaches show promising potential to meet the requirement.However,existing approaches require large search space on massive road networks especially for long-distance queries,which is inefficient and hard to scale.To overcome the drawbacks,we propose the shortcut-enhanced graph hierarchy tree(SCG-tree),which leverages shortcuts to effectively prune the search space over a hierarchical structure.With the SCG-tree,a pruned shortcut-based method is designed to answer SPSP query,and a two-phase expansion strategy is proposed to leverage shortcuts for kNN and range queries.Theoretical analyses show the superiority of proposed shortcut-based query algorithms.Extensive experiments demonstrate that our approach can achieve three times speedup for kNN query and an order of magnitude speedup for SPSP and range queries over existing methods on real road networks that scale up to 24 million nodes and 58 million edges.
