A Spatio-temporal Query Clustering Tree for Multiple Query Optimization
Multiple query optimization (MQO) is a critical research issue in the field of database. Reasonable methods for concurrent query processing are meaningful to service quality. Various solutions were proposed for spatial query processing, e.g. gridbased scheduling. However, little work has been done for temporal considerations, i.e. spatio-temporal query. The clustering based method, which aims to group M queries into N clusters so that they can be processed virtually as N queries (N≤M), is a representative approach for MQO. In terms of spatial considerations, this method makes sense since I/O counts can be reduced, which is the bottleneck for spatial processing. Lately, stream cube was proposed for multi dimensional online stream analytics (OLSA). It uses H-cubingto compute selected cuboids that users are interested and stores the precomputed cuboids along a specified popular path in an H-tree. Motivated by stream cube/H-tree and clustering based query optimizing methods, our work aim to apply MQO in data stream environment by constructing and maintaining a spatio-temporal query clustering tree (STQC-tree). The tree not only utilizes the geological information represented by grids, but also takes into account the query-related geometry information, e.g. point, line, polygon. In this thesis, we first examine the spatio-temporal query features and propose to organize these features in spatial cube. Then, the STQC-tree based multiple spatio-temporal query optimizing scheme is designed. Detailed data structure description and constructing algorithm of STQC-tree is given, and the STQCtree based clustering method is implemented. The performance study turns out that the STQC-tree based multiple query optimizing method outperforms the traditional grid-based multiple spatial query optimization. The idea of utilizing query features for query optimization extends the grid based method to a more deep and effective extent. Typically, it can be applied for on-line location based services, e.g. traffic navigation, where concurrent query answering is a must and can be a big issue for service quality improvement.
spatio-temporal query query clustering multiple query optimization STQC-tree
Xiang-Rui Chen Sung-Ha Baek Young-Hwan Oh Hae-Young Bae
Dept. of Computer Science and Information Engineering, Inha University, Incheon, South Korea Dept. of Information Science, Korea Nazarene University, Choongnam, South Korea
国际会议
重庆
英文
5-9
2010-04-22（万方平台首次上网日期，不代表论文的发表时间）