de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Thesis

Orthogonal Range Searching

MPS-Authors

Tiwary,  Hansraj
International Max Planck Research School, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

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


Cite as: http://hdl.handle.net/11858/00-001M-0000-0027-F85D-6
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.