|
 ABSTRACT
In this tutorial we will describe some of the recent advances in the development of worst-case efficient range search indexing structures, that is, structures for storing a set of data points such that the points in a axis-parallel (hyper-) query rectangle can be found efficiently (with as few disk accesses - or I/Os - as possible). We first quickly discuss the well-known and optimal structure for the one-dimensional version of the problem, the B-tree [10, 12], along with its variants weight-balanced B-trees [9], multi-version (or persistent) B-trees [6, 11, 13, 22] and buffer-trees [4]. Then we discuss the external priority search tree [8], which solves a restricted version of the two-dimensional version of the problem where the query rectangle is unbounded on one side. This structure is then used in a range tree index structure [8, 21] that answers general two-dimensional queries in the same number of I/Os as the B-tree in the one-dimensional case, but using super-linear space. We also describe the linear space kdB-tree [19, 20] and O-tree [17] index structures that also solve the problem efficiently (but using more I/Os than the range tree). A detailed presentation of all the the above structures can be found in lecture notes by the author [5]. Finally, we also discuss lower bounds techniques, most notably the theory of indexability [16], that can be used to prove that both the range tree and kdB-tree/O-tree are optimal among query efficient and linear space structures, respectively [2, 8, 17], as well as recent index structures for higher-dimensional range search indexing [1]. We end by mentioning various R-tree variant [7, 18, 15] that can be used to solve the extended version of range search indexing where the queries as well as the data are (hyper-) rectangles. More comprehensive surveys of efficient index structures can be found in [3, 14, 23].
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
P. Afshani, L. Arge, and K.D. Larsen. Orthogonal range reporting in three and higher dimensions. Submitted, 2009.
|
 |
2
|
Pankaj K. Agarwal , Mark de Berg , Joachim Gudmundsson , Mikael Hammar , Herman J. Haverkort, Box-trees and R-trees with near-optimal query time, Proceedings of the seventeenth annual symposium on Computational geometry, p.124-133, June 2001, Medford, Massachusetts, United States
[doi> 10.1145/378583.378645]
|
| |
3
|
|
| |
4
|
L. Arge. The buffer tree: A technique for designing batched external data structures. Algorithmica, 37(1):1--24, 2003.
|
| |
5
|
L. Arge. External-memory geometric data structures. In G.S. Brodal and R. Fagerberg, editors, EEF Summer School on Massive Datasets. Springer Verlag, 2004.
|
| |
6
|
L. Arge, A. Danner, and S.-H. Teh. I/O-efficient point location using persistent B-trees. In Proc. Workshop on Algorithm Engineering and Experimentation, 2003.
|
| |
7
|
|
| |
8
|
Lars Arge , Vasilis Samoladas , Jeffrey Scott Vitter, On two-dimensional indexability and optimal range search indexing, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.346-357, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
[doi> 10.1145/303976.304010]
|
| |
9
|
|
| |
10
|
R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173--189, 1972.
|
| |
11
|
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
| |
15
|
|
| |
16
|
|
| |
17
|
|
| |
18
|
Y. Manolopoulos, A. Nanopoulos, A.N. Papadopoulos, and Y. Theodoridis. R-trees have grown everywhere. Technical report, Available at http://www.rtreeportal.org, 2003.
|
| |
19
|
O. Procopiuc, P.K. Agarwal, L. Arge, and J.S. Vitter. Bkd-tree: A dynamic scalable kd-tree. In Proc. International Symposium on Spatial and Temporal Databases, LNCS 2750, 2003.
|
| |
20
|
|
| |
21
|
|
| |
22
|
|
| |
23
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
A.1