A Spatial Index Based on Clipping Bounding Box of Space Partitioning Tree
[1]XIONG Wei,LI Ruiqing,CHEN Luo,et al.A Spatial Index Based on Clipping Bounding Box of Space Partitioning Tree[J].Journal of Zhengzhou University (Engineering Science),2022,43(03):1-7.[doi:10.13705/j.issn.1671-6833.2022.03.016]
Copy
Journal of Zhengzhou University (Engineering Science)[ISSN
1671-6833/CN
41-1339/T] Volume:
43卷
Number of periods:
2022 03
Page number:
1-7
Column:
Public date:
2022-04-10
- Title:
- A Spatial Index Based on Clipping Bounding Box of Space Partitioning Tree
- CLC:
- TP392
- DOI:
- 10.13705/j.issn.1671-6833.2022.03.016
- Abstract:
- In spatial databases, spatio-temporal indexes based on R tree use minimum bounding box(MBB)to approximate spatio-temporal data to improve query efficiency, and the efficiency of indexing can be further improved by by clipping the bounding box.To address this problem, an improved spatio-temporal indexing method based on CBB was proposed, which firstly extended the method from two dimensions to the spatio-temporal dimension and obtained the possible clipping points by calculation, and recorded these points in the index for optimizing the clipping space of the bounding box of the index nodes, which could reduce the unnecessary child-node search in the query process.Then, the intersection of query box and the MBB of index node was analyzed, and the range query processing algorithm was further optimized, thus avoiding redundant comparison of clipping points in the query process.The experimental results showed that the indexing method could clip the space of the MBB of index nodes three times more than the original method, and could reduce the node computation by 40%, and could reduce the query time by 20%, which further could improve the query performance of spatial division tree-based spatio-temporal index.
- References:
-
[1] GUTTMAN A. R-trees: a dynamic index structure for spatial searching [ J] . Acm sigmod record, 1984, 14 (2) :47-57. [2] XU H, LIU N, TAI W P, et al. Range queries in spatial index research based on the spark[C]∥2017 2nd IEEE International Conference on Computational Intelligence and Applications. Piscataway:IEEE, 2017: 46-50.[3] XIAO J T, ZHANG Y C, JIA X H. Clustering nonuniform-sized spatial objects to reduce I / O cost for spatial-join processing [ J ] . The computer journal, 2001, 44(5) : 384-397.[4] JAGADISH H V. Spatial search with polyhedra[ C]∥ Proceedings of Sixth International Conference on Data Engineering of Piscataway:IEEE, 1990: 311-319.[5] DANKO O, SKOPAL T. Elliptic indexing of multidimensional databases[C]∥Proceedings of the Twentieth Australasian Conference on Australasian Database. Wellington: Australian Computer Society, 2009: 85 -94.[6] SIDLAUSKAS D, CHESTER S, ZACHARATOU E T, et al. Improving spatial data processing by clipping minimum bounding boxes[C]∥2018 IEEE 34th International Conference on Data Engineering. Piscataway: IEEE, 2018: 425-436.[7] LANGENDOEN K, GLASBERGEN B, DAUDJEE K. NIR-tree: a non-intersecting R-tree[C]∥33rd International Conference on Scientific and Statistical Database Management. New York: ACM, 2021: 157-168.[8] EVAGOROU G, HEINIS T. MAMBO-indexing dead space to accelerate spatial queries [ C]∥33rd International Conference on Scientific and Statistical Database Management. New York: ACM, 2021: 73-84.[9] MAHMOOD A R, PUNNI S, AREF W G. Spatiotemporal access methods: a survey ( 2010—2017 ) [ J] . GeoInformatica, 2019, 23(1) : 1-36.[10] SON W, STEHN F, KNAUER C, et al. Top-k manhattan spatial skyline queries[ J] . Information processing letters, 2017, 123: 27-35.[11] BECKMANN N, SEEGER B. A benchmark for multidimensional index structures[ EB / OL] . ( 2008 - 03 - 29) [ 2020 - 11 - 15] . http:∥www. mathematik. unimarburg. de / ~ seeger / rrstar / .
- Similar References:
Memo
-
Last Update:
2022-05-02