Geometric Retrieval for Grid Points in the RAM Model

Spyros Sioutas (Department of Computer Engineering and Informatics, University of Patras, Greece)

Christos Makris (Department of Computer Engineering and Informatics, University of Patras, Greece)

Nektarios Kitsios (Department of Computer Engineering and Informatics, University of Patras, Greece)

George Lagogiannis (Department of Computer Engineering and Informatics, University of Patras, Greece)

John Tsaknakis (Department of Computer Engineering and Informatics, University of Patras, Greece)

Kostas Tsichlas (Department of Computer Engineering and Informatics, University of Patras, Greece)

Bill Vassiliadis (Department of Computer Engineering and Informatics, University of Patras, Greece)

Abstract: We consider the problem of d-dimensional searching (d 3) for four query types: range, partial range, exact match and partial match searching. Let N be the number of points, s be the number of keys specified in a partial match and partial range query and t be the number of points retrieved. We present a data structure with worst case time complexities O(t + logd-2 N), O(t + (d - s) + logs N), O(d + ) and O(t + (d - s) + s ) for each of the aforementioned query types respectively. We also present a second, more concrete solution for exact and partial match queries, which achieves the same query time but has different space requirements. The proposed data structures are considered in the RAM model of computation.

Keywords: File Systems, Grid Model, Indexing, Multi-Dimensional Data Structures, Spatial Data

Categories: E.1, E.5