Node and edge selectivity estimation for range queries in spatial networks

作者:

Highlights:

摘要

Modern applications requiring spatial network processing pose several interesting query optimization challenges. Spatial networks are usually represented as graphs, and therefore, queries involving a spatial network can be executed by using the corresponding graph representation. This means that the cost for executing a query is determined by graph properties such as the graph order and size (i.e., number of nodes and edges) and other graph parameters. In this paper, we present novel methods to estimate the number of nodes and edges in regions of interest in spatial networks, towards predicting the space and time requirements for range queries. The methods are evaluated by using real-life and synthetic data sets. Experimental results show that the number of nodes and edges can be estimated efficiently and accurately, with relatively small space requirements, thus providing useful information to the query optimizer.

论文关键词:Spatial networks,Selectivity estimation,Query optimization

论文评审过程:Received 24 March 2008, Revised 1 September 2008, Accepted 9 September 2008, Available online 5 November 2008.

论文官网地址:https://doi.org/10.1016/j.is.2008.09.004