Orthogonal Range Searching

Tiwary, Hans Raj

Local TagsRelease HistoryDetailsSummary

Orthogonal Range Searching

Tiwary, H. R. (2003). Orthogonal Range Searching. Master Thesis, Universität des Saarlandes, Saarbrücken.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-F85D-6 Version Permalink: https://hdl.handle.net/21.11116/0000-0003-0137-E

Genre: Thesis

Files

show Files

Locators

show

Creators

show

hide

Creators:
Tiwary, Hans Raj¹, Author
Seidel, Reimund², Advisor

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019
2External Organizations, ou_persistent22

Content

show

hide

Free keywords: -

Abstract: Orthogonal range searches arise in many areas of application, most often, in
database queries. Many techniques have been developed for this problem and
related geometric search problems where the points are replaced by general
objects like simplices, discs etc. This report is a brief study of some of the
techniques developed and how they can be plugged together to give various
solutions for this problem. The motivation for this study was to find a general
method to solve this problem in time O(log n) and space O (npolylog n) where
the dependency on the dimension affects only the constant in the query time and
the polylogarithmic factor in the space complexity. The study hasn't led to any
such algorithm so far but it helps us to see the common thread in some of the
structures and tools available in the study of algorithms. Interestingly, some
of these structures and tools were proposed for quite other purposes than
answering Orthogonal Range Queries. A small part of the thesis also deals with
Dominance Queries because of their close relation to the Orthogonal Range
Queries in terms of both problem definition and solution.

Details

show

hide

Language(s): eng - English

Dates: Accepted: 2003Date issued: 2003

Publication Status: Issued

Pages: -

Publishing info: Saarbrücken : Universität des Saarlandes

Table of Contents: -

Rev. Type: -

Identifiers: BibTex Citekey: Tiwary2003

Degree: Master

Event

show

Legal Case

show

Project information

show

Source

show