Worst-Case Efficient Range Searching: Invited Tutorial 2

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearch

  • Department of Computer Science
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].
Original languageEnglish
Title of host publication28th Symposium on Principles of Database Systems : Proceedings
EditorsJan Paredaens, Jianwen Su
Number of pages2
PublisherAssociation for Computing Machinery
Publication year2009
ISBN (print)978-1-60558-553-6
Publication statusPublished - 2009
EventACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systemdatabase systems - Providence, Rhode Island, United States
Duration: 29 Jun 20091 Jul 2009
Conference number: 28


ConferenceACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systemdatabase systems
LandUnited States
ByProvidence, Rhode Island

    Research areas

  • Indexing, Range search, Algorithms

See relations at Aarhus University Citationformats

ID: 18162595