Back to search

University of Patras

Αποτελεσματικοί αλγόριθμοι και βελτιωμένες τεχνικές αναζήτησης χωρικής, χρονικής και χώρο-χρονικής πληροφορίας

Abstract

dc:description

The subject of this dissertation is the invention of algorithmic techniques which assure efficient retrieval and searching (optimal or near optimal) of spatial, temporal and spatiotemporal data. Spatial data consist of points (we include either real numbers on the l-dimensional axis or d-dimensional vectors with d≥2), lines, rectangles, regions, surfaces and volumes. The representation of such data is becoming increasingly important in applications in computer graphics, computer vision, database management systems, computer-aided design, solid modeling, robotics, geographic information systems (GIS), image processing, computational geometry, pattern recognition, and other areas. We define as temporal data either the discrete time-stamps where some entities are being appeared on the time-intervals that represent the duration of its appearance. On the current dissertation the term "entity" is concerned with either a "process" in a Parallel or Distributed Environment or a multimedia object in a Database management system. Spatiotemporal data is the combination of spatial and temporal data, for example 3-dimensional moving objects. The second-chapter is concerned with the effective and efficient processing of spatiotemporal selection queries under varying degrees of approximation. Such queues may employ operations like overlaps north during, etc., and then result as a set of entities standing approximately in some spatiotemporal relation θ with respect to a query object X. The contribution of this chapter is twofold. 1) First we describe a mathematical framework for representing multidimensional relations at varying granularity levels, modelling relation approximation through the concept of relation convexity. 2) We subsequently exploit the framework to developing approximate spatiotemporal retrieval mechanisms, employing a set of existing as well as new main memory and secondary memory data structures that achieve either optimal or the best known performance in terms of time and space complexity, for both static and dynamic problems. Our new result studies the static 2D range query problem and an extension of the most well-known technique for static range queries of higher dimensions. At the end of this chapter, we describe the implementation of a real-time system which is based on the integration of GIS, GPS and GSM technologies. Incorporating efficient spatiotemporal algorithms within the GIS, the system's credibility has been increased. The third chapter is concerned with the problem of d-dimensional space searching (where d≥3) for two query types range and partial range geometric searching with Video Database Applications Let Ν be the number of points, s the number of keys specified m a partial match and partial range query and t the number of points retrieved. We present a structure that optimizes the best known time complexity for range queries O(t +logd°N) improving also the partial range query complexity from O(t + logd°2N) to 0(t +(d-s)+log'N). In particular we optimize the best known solution for three-sided range queries presented by Gabow, Bentley and Tarjan [ 60 ] which solve the problem in 0(N+M) space and O(t) time. The structure relies on the Cartesian Tree of Vuillemin [68] which in essence is a predecessor of the priority search tree. Their algorithm finds each point in the range by forming and answering an lca query [67]. This incurs a time overhead for each reported point. The algorithm for lowest common ancestors on arbitrary trees is also somewhat complicated. Here we present a modified priority search tree, which matches the performance of the structure of Gabow et al. [9] but the overall solution is simpler and faster. We also prove this by giving both theoretical and experimental evaluation. Based on this structure we present a d-dimensional data structure, which uses as its skeleton a Range tree, with its last level being replaced by our modified Priority Search tree. Thus we can achieve in a more simple and concrete way, O(t +logd2N) response time in d-dimensional range queries. Then observing a nice property of range trees we are able to perform partial range queries in O(t+(d-s)+log8N) time. We also use the above efficient geometric techniques in order to implement time and space efficient video content queries. Indexing video content is one of the most important problems in video databases. We present a simple optimal algorithm for this problem that answers certain content queries invoking video functions in linear time and space in terms of the number of the objects appearing in the video. To accomplish this, we make a straightforward reduction of this problem to the intersection problem in Computational Geometry. Our result is an improvement over the one of V S Subrahmaman [69] by a logarithmic factor in storage and is achieved by using different basic data structures. This logarithmic save is of great importance in video databases because vast space is needed to store videos and metadata for each video. Finally we present two time efficiently different approaches. We also compare the CPU times of some of our algorithms presenting experimental results. The used model is a unit cost RAM with word size w with each of the d keys having w-bits. In fourth chapter we refer to the Temporal Precedence Problem on Pine Pointer Machines. This problem asks for the design of a data structure, maintaining a set of stored elements and supporting the following two operations insert and precedes. The operation insert (a) introduces a new element a in the structure, while the operation precedes (a b) returns true if element a was inserted before element b temporally. In Ranjan et al. [104] a solution was provided to the problem with worst-case time complexity O(log logn) per operation and O(n log logn) space, where n is the number of elements inserted. It was also demonstrated that the precedes operation has a lower bound of Ω(log logn) for the Pure Pointer Machine model of computation. In this chapter we present two simple solutions with linear space and worst-case constant update time. The problem is important in two distinct ways. Firstly it is the first problem that clearly shows that the Pure Pointer Machine is a less powerful computational model than that of a Pointer Machine, since in a Pointer Machine the specific problem can be solved trivially (using time-stamps) with worst-case constant time for each operation, by using linear space. In [104] a non-constant lower bound on the precedes operation has been proved and as a consequence it was concluded that a Pointer Machine is a more powerful computational model than that of a Pure Pointer Machine. Secondly, the problem is related to a very concrete problem that arises in parallel implementation of logic programming languages. More specifically, in [102] a "tight" relationship between the And-Parallelism problem and the problem of "time stamping" on pointer machines was presented In the And-Parallelism problem, which arises from don't care non-determinism given a resolvent B1,B2, ,Bn multiple subgoals in the resolvent can be concurrently reduced. The computation can be visualized though a tree, the so called And-Tree, the root of which is labeled with the initial goal. If a node contains a conjunction B1,B2, ,Bn then it will have n children, the i-th child of the node is labeled with the body of the clause used to solve the Β. The main problem here is to find a way to efficiently manage the unifiers produced by the concurrent reduction of different subgoals. Two subgoals B1, B1 (l ≤ / ≤ / ≤ n) in the Β1 Bn resolvent should agree in the bindings of all the variables ("dependent" variables in terms of Prolog) that are common to them. In [102] it was shown how the problem of correct binding and assignment of variables in such parallel environments can be reduced to the problem of handling a dynamic tree, capable of growing and shrinking at the leaves and detecting whether the first node is the leftmost leaf in the subtree rooted at the second node. Both operations can be reduced (for more details see [102]) to the insert and precedes operations of the Temporal Precedence problem. The last chapter is concerned with the finger searching problem on a set oi 1-dimensional elements in RAM model of computation. We describe a new implicit tree structure based on Balls in Bins combinatorial games that support finger searching in O(loglogd) expected time with high probability for a large class of input distributions and insertions/deletions in O(1) worst-case update time. In the particular case we have insertions/deletions only at the end of a given set S of n elements, we present a simpler than eager partial rebuilding method of [115] matching the worst-case upper bound O(V(logd/loglogd)) of [115]. Also, in general case we have insertions/deletions anywhere we present the randomized version of [115] achieving the same time bounds with high probability.

Degree

thesis:*
Grantor dc:publisher
University of Patras
Year dc:date
2002

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Σιούτας, Σπυρίδων
  • Sioutas, Spyros

Subjects

dc:subject × 24

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/14364

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Σιούτας, Σπυρίδων; Sioutas, Spyros. Αποτελεσματικοί αλγόριθμοι και βελτιωμένες τεχνικές αναζήτησης χωρικής, χρονικής και χώρο-χρονικής πληροφορίας. University of Patras, 2002. http://hdl.handle.net/10442/hedi/14364