JUCS - Journal of Universal Computer Science 10(9): 1325-1353, doi: 10.3217/jucs-010-09-1325
Geometric Retrieval for Grid Points in the RAM Model
Spyros Sioutas‡, Christos Makris‡, Nektarios Kitsios§, George Lagogiannis§, John Tsaknakis§, Kostas Tsichlas§, Bill Vassiliadis§‡ Computer Engineering and Informatics Department, University of Patras and Computer Technology Institute, Patras, Greece§ Department of Computer Engineering and Informatics, University of Patras, Greece
Corresponding author: Spyros Sioutas ( sioutas@ceid.upatras.gr ) © Spyros Sioutas, Christos Makris, Nektarios Kitsios, George Lagogiannis, John Tsaknakis, Kostas Tsichlas, Bill Vassiliadis. This article is freely available under the J.UCS Open Content License. Citation:
Sioutas S, Makris C, Kitsios N, Lagogiannis G, Tsaknakis J, Tsichlas K, Vassiliadis B (2004) Geometric Retrieval for Grid Points in the RAM Model. JUCS - Journal of Universal Computer Science 10(9): 1325-1353. https://doi.org/10.3217/jucs-010-09-1325 |  |
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
Multi-Dimensional Data Structures, Indexing, Spatial Data, Grid Model, File Systems