Advanced Data Structures for Set of Intervals
Explore tree structures like Interval Trees and Segment Trees designed by experts like Edelsbrunner, McCreight, and Bentley for efficient storage and retrieval of interval data sets. Learn about Orthogonal Range Trees and canonical interval decomposition for higher-dimensional tasks. Discover the power of tree-based data structures in organizing and querying intervals effectively.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Tree Structures for Set of Intervals ADVANCED DATA STRUCTURES RAJANI PINGILI
Tree Structures for Sets of Intervals: 2 Interval Trees Segment Trees Trees for the Union of Intervals Orthogonal Range Trees Higher-Dimensional Segment Trees kd-Trees
Interval Trees: Interval trees are invented by Edelsbrunner and McCreight. 3 The structure of interval tree stores a proper set of intervals. It returns the query key values for all of the intervals. A set of intervals stored in interval trees. Each interval contains a key node and it is associated with node.
Segment Trees: 4 Segment trees are invented by Bentley. It is a static data structure. The primary task performed by segment tree is the same as that done by an interval tree: keeping track of a set of n intervals, here assumed to be half-open, and listing for a given query key all the intervals It is based on the canonical interval decomposition is a framework on which number of more general tasks can be performed.
Segment Trees: 5 Theorem: The canonical interval decomposition is a representation of the interval as union of disjoint node intervals. Any search path for a value in the interval will go through exactly one node that belongs to the canonical interval decomposition. It is easy to construct the canonical interval decomposition.
Segment Trees: 1. Each time the node interval of the current node is entirely contained in [xi, xj [, we take that node into our representation and stop following that path down because all nodes below are redundant; 2. Each time the node interval of the current node partially overlaps [xi, xj [, we follow both paths down; 3. Each time the node interval of the current node is disjoint from [xi, xj [, we stop following that path down. 6
Orthogonal Range Trees: 8 Orthogonal range trees were independently discovered by Bentley, Lee and Wong, Lueker and Willard. Orthogonal range searching is more useful for database index structures. The main aim of the orthogonal range trees is that in order to solve the d- dimensional orthogonal range-searching problem, we build a balanced search tree for the key values that occur in the first coordinate of the data points. Orthogonal range trees can be applied to solve computational Geometry Problems
Orthogonal Range Trees: 9
kd-Trees: 10 The kd-tree is another structure that supports orthogonal range searching. It is quite popular in practical applications and conceptually easy to understand and implement; but it is unsatisfactory because its worst- case performance is much worse than orthogonal range trees. It is widely used in database structures. The application of kd-tree is Astronomy
kd-Trees: 11
References: 12 Advanced Data Structures, Peter Brass, 1st edition, Cambridge University Press https://camo.ici.ro/journal/vol11/v11c2.pdf http://adsabs.harvard.edu/full/2008ASPC..394..525G https://www2.cs.arizona.edu/classes/cs437/fall07/Lecture5.prn.pdf http://graphics.stanford.edu/courses/cs428-03-spring/03Talks/Range.pdf https://courses.csail.mit.edu/6.851/spring10/scribe/lec03.pdf https://www.researchgate.net/publication/260077217_Range_Tree_Applications _in_Computational_Geometry https://arxiv.org/abs/1811.01226 https://stackoverflow.com/questions/17466218/what-are-the-differences- between-segment-trees-interval-trees-binary-indexed-t/34699478
