A brand-new node-choosing algorithm in R-tree spatial index

Jun Gong; Shengnan Ke; Shuming Bao

doi:10.1117/12.760460

25 July 2007 A brand-new node-choosing algorithm in R-tree spatial index

Jun Gong, Shengnan Ke, Shuming Bao

Proceedings Volume 6753, Geoinformatics 2007: Geospatial Information Science; 675307 (2007) https://doi.org/10.1117/12.760460
Event: Geoinformatics 2007, 2007, Nanjing, China

Abstract

Spatial index is one of the key techniques in the field of spatial database. This paper presents a brand-new node-choosing algorithm in the insertion procedure of R-tree spatial index, which is very different from the current algorithms. From the beginning of the leaf-node layer, firstly from bottom to top then inversely, the proper leaf-node is chosen, and this scheme can solve the problems caused by node overlapping. Meantime, the concept of Rtree_Cauchy is firstly put forward, and the sum of overlay, overlap and Rtree_Cauchy is introduced as selection criterion to guarantee that shape of node is average and avoid generating long-strip-shape nodes. A comparative performance analysis on the current and improved methods shows that not only the query performance but also the generation performance of the improved method is higher than the current methods such as R*-tree.

Citation Download Citation

Jun Gong, Shengnan Ke, and Shuming Bao "A brand-new node-choosing algorithm in R-tree spatial index", Proc. SPIE 6753, Geoinformatics 2007: Geospatial Information Science, 675307 (25 July 2007); https://doi.org/10.1117/12.760460

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available