Search

Algorithms for answering the k nearest-neighbor (k-NN) query are widely used for queries in spatial databases and for distance classification of a group of query points against a reference dataset to derive the dominating feature class. GPU devices have significantly more processing cores than CPUs and faster device memory than the main memory accessed by CPUs, thus, providing higher computing power for processing demanding queries like the k-NN. However, since device and/or main memory may not be able to host an entire, rather big, reference and query datasets, storing these datasets in a fast secondary device, like a solid state disk (SSD), and partially retrieve the required, at each stage, partitions is, in many practical cases, a feasible solution. We propose and implement the first GPU-based algorithms for processing the k-NN query for big reference and query spatial data stored on SSDs. Based on 3d synthetic and real big spatial data, we experimentally compare these algorithms and highlight the most efficient algorithmic variation. This variation utilizes a CUDA feature known as Concurrent Kernel Execution, to further improve its performance. [ABSTRACT FROM AUTHOR]

Efficient processing of Distance-Based Join Queries (DBJQs) in spatial databases is of paramount importance in many application domains. The most representative and known DBJQs are the K Closest Pairs Query (KCPQ) and the ε Distance Join Query (εDJQ). These types of join queries are characterized by a number of desired pairs (K) or a distance threshold (ε) between the components of the pairs in the final result, over two spatial datasets. Both are expensive operations, since two spatial datasets are combined with additional constraints. Given the increasing volume of spatial data originating from multiple sources and stored in distributed servers, it is not always efficient to perform DBJQs on a centralized server. For this reason, this paper addresses the problem of computing DBJQs on big spatial datasets in SpatialHadoop, an extension of Hadoop that supports efficient processing of spatial queries in a cloud-based setting. We propose novel algorithms, based on plane-sweep, to perform efficient parallel DBJQs on large-scale spatial datasets in SpatialHadoop. We evaluate the performance of the proposed algorithms in several situations with large real-world as well as synthetic datasets. The experiments demonstrate the efficiency and scalability of our proposed methodologies. [ABSTRACT FROM AUTHOR]

Efficient and effective processing of the distance-based join query (DJQ) is of great importance in spatial databases due to the wide area of applications that may address such queries (mapping, urban planning, transportation planning, resource management, etc.). The most representative and studied DJQs are the K Closest Pairs Query ( KCPQ) and εDistance Join Query ( εDJQ). These spatial queries involve two spatial data sets and a distance function to measure the degree of closeness, along with a given number of pairs in the final result ( K) or a distance threshold ( ε). In this paper, we propose four new plane-sweep-based algorithms for KCPQs and their extensions for εDJQs in the context of spatial databases, without the use of an index for any of the two disk-resident data sets (since, building and using indexes is not always in favor of processing performance). They employ a combination of plane-sweep algorithms and space partitioning techniques to join the data sets. Finally, we present results of an extensive experimental study, that compares the efficiency and effectiveness of the proposed algorithms for KCPQs and εDJQs. This performance study, conducted on medium and big spatial data sets (real and synthetic) validates that the proposed plane-sweep-based algorithms are very promising in terms of both efficient and effective measures, when neither inputs are indexed. Moreover, the best of the new algorithms is experimentally compared to the best algorithm that is based on the R-tree (a widely accepted access method), for KCPQs and εDJQs, using the same data sets. This comparison shows that the new algorithms outperform R-tree based algorithms, in most cases. [ABSTRACT FROM AUTHOR]

Summary Corporate Reputation (CR) is a critical intangible asset for a firm. As a representation of its past actions and results, CR encompasses a number of features which conform the status of a firm regarding its competitors. This helps corporations not only to gain competitive advantages, but also to survive in times of economic turbulences. Despite its apparent relevance, it remains inconclusive and controversial whether CR affects firms’ financial performance, a key point for current and potential investors. Our aim is to provide new evidence that could shed some light in determining the role of CR in stock market valuation. Since most of the previous research focus on this relationship using Multiple Regression (MR), it has been suggested that more conclusive results could be achieved using neural networks, but it has not been proven yet to the best of our knowledge. Using a sample of Spanish listed companies in the period 2008–2011, MR and a neural network technique, Generalized Regression Neural Network (GRNN), have been used. At an empirical level, results show that the mere presence of a firm in a reputation ranking has a positive impact on its market value, and that also a higher CR have a favorable influence on financial performance. At a methodological level, results of GRNN have proven to be more robust than those obtained using traditional MR. [ABSTRACT FROM AUTHOR]

Our main objective was to analyse the different contributions of relational verbal reasoning (analogical and class inclusion) and executive functioning to metaphor comprehension across development. We postulated that both relational reasoning and executive functioning should predict individual and developmental differences. However, executive functioning would become increasingly involved when metaphor comprehension is highly demanding, either because of the metaphors’ high difficulty (relatively novel metaphors in the absence of a context) or because of the individual’s special processing difficulties, such as low levels of reading experience or low semantic knowledge. Three groups of participants, 11-year-olds, 15-year-olds and young adults, were assessed in different relational verbal reasoning tasks—analogical and class-inclusion—and in executive functioning tasks—updating information in working memory, inhibition, and shifting. The results revealed clear progress in metaphor comprehension between ages 11 and 15 and between ages 15 and 21. However, the importance of executive function in metaphor comprehension was evident by age 15 and was restricted to updating information in working memory and cognitive inhibition. Participants seemed to use two different strategies to interpret metaphors: relational verbal reasoning and executive functioning. This was clearly shown when comparing the performance of the "more efficient" participants in metaphor interpretation with that of the "less efficient” ones. Whereas in the first case none of the executive variables or those associated with relational verbal reasoning were significantly related to metaphor comprehension, in the latter case, both groups of variables had a clear predictor effect. [ABSTRACT FROM AUTHOR]

Abstract: The K-Closest-Pairs Query (K-CPQ), a type of distance join in spatial databases, discovers the K pairs of objects formed from two different datasets with the K smallest distances. Recently, branch-and-bound algorithms based on R-trees have been developed in order to answer K-CPQs efficiently. For query optimization purposes, analytical models are needed to estimate the processing cost of a specific query in order to evaluate alternative execution plans. In this paper, we combine techniques that have been used for the analysis of nearest neighbor and spatial join queries, and derive the performance cost (in terms of disk accesses) of K-CPQs using R-trees. Moreover, we present two interesting extensions of the cost model for K-CPQs, one exploiting the buffering management using R-trees and another for a second type of distance join, the so-called buffer queries. The proposed cost models are verified under a variety of distributions in 2-dimensional space on both synthetic and real datasets, shown to achieve accurate estimations of the measured experimental results. [Copyright &y& Elsevier]

Let a tuple of n objects obeying a query graph (QG) be called the n-tuple. The “D_distance-value” of this n-tuple is the value of a linear function of distances of the n objects that make up this n-tuple, according to the edges of the QG. This paper addresses the problem of finding the K n-tuples between n spatial datasets that have the smallest D_distance-values, the so-called K-multi-way distance join query (K-MWDJQ), where each set is indexed by an R-tree-based structure. This query can be viewed as an extension of K-closest-pairs query (K-CPQ) [8] for n inputs. In addition, a recursive non-incremental branch-and-bound algorithm following a depth-first search for processing synchronously all inputs without producing any intermediate result is proposed. Enhanced pruning techniques are also applied to n R-trees nodes in order to reduce the total response time and the number of distance computations of the query. Due to the exponential nature of the problem, we also propose a time-based approximate version of the recursive algorithm that combines approximation techniques to adjust the quality of the result and the global processing time. Finally, we give a detailed experimental study of the proposed algorithms using real spatial datasets, highlighting their performance and the quality of the approximate results. [ABSTRACT FROM AUTHOR]

The development of anthropic activities during recent years has led to an increase in nutrient fluxes in the Río Grande de Comitán and Montebello Lakes National Park, Mexico. In turn, this has modified the dynamics of the biotic community, specifically favoring the presence of cyanobacteria tolerant to contamination. The continual and massive presence of Planktothrix species (spp.) in the system suggests a potential detrimental impact for economic issues and human health. In this study, we identify the morphological and molecular characteristics of Planktothrix populations from seven tropical (1,380–1,740 masl, 23.0–25.5°C) and calcareous lakes and two ponds from a water treatment plant. We also assess the ecological drivers that could be related to the presence of cyanotoxins in the system. The ecological preferences, morphology, 16S rRNA structure, and 16S-23S rRNA internal transcribed spacer found evidence for three species: P. agardhii distributed in neutral to slightly basic water (pH = 7.7–8.7), and P. spiroides and Planktothrix sp. in alkaline waters (pH = 9.1). The presence of the mcyE gene and its validation by liquid chromatography confirmed the presence of two microcystin variants (MC-RR and MC-LR) in at least three populations of P. agardhii. These microcystins put the health of the ecosystem and its inhabitants at risk, a condition that should be addressed and resolved with a water management and detoxification strategy in the basin. [ABSTRACT FROM AUTHOR]

In this paper, we revisit level-dependent quasi-birth-death processes with finitely many possible values of the level and phase variables by complementing the work of Gaver, Jacobs, and Latouche (Adv. Appl. Probab. 1984), where the emphasis is upon obtaining numerical methods for evaluating stationary probabilities and moments of first-passage times to higher and lower levels. We provide a matrix-analytic scheme for numerically computing hitting probabilities, the number of upcrossings, sojourn time analysis, and the random area under the level trajectory. Our algorithmic solution is inspired from Gaussian elimination, which is applicable in all our descriptors since the underlying rate matrices have a block-structured form. Using the results obtained, numerical examples are given in the context of varicella-zoster virus infections. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the author discusses various reports within the issue on topics including a survey of retrial queueing systems, retrial queues in continuous-time, and an overview on single-server retrial queues in discrete-time.

We propose a stochastic model for the development of gastrointestinal nematode infection in growing lambs under the assumption that nonhomogeneous Poisson processes govern the acquisition of parasites, the parasite-induced host mortality, the natural (no parasite-induced) host mortality and the death of parasites within the host. By means of considering a number of age-dependent birth and death processes with killing, we analyse the impact of grazing strategies that are defined in terms of an intervention instant t 0 , which might imply a move of the host to safe pasture and/or anthelmintic treatment. The efficacy and cost of each grazing strategy are defined in terms of the transient probabilities of the underlying stochastic processes, which are computed by means of Strang–Marchuk splitting techniques. Our model, calibrated with empirical data from Uriarte et al and Nasreen et al., regarding the seasonal presence of nematodes on pasture in temperate zones and anthelmintic efficacy, supports the use of dose-and-move strategies in temperate zones during summer and provides stochastic criteria for selecting the exact optimum time instant t 0 when these strategies should be applied. [ABSTRACT FROM AUTHOR]

Nowadays, mashups applications are growing in popularity. They are accessible by cross-device applications, supporting multiple forms of interaction in cloud environments. In general, mashups manage a huge amount of heterogeneous data from different sources and handle different kinds of users. In this respect, mashup User Interfaces are becoming one of the most important pieces in many kinds of current management systems, such as for certain geographic or environmental information systems working on the Internet. In this type of systems, the user interface plays a particular role due to the huge variety of components or apps that the users need to manage at the same time. However, currently, there has been scant attention paid to the management of the user’s interaction with mashups interfaces. This goal involves the need of having important, well-constructed tools and methods conducting the data acquisition process for managing properly: (a) the interaction over the mashup user interfaces, at the front-end side; (b) the storage of the interaction in relational databases; and (c) well-supported microservices structures handled in the cloud. The fact of having valuable and flexible data acquisition processes encourages the deployment of others important issues of the interaction management, i.e., data searching, data mining, marketing, security, accessibility, usability or traceability of interaction data, among others. In this article, we present a flexible Data Acquisition System capable of capturing the human-computer interactions performed by users over mashup (User) Interfaces with the aim of storing them in a relational database. Firstly, the morphology of traditional mashup applications, their specifications and the relevant information that surrounds an interaction have been studied. Thereupon, a data acquisition system that stores user interaction on mashup based on such specifications was constructed. To achieve that purpose, an architecture of microservices was also designed in the cloud to detect, acquire, and collect the interactions performed over this kind of interfaces. The whole process is ready for acquiring internal data of the information system as well as context information and location awareness. To validate the data acquisition system, some tests on empirical case studies have been developed. Efficiency and effectiveness have also been determined by evaluating the performance of the acquisition system during different load tests. Finally, in order to ensure the software quality, a continuous integration strategy for software development and an easy management of the code have been used, facilitating the software maintenance alongside the microservice architecture, where functionalities are well encapsulated. [ABSTRACT FROM AUTHOR]

Indexing data on flash-based Solid State Drives (SSDs) is an important paradigm recently applied in spatial data management. During last years, the design of new spatial access methods for SSDs, named flash-aware spatial indices, has attracted the attention of many researchers, mainly to exploit the advantages of SSDs in spatial query processing. eFIND is a generic framework for transforming a disk-based spatial index into a flash-aware one, taking into account the intrinsic characteristics of SSDs. In this article, we present a systematic approach for porting disk-based data-driven and space-driven access methods to SSDs, through the eFIND framework. We also present the actual porting of representatives data-driven (R-trees, R*-trees, and Hilbert R-trees) and space-driven (xBR+-trees) access methods through this framework. Moreover, we present an extensive experimental evaluation that compares the performance of these ported indices when inserting and querying synthetic and real point datasets. The main conclusions of this experimental study are that the eFIND R-tree excels in insertions, the eFIND xBR+-tree is the fastest for different types of spatial queries, and the eFIND Hilbert R-tree is efficient for processing intersection range queries. [ABSTRACT FROM AUTHOR]

Let S be a set of n points in a fixed axis-parallel rectangle $R\subseteq \Re^{2}$, i.e. in the two-dimensional space (2D). Assuming that those points are stored in an R-tree, this paper presents several algorithms for finding the empty rectangle in R with the largest area, sides parallel to the axes of the space, and containing only a query point q. This point can not be part of S, that is, it is not stored in the R-tree. All algorithms follow the basic idea of discarding part of the points of S, in such a way that the problem can be solved only considering the remaining points. As a consequence, the algorithms only have to access a very small portion of the nodes (disk blocks) of the R-tree, saving main memory resources and computation time. We provide formal proofs of the correctness of our algorithms and, in order to evaluate the performance of the algorithms, we run an extensive set of experiments using synthetic and real data. The results have demonstrated the efficiency and scalability of our algorithms for different dataset configurations. [ABSTRACT FROM AUTHOR]

Aiming at the problem of spatial query processing in distributed computing systems, the design and implementation of new distributed spatial query algorithms is a current challenge. Apache Spark is a memory-based framework suitable for real-time and batch processing. Spark-based systems allow users to work on distributed in-memory data, without worrying about the data distribution mechanism and fault-tolerance. Given two datasets of points (called Query and Training), the group K nearest-neighbor (GKNN) query retrieves (K) points of the Training with the smallest sum of distances to every point of the Query. This spatial query has been actively studied in centralized environments and several performance improving techniques and pruning heuristics have been also proposed, while, a distributed algorithm in Apache Hadoop was recently proposed by our team. Since, in general, Apache Hadoop exhibits lower performance than Spark, in this paper, we present the first distributed GKNN query algorithm in Apache Spark and compare it against the one in Apache Hadoop. This algorithm incorporates programming features and facilities that are specific to Apache Spark. Moreover, techniques that improve performance and are applicable in Apache Spark are also incorporated. The results of an extensive set of experiments with real-world spatial datasets are presented, demonstrating that our Apache Spark GKNN solution, with its improvements, is efficient and a clear winner in comparison to processing this query in Apache Hadoop. [ABSTRACT FROM AUTHOR]