Resultados de búsqueda para query processing

Given a set S of points in the two-dimensional space, which are stored in a spatial database, this work presents an efficient algorithm to find the empty circle, in the area delimited by those points, with thelargest area and containing only a query point q.Our algorithm adapts previous work in the field of computational geometry to be used in spatial databases, which require to manage large amounts of data. To achieve this objective, the basic idea is to discard a large part of the points of $S$, in such a way that the problem can be solved providing only the remaining points to a classical computational geometry algorithm that, by processing a smaller collection of points, saves main memory resources and computation time.The correctness of our algorithm is formally proven. In addition, we empirically show its efficiency and scalability by running a set of experiments using both synthetic and real data.

Due to the ubiquitous use of spatial data applications and the large amounts of spatial data that these applications generate, the processing of large-scale queries in distributed systems is becoming increasingly popular. Complex spatial systems are very often organized under the form of Spatial Networks, a type of graph where nodes and edges are embedded in space. Examples of these spatial networks are transportation and mobility networks, mobile phone networks, social and contact networks, etc. When these spatial networks are big enough that exceed the capacity of commonly-used spatial computing technologies, we have Big Spatial Networks, and to manage them is necessary the use of distributed graph-parallel systems. In this paper, we describe our emerging work concerning the design of new storage methods and query processing algorithms over big spatial networks in scalable and distributed systems, which is a very active research area in the past years.

Processing of spatial queries has been studied extensively in the literature. In most cases, it is accomplished by indexing spatial data using spatial access methods. Spatial indexes, such as those based on the Quadtree, are important in spatial databases for efficient execution of queries involving spatial constraints and objects. In this paper, we study a recent balanced disk-based index structure for point data, called xBR+-tree, that belongs to the Quadtree family and hierarchically decomposes space in a regular manner. For the most common spatial queries, like Point Location, Window, Distance Range, Nearest Neighbor and Distance-based Join, the R-tree family is a very popular choice of spatial index, due to its excellent query performance. For this reason, we compare the performance of the xBR+-tree with respect to the R?-tree and the R+-tree for tree building and processing the most studied spatial queries. To perform this comparison, we utilize existing algorithms and present new ones. We demonstrate through extensive experimental performance results (I/O efficiency and execution time), based on medium and large real and synthetic datasets, that the xBR+-tree is a big winner in execution time in all cases and a winner in I/O in most cases.

In the last years, and thanks to improvements on computing and communications technologies, wireless networks formed by vehicles (called vehicular networks) have emerged as a key topic of interest. In these networks, the vehicles can exchange data by using short-range radio signals in order to get useful information related to traffic conditions, road safety, and other aspects. The availability of different types of sensors can be exploited by the vehicles to measure many parameters from their surroundings. These data can then be shared with other drivers who, on the other side, could also explicitly submit queries to retrieve information available in the network. This can be a challenging task, since the data is scattered among the vehicles belonging to the network and the communication links among them have usually a short life due to their constant movement. In this paper, we use mobile agent technology to help to accomplish these tasks, since mobile agents have a number of features that are very well suited for mobile environments, such as autonomy, mobility, and intelligence. Specifically, we analyze the benefits that mobile agents can bring to vehicular networks and the potential difficulties for their adoption. Moreover, we describe a query processing approach based on the use of mobile agents. We focus on range queries that retrieve interesting information from the vehicles located within a geographic area, and perform an extensive experimental evaluation that shows the feasibility and the interest of the proposal.