de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Hochschulschrift

Orthogonal Range Searching

MPG-Autoren

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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


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