Global Center Point Splitting: New Linear Node Splitting Algorithm for R-Trees
We introduce a new linear algorithm to split overflowed nodes of an R-tree index called the Global Center Point Splitting (GCPS) algorithm. The proposed method is an enhancement of the Quadratic splitting algorithm proposed by Guttmann (Guttman A, 1984; 47–57). Most known algorithms do not take adva...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
An-Najah National University
2016-03-01
|
| Series: | مجلة جامعة النجاح للأبحاث العلوم الطبيعية |
| Subjects: | |
| Online Access: | https://journals.najah.edu/media/journals/full_texts/7_OYg3e58.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849684014964670464 |
|---|---|
| author | Manar Arafat |
| author_facet | Manar Arafat |
| author_sort | Manar Arafat |
| collection | DOAJ |
| description | We introduce a new linear algorithm to split overflowed nodes of an R-tree index called the Global Center Point Splitting (GCPS) algorithm. The proposed method is an enhancement of the Quadratic splitting algorithm proposed by Guttmann (Guttman A, 1984; 47–57). Most known algorithms do not take advantage of the fact that most spatial objects data is known beforehand, and these objects are relatively easy to identify. In this paper we have adopted an informative approach by making use of spatial information provided by the problem space. Objects in the problem space are scanned and the Global Center Point (GCP) that the objects are concentrated around is determined. The GCPS algorithm uses the proximity between the Global Center Point (GCP) and the remaining objects in selecting a splitting axis that produces the most even split. We conducted several experiments using both real and synthetic data sets. Results show that the proposed splitting method outperforms the quadratic version in terms of construction time especially for nodes with high capacity. The query performance approximately remains the same. |
| format | Article |
| id | doaj-art-c2c01f251a8a40eeba91da3c07cf1baf |
| institution | DOAJ |
| issn | 1727-2114 2311-8865 |
| language | English |
| publishDate | 2016-03-01 |
| publisher | An-Najah National University |
| record_format | Article |
| series | مجلة جامعة النجاح للأبحاث العلوم الطبيعية |
| spelling | doaj-art-c2c01f251a8a40eeba91da3c07cf1baf2025-08-20T03:23:35ZengAn-Najah National Universityمجلة جامعة النجاح للأبحاث العلوم الطبيعية1727-21142311-88652016-03-0130111112610.35552/anujr.a.30.1.1176Global Center Point Splitting: New Linear Node Splitting Algorithm for R-TreesManar Arafat0Department of Computer Science, Faculty of Engineering & Information Technology, An-Najah National University Nablus, PalestineWe introduce a new linear algorithm to split overflowed nodes of an R-tree index called the Global Center Point Splitting (GCPS) algorithm. The proposed method is an enhancement of the Quadratic splitting algorithm proposed by Guttmann (Guttman A, 1984; 47–57). Most known algorithms do not take advantage of the fact that most spatial objects data is known beforehand, and these objects are relatively easy to identify. In this paper we have adopted an informative approach by making use of spatial information provided by the problem space. Objects in the problem space are scanned and the Global Center Point (GCP) that the objects are concentrated around is determined. The GCPS algorithm uses the proximity between the Global Center Point (GCP) and the remaining objects in selecting a splitting axis that produces the most even split. We conducted several experiments using both real and synthetic data sets. Results show that the proposed splitting method outperforms the quadratic version in terms of construction time especially for nodes with high capacity. The query performance approximately remains the same.https://journals.najah.edu/media/journals/full_texts/7_OYg3e58.pdfr-tree indexquery performance.spatial databases |
| spellingShingle | Manar Arafat Global Center Point Splitting: New Linear Node Splitting Algorithm for R-Trees مجلة جامعة النجاح للأبحاث العلوم الطبيعية r-tree index query performance. spatial databases |
| title | Global Center Point Splitting: New Linear Node Splitting Algorithm for R-Trees |
| title_full | Global Center Point Splitting: New Linear Node Splitting Algorithm for R-Trees |
| title_fullStr | Global Center Point Splitting: New Linear Node Splitting Algorithm for R-Trees |
| title_full_unstemmed | Global Center Point Splitting: New Linear Node Splitting Algorithm for R-Trees |
| title_short | Global Center Point Splitting: New Linear Node Splitting Algorithm for R-Trees |
| title_sort | global center point splitting new linear node splitting algorithm for r trees |
| topic | r-tree index query performance. spatial databases |
| url | https://journals.najah.edu/media/journals/full_texts/7_OYg3e58.pdf |
| work_keys_str_mv | AT manararafat globalcenterpointsplittingnewlinearnodesplittingalgorithmforrtrees |