Paper Info
Title
The Interval Skip List - A Data Structure For Finding All Intervals That Overlap A Point
Abstract
A problem that arises in computational geometry, pattern matching, and other applications is the need to quickly determine which of a collection of intervals overlap a query point. The interval binary search tree (IBS-tree) has been proposed as a solution to this problem. A recently discovered randomized data structure called the skip list provides functionality and performance similar to balanced binary trees (e.g., AVL-trees), but is much simpler to implement than balanced trees. This paper introduces an extension of the skip list called the interval skip list, or IS-list, to support interval indexing. IS-lists remain dynamicly balanced, and show similar performance to IBS-trees, but can be implemented in about one-fourth as much high-level language code. Searching an IS-list containing n intervals to find intervals overlapping a point takes expected time O(log n + L) where L is the number of matching intervals. Inserting or deleting an interval takes expected time O(log2 n).
Year
DOI
Venue
1991
10.1007/BFb0028258
LECTURE NOTES IN COMPUTER SCIENCE
Keywords
Field
DocType
binary tree,data structure,pattern matching,high level language,indexation,computational geometry,skip list,binary search tree
Discrete mathematics,Range tree,Combinatorics,Linked list,Computer science,Skip list,Random binary tree,Segment tree,Linear search,Binary search tree,Interval tree
Conference
Volume
ISSN
Citations 
519
0302-9743
20
PageRank 
References 
Authors
4.55
6
1
Name
Order
Citations
PageRank
Eric N. Hanson1917376.11