English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 DetailsSummary
  Orthogonal Range Searching

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

Item is

 

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/11858/00-001M-0000-0027-F85E-4
Genre: Thesis

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Tiwary, Hansraj1, Author
Seidel, Reimund2, Advisor
Affiliations:
1International Max Planck Research School, MPI for Informatics, Max Planck Society, Campus E1 4, 66123 Saarbrücken, DE, ou_1116551              
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: 20032003
 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