R*-tree - Revision history

2A02:587:186B:5300:6D64:F34B:9073:4A3D: Briefly described the heuristics introduced in R*

2024-04-01T22:03:03Z

Briefly described the heuristics introduced in R*

← Previous revision		Revision as of 22:03, 1 April 2024
Line 24:		Line 24:
	effect of producing more well-clustered groups of entries in nodes, reducing node coverage. Furthermore,		effect of producing more well-clustered groups of entries in nodes, reducing node coverage. Furthermore,
	actual node splits are often postponed, causing average node occupancy to rise. Re-insertion can be seen as a method of incremental tree optimization triggered on node overflow.		actual node splits are often postponed, causing average node occupancy to rise. Re-insertion can be seen as a method of incremental tree optimization triggered on node overflow.

			The R-tree describes three metrics by which the quality of a split can be quantified. These being overlap (common between R-trees and R-trees), defined as the intersection area of the bounding boxes of two clusters; Area-value, being the sum of the area of two cluster bounding boxes and Margin-value being the sum of the perimeters of two cluster bounding boxes.

	==Performance==		==Performance==

OpalYosutebito: cleaning up/removing nonexistent parameters across Wikipedia using AutoWikiBrowser

2023-12-30T23:53:38Z

cleaning up/removing nonexistent parameters across Wikipedia using AutoWikiBrowser

← Previous revision		Revision as of 23:53, 30 December 2023
Line 33:		Line 33:
	{{Gallery		{{Gallery
	\|title=Effect of different splitting heuristics on a database with Germany postal districts		\|title=Effect of different splitting heuristics on a database with Germany postal districts
		⚫	\|width=300 \| height=300 \| align=center \|File:Zipcodes-Germany-GuttmanRTree.svg\|R-Tree with Guttman quadratic split.<ref name="guttman">{{Cite book \| last1 = Guttman \| first1 = A. \| chapter = R-Trees: A Dynamic Index Structure for Spatial Searching\| doi = 10.1145/602259.602266 \| title = Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84 \| pages = 47 \| year = 1984 \| isbn = 0897911288 \| url = http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf}}</ref><br /> There are many pages that extend from east to west all over Germany, and pages overlap a lot. This is not beneficial for most applications, that often only need a small rectangular area that intersects with many slices.
	\|width=300 \| height=300 \| align=center \| lines=6
⚫	\|File:Zipcodes-Germany-GuttmanRTree.svg\|R-Tree with Guttman quadratic split.<ref name="guttman">{{Cite book \| last1 = Guttman \| first1 = A. \| chapter = R-Trees: A Dynamic Index Structure for Spatial Searching\| doi = 10.1145/602259.602266 \| title = Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84 \| pages = 47 \| year = 1984 \| isbn = 0897911288 \| url = http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf}}</ref><br /> There are many pages that extend from east to west all over Germany, and pages overlap a lot. This is not beneficial for most applications, that often only need a small rectangular area that intersects with many slices.
	\|File:Zipcodes-Germany-AngTanSplit.svg\|R-Tree with Ang-Tan linear split.<ref name="ang-tan">{{cite conference \| last1= Ang \| first1 = C. H. \| last2 = Tan \| first2 = T. C. \| editor1-first = Michel \| editor1-last = Scholl \| editor2-first = Agnès \| editor2-last = Voisard \| year = 1997 \| title = New linear node splitting algorithm for R-trees \| book-title = Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997 \| volume = 1262 \|series=Lecture Notes in Computer Science \| publisher=Springer \| pages = 337–349 \| doi = 10.1007/3-540-63238-7_38}}</ref><br /> While the slices do not extend as far as with Guttman, the slicing problem affects almost every leaf page. Leaf pages overlap little, but directory pages do.		\|File:Zipcodes-Germany-AngTanSplit.svg\|R-Tree with Ang-Tan linear split.<ref name="ang-tan">{{cite conference \| last1= Ang \| first1 = C. H. \| last2 = Tan \| first2 = T. C. \| editor1-first = Michel \| editor1-last = Scholl \| editor2-first = Agnès \| editor2-last = Voisard \| year = 1997 \| title = New linear node splitting algorithm for R-trees \| book-title = Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997 \| volume = 1262 \|series=Lecture Notes in Computer Science \| publisher=Springer \| pages = 337–349 \| doi = 10.1007/3-540-63238-7_38}}</ref><br /> While the slices do not extend as far as with Guttman, the slicing problem affects almost every leaf page. Leaf pages overlap little, but directory pages do.
	\|File:Zipcodes-Germany-RStarTree.svg\|R-tree topological split.<ref name="rstar" /><br /> The pages overlap very little since the R-tree tries to minimize page overlap, and the reinsertions further optimized the tree. The split strategy also does not prefer slices, so the resulting pages are much more useful for common map applications.		\|File:Zipcodes-Germany-RStarTree.svg\|R-tree topological split.<ref name="rstar" /><br /> The pages overlap very little since the R-tree tries to minimize page overlap, and the reinsertions further optimized the tree. The split strategy also does not prefer slices, so the resulting pages are much more useful for common map applications.
Line 53:		Line 52:

	==External links==		==External links==
	* {{commons ~~cat~~ inline}}		* {{commons category-inline}}

	{{CS trees}}		{{CS trees}}

Iljhgtn: Spelling/grammar/punctuation/typographical correction

2023-08-22T20:42:56Z

Spelling/grammar/punctuation/typographical correction

Jrf: Importing Wikidata short description: "A variant of R-trees used for indexing spatial information" (Shortdesc helper)

2022-05-14T09:31:03Z

Importing Wikidata short description: "A variant of R-trees used for indexing spatial information" (Shortdesc helper)

← Previous revision		Revision as of 09:31, 14 May 2022
Line 1:		Line 1:
			{{Short description\|A variant of R-trees used for indexing spatial information}}
	{{Infobox data structure		{{Infobox data structure
	\|name=R*-tree		\|name=R*-tree

WikiLinuz: Reverted edits by WikiLinuz (talk) to last version by Mwtoews

2022-03-11T09:09:19Z

Reverted edits by WikiLinuz (talk) to last version by Mwtoews

← Previous revision		Revision as of 09:09, 11 March 2022
Line 65:		Line 65:
	[[Category:R-tree]]		[[Category:R-tree]]
	[[Category:Database index techniques]]		[[Category:Database index techniques]]
	[[Category:Trees (data structures)]]
	[[Category:Data structures]]

	[[de:R-Baum]]		[[de:R-Baum]]

WikiLinuz: added Category:Data structures using HotCat

2022-03-11T01:49:29Z

added Category:Data structures using HotCat

← Previous revision		Revision as of 01:49, 11 March 2022
Line 66:		Line 66:
	[[Category:Database index techniques]]		[[Category:Database index techniques]]
	[[Category:Trees (data structures)]]		[[Category:Trees (data structures)]]
			[[Category:Data structures]]

	[[de:R-Baum]]		[[de:R-Baum]]

WikiLinuz: added Category:Trees (data structures) using HotCat

2022-03-11T01:49:19Z

added Category:Trees (data structures) using HotCat

← Previous revision		Revision as of 01:49, 11 March 2022
Line 65:		Line 65:
	[[Category:R-tree]]		[[Category:R-tree]]
	[[Category:Database index techniques]]		[[Category:Database index techniques]]
			[[Category:Trees (data structures)]]

	[[de:R-Baum]]		[[de:R-Baum]]

Mwtoews: consistency with R*-tree

2021-11-04T20:50:32Z

consistency with R*-tree

← Previous revision		Revision as of 20:50, 4 November 2021
Line 1:		Line 1:
	{{Infobox data structure		{{Infobox data structure
	\|name=R* tree		\|name=R*-tree
	\|invented_by=Norbert Beckmann, [[Hans-Peter Kriegel]], Ralf Schneider, and Bernhard Seeger		\|invented_by=Norbert Beckmann, [[Hans-Peter Kriegel]], Ralf Schneider, and Bernhard Seeger
	\|invented_year=1990		\|invented_year=1990
Line 40:		Line 40:
	\|File:Zipcodes-Germany-GuttmanRTree.svg\|R-Tree with Guttman quadratic split.<ref name="guttman">{{Cite book \| last1 = Guttman \| first1 = A. \| chapter = R-Trees: A Dynamic Index Structure for Spatial Searching\| doi = 10.1145/602259.602266 \| title = Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84 \| pages = 47 \| year = 1984 \| isbn = 0897911288 \| url = http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf}}</ref><br /> There are many pages that extend from east to west all over Germany, and pages overlap a lot. This is not beneficial for most applications, that often only need a small rectangular area that intersects with many slices.		\|File:Zipcodes-Germany-GuttmanRTree.svg\|R-Tree with Guttman quadratic split.<ref name="guttman">{{Cite book \| last1 = Guttman \| first1 = A. \| chapter = R-Trees: A Dynamic Index Structure for Spatial Searching\| doi = 10.1145/602259.602266 \| title = Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84 \| pages = 47 \| year = 1984 \| isbn = 0897911288 \| url = http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf}}</ref><br /> There are many pages that extend from east to west all over Germany, and pages overlap a lot. This is not beneficial for most applications, that often only need a small rectangular area that intersects with many slices.
	\|File:Zipcodes-Germany-AngTanSplit.svg\|R-Tree with Ang-Tan linear split.<ref name="ang-tan">{{cite conference \| last1= Ang \| first1 = C. H. \| last2 = Tan \| first2 = T. C. \| editor1-first = Michel \| editor1-last = Scholl \| editor2-first = Agnès \| editor2-last = Voisard \| year = 1997 \| title = New linear node splitting algorithm for R-trees \| book-title = Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997 \| volume = 1262 \|series=Lecture Notes in Computer Science \| publisher=Springer \| pages = 337–349 \| doi = 10.1007/3-540-63238-7_38}}</ref><br /> While the slices do not extend as far as with Guttman, the slicing problem affects almost every leaf page. Leaf pages overlap little, but directory pages do.		\|File:Zipcodes-Germany-AngTanSplit.svg\|R-Tree with Ang-Tan linear split.<ref name="ang-tan">{{cite conference \| last1= Ang \| first1 = C. H. \| last2 = Tan \| first2 = T. C. \| editor1-first = Michel \| editor1-last = Scholl \| editor2-first = Agnès \| editor2-last = Voisard \| year = 1997 \| title = New linear node splitting algorithm for R-trees \| book-title = Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997 \| volume = 1262 \|series=Lecture Notes in Computer Science \| publisher=Springer \| pages = 337–349 \| doi = 10.1007/3-540-63238-7_38}}</ref><br /> While the slices do not extend as far as with Guttman, the slicing problem affects almost every leaf page. Leaf pages overlap little, but directory pages do.
	\|File:Zipcodes-Germany-RStarTree.svg\|~~'''~~R* tree~~'''~~ topological split.<ref name="rstar" /><br /> The pages overlap very little since the R*-tree tries to minimize page overlap, and the reinsertions further optimized the tree. The split strategy also does not prefer slices, so the resulting pages are much more useful for common map applications.		\|File:Zipcodes-Germany-RStarTree.svg\|R-tree topological split.<ref name="rstar" /><br /> The pages overlap very little since the R-tree tries to minimize page overlap, and the reinsertions further optimized the tree. The split strategy also does not prefer slices, so the resulting pages are much more useful for common map applications.
	}}		}}

Mwtoews: Mwtoews moved page R* tree to R*-tree over redirect: Consistency with hyphenated form

2021-11-04T20:48:23Z

Mwtoews moved page R* tree to R*-tree over redirect: Consistency with hyphenated form

← Previous revision	Revision as of 20:48, 4 November 2021
(No difference)

Benbals: Updated PDF link for paper "The R*-tree: an efficient and robust access method for points and rectangles" as the old link was dead.

2021-06-09T16:29:55Z

Updated PDF link for paper "The R*-tree: an efficient and robust access method for points and rectangles" as the old link was dead.

← Previous revision		Revision as of 16:29, 9 June 2021
Line 11:		Line 11:

	In [[data processing]] '''R-trees''' are a variant of [[R-tree]]s used for indexing spatial information. R-trees have slightly higher construction cost than standard R-trees, as the data may need to be reinserted; but the resulting tree will usually have a better query performance. Like the standard R-tree, it can store both point and spatial data.		In [[data processing]] '''R-trees''' are a variant of [[R-tree]]s used for indexing spatial information. R-trees have slightly higher construction cost than standard R-trees, as the data may need to be reinserted; but the resulting tree will usually have a better query performance. Like the standard R-tree, it can store both point and spatial data.
	It was proposed by Norbert Beckmann, [[Hans-Peter Kriegel]], Ralf Schneider, and Bernhard Seeger in 1990.<ref name="rstar">{{Cite book \| last1 = Beckmann \| first1 = N. \| last2 = Kriegel \| first2 = H. P. \| author-link2 = Hans-Peter Kriegel\| last3 = Schneider \| first3 = R. \| last4 = Seeger \| first4 = B. \| chapter = The R*-tree: an efficient and robust access method for points and rectangles \| doi = 10.1145/93597.98741 \| title = Proceedings of the 1990 ACM SIGMOD international conference on Management of data - SIGMOD '90 \| pages = 322 \| year = 1990 \| isbn = 0897913655 \| url = ~~http~~://~~dbs~~.~~mathematik~~.~~uni-marburg.de~~/~~publications~~/~~myPapers~~/~~1990~~/~~BKSS90~~.pdf}}</ref>		It was proposed by Norbert Beckmann, [[Hans-Peter Kriegel]], Ralf Schneider, and Bernhard Seeger in 1990.<ref name="rstar">{{Cite book \| last1 = Beckmann \| first1 = N. \| last2 = Kriegel \| first2 = H. P. \| author-link2 = Hans-Peter Kriegel\| last3 = Schneider \| first3 = R. \| last4 = Seeger \| first4 = B. \| chapter = The R*-tree: an efficient and robust access method for points and rectangles \| doi = 10.1145/93597.98741 \| title = Proceedings of the 1990 ACM SIGMOD international conference on Management of data - SIGMOD '90 \| pages = 322 \| year = 1990 \| isbn = 0897913655 \| url = https://infolab.usc.edu/csci599/Fall2001/paper/rstar-tree.pdf}}</ref>

	==Difference between R*-trees and R-trees==		==Difference between R*-trees and R-trees==

← Previous revision		Revision as of 20:42, 22 August 2023
Line 11:		Line 11:
	}}		}}

	In [[data processing]] '''R-trees''' are a variant of [[R-tree]]s used for indexing spatial information. R-trees have slightly higher construction cost than standard R-trees, as the data may need to be reinserted; but the resulting tree will usually have a better query performance. Like the standard R-tree, it can store both point and spatial data.		In [[data processing]] '''R-trees''' are a variant of [[R-tree]]s used for indexing spatial information. R-trees have slightly higher construction cost than standard R-trees, as the data may need to be reinserted; but the resulting tree will usually have a better query performance. Like the standard R-tree, it can store both point and spatial data. It was proposed by Norbert Beckmann, [[Hans-Peter Kriegel]], Ralf Schneider, and Bernhard Seeger in 1990.<ref name="rstar">{{Cite book \| last1 = Beckmann \| first1 = N. \| last2 = Kriegel \| first2 = H. P. \| author-link2 = Hans-Peter Kriegel\| last3 = Schneider \| first3 = R. \| last4 = Seeger \| first4 = B. \| chapter = The R*-tree: an efficient and robust access method for points and rectangles \| doi = 10.1145/93597.98741 \| title = Proceedings of the 1990 ACM SIGMOD international conference on Management of data - SIGMOD '90 \| pages = 322 \| year = 1990 \| isbn = 0897913655 \| url = https://infolab.usc.edu/csci599/Fall2001/paper/rstar-tree.pdf}}</ref>
	It was proposed by Norbert Beckmann, [[Hans-Peter Kriegel]], Ralf Schneider, and Bernhard Seeger in 1990.<ref name="rstar">{{Cite book \| last1 = Beckmann \| first1 = N. \| last2 = Kriegel \| first2 = H. P. \| author-link2 = Hans-Peter Kriegel\| last3 = Schneider \| first3 = R. \| last4 = Seeger \| first4 = B. \| chapter = The R*-tree: an efficient and robust access method for points and rectangles \| doi = 10.1145/93597.98741 \| title = Proceedings of the 1990 ACM SIGMOD international conference on Management of data - SIGMOD '90 \| pages = 322 \| year = 1990 \| isbn = 0897913655 \| url = https://infolab.usc.edu/csci599/Fall2001/paper/rstar-tree.pdf}}</ref>

	==Difference between R*-trees and R-trees==		==Difference between R*-trees and R-trees==
	[[Image:RTree 2D.svg\|thumb\|350px\|R*-Tree built by repeated insertion (in [[Environment for DeveLoping KDD-Applications Supported by Index-Structures\|ELKI]]). There is little overlap in this tree, resulting in good query performance. Red and blue MBRs are index pages, green MBRs are leaf nodes.]]		[[Image:RTree 2D.svg\|thumb\|350px\|R*-Tree built by repeated insertion (in [[Environment for DeveLoping KDD-Applications Supported by Index-Structures\|ELKI]]). There is little overlap in this tree, resulting in good query performance. Red and blue MBRs are index pages, green MBRs are leaf nodes.]]
	Minimization of both coverage and overlap is crucial to the performance of R-trees. Overlap means that, on data query or insertion, more than one branch of the tree needs to be expanded (due to the way data is being split in regions which may overlap). A minimized coverage improves pruning performance, allowing exclusion of whole pages from search more often, in particular for negative range queries.		Minimization of both coverage and overlap is crucial to the performance of R-trees. Overlap means that, on data query or insertion, more than one branch of the tree needs to be expanded (due to the way data is being split in regions which may overlap). A minimized coverage improves pruning performance, allowing exclusion of whole pages from search more often, in particular for negative range queries. The R*-tree attempts to reduce both, using a combination of a revised node split algorithm and the concept of forced reinsertion at node overflow. This is based on the observation that R-tree structures are highly susceptible
	The R*-tree attempts to reduce both, using a combination of a revised node split algorithm and the concept of forced reinsertion
	at node overflow. This is based on the observation that R-tree structures are highly susceptible
	to the order in which their entries are inserted, so an insertion-built (rather than bulk-loaded) structure		to the order in which their entries are inserted, so an insertion-built (rather than bulk-loaded) structure
	is likely to be sub-optimal. Deletion and reinsertion of entries allows them to "find" a place in the tree		is likely to be sub-optimal. Deletion and reinsertion of entries allows them to "find" a place in the tree
	that may be more appropriate than their original location.		that may be more appropriate than their original location.

	When a node overflows, a portion of its entries are removed from the node and reinserted into the tree.		When a node overflows, a portion of its entries are removed from the node and reinserted into the tree. (In order to avoid an indefinite cascade of reinsertions caused by subsequent node overflow, the reinsertion
	(In order to avoid an indefinite cascade of reinsertions caused by subsequent node overflow, the reinsertion
	routine may be called only once in each level of the tree when inserting any one new entry.) This has the		routine may be called only once in each level of the tree when inserting any one new entry.) This has the
	effect of producing more well-clustered groups of entries in nodes, reducing node coverage. Furthermore,		effect of producing more well-clustered groups of entries in nodes, reducing node coverage. Furthermore,
	actual node splits are often postponed, causing average node occupancy to rise.		actual node splits are often postponed, causing average node occupancy to rise. Re-insertion can be seen as a method of incremental tree optimization triggered on node overflow.
	Re-insertion can be seen as a method of incremental tree optimization triggered on node overflow.

	==Performance==		==Performance==
	*Improved split heuristic produces pages that are more rectangular and thus better for many applications.		*Improved split heuristic produces pages that are more rectangular and thus better for many applications.
	*Reinsertion method optimizes the existing tree, but increases complexity.		*Reinsertion method optimizes the existing tree but increases complexity.
	*Efficiently supports point and spatial data at the same time.		*Efficiently supports point and spatial data at the same time.
	{{clear}}		{{clear}}
Line 50:		Line 45:
	* In addition to an improved split strategy, the R*-tree also tries to avoid splits by reinserting objects and subtrees into the tree, inspired by the concept of balancing a [[B-tree]].		* In addition to an improved split strategy, the R*-tree also tries to avoid splits by reinserting objects and subtrees into the tree, inspired by the concept of balancing a [[B-tree]].

	Worst case query and delete complexity are thus identical to the R-Tree. The insertion strategy to the R-tree is with <math>\mathcal{O}(M \log M)</math> more complex than the linear split strategy (<math>\mathcal{O}(M)</math>) of the R-tree, but less complex than the quadratic split strategy (<math>\mathcal{O}(M^2)</math>) for a page size of <math>M</math> objects and has little impact on the total complexity. The total insert complexity is still comparable to the R-tree: reinsertions affect at most one branch of the tree and thus <math>\mathcal{O}(\log n)</math> reinsertions, comparable to performing a split on a regular R-tree. So on overall, the complexity of the R-tree is the same as that of a regular R-tree.		Worst case query and delete complexity are thus identical to the R-Tree. The insertion strategy to the R-tree is with <math>\mathcal{O}(M \log M)</math> more complex than the linear split strategy (<math>\mathcal{O}(M)</math>) of the R-tree, but less complex than the quadratic split strategy (<math>\mathcal{O}(M^2)</math>) for a page size of <math>M</math> objects and has little impact on the total complexity. The total insert complexity is still comparable to the R-tree: reinsertions affect at most one branch of the tree and thus <math>\mathcal{O}(\log n)</math> reinsertions, comparable to performing a split on a regular R-tree. So, on overall, the complexity of the R-tree is the same as that of a regular R-tree.

	An implementation of the full algorithm must address many corner cases and tie situations not discussed here.		An implementation of the full algorithm must address many corner cases and tie situations not discussed here.