Efficient evaluation of continuous spatio-temporal queries on moving objects with uncertain velocity

Continuous Range (CR) query and Continuous K-Nearest Neighbor (CKNN) query are two important types of spatio-temporal queries. Given a time interval [t _s , t _e ] and a moving query object q, a CR query is to find the moving objects whose Euclidean distances to q are within a user-given distance at each time instant within [t _s , t _e ]. A CKNN query is to retrieve the K-Nearest Neighbors (KNNs) of this query object q at each time instant within [t _s , t _e ]. In this paper, we investigate how to process these spatio-temporal queries efficiently under the situation that the velocity of each object is not fixed. This uncertainty on the velocity of object inevitably results in high complexity in processing spatio-temporal queries. We will discuss the complications incurred by this uncertainty and propose two algorithms, namely the Possibility-based possible within objects searching algorithm and the Possibility-based possible KNN searching algorithm, for the CR query and the CKNN query, respectively. A Possibility-based model is designed accordingly to quantify the possibility of each object being the result of a CR query or a CKNN query. Comprehensive experiments are performed to demonstrate the effectiveness and the efficiency of the proposed approaches.     

Continuous K-Nearest Neighbor Query for Moving Objects with Uncertain Velocity

One of the most important queries in spatio-temporal databases that aim at managing moving objects efficiently is the continuous K-nearest neighbor (CKNN) query. A CKNN query is to retrieve the K-nearest neighbors (KNNs) of a moving user at each time instant within a user-given time interval [t _s , t _e ]. In this paper, we investigate how to process a CKNN query efficiently. Different from the previous related works, our work relieves the past assumption, that an object moves with a fixed velocity, by allowing that the velocity of the object can vary within a known range. Due to the introduction of this uncertainty on the velocity of each object, processing a CKNN query becomes much more complicated. We will discuss the complications incurred by this uncertainty and propose a cost-effective P² KNN algorithm to find the objects that could be the KNNs at each time instant within the given query time interval. Besides, a probability-based model is designed to quantify the possibility of each object being one of the KNNs. Comprehensive experiments demonstrate the efficiency and the effectiveness of the proposed approach.

Vague continuous K-nearest neighbor queries over moving objects with uncertain velocity in road networks

Recent research has focused on Continuous K Nearest Neighbor (CKNN) queries in road networks, where the queries and the data objects are moving. Most existing approaches assume the fixed velocity of moving objects. The release of fixed moving velocity makes the query process slowly due to the significant repetitive query cost. In this paper, we study CKNN queries over moving objects with uncertain velocity in road networks. A Distance Interval Model (DIM) is designed to calculate the minimal and maximal road network distances between moving objects and query point. Furthermore, we propose a novel Possibility-based Vague KNN (PVKNN) algorithm to process the query efficiently, which determines the CKNN query results with possibility within each division time subinterval of given time interval by applying the vague set theory. In the PVKNN algorithm, the query efficiency can be improved significantly with the pruning, distilling and possibility-ranking phases. With these phases, the objects candidates are scaled down and the given time interval is divided into subintervals to reduce the repetitive query cost. In addition, an index structure TPR^uv-Tree is designed to efficiently index moving objects with uncertain velocity in road network by involving edge connection and moving objects information. Experiments with simulation and comparison show that significant improvement in the performance of efficiency can be achieved with our proposed algorithms.     

Algorithms for constrained <Emphasis Type="Italic">k</Emphasis>-nearest neighbor queries over moving object trajectories

An important query for spatio-temporal databases is to find nearest trajectories of moving objects. Existing work on this topic focuses on the closest trajectories in the whole data space. In this paper, we introduce and solve constrained k-nearest neighbor (CkNN) queries and historical continuous CkNN (HCCkNN) queries on R-tree-like structures storing historical information about moving object trajectories. Given a trajectory set D, a query object (point or trajectory) q, a temporal extent T, and a constrained region CR, (i) a CkNN query over trajectories retrieves from D within T, the k (≥ 1) trajectories that lie closest to q and intersect (or are enclosed by) CR; and (ii) an HCCkNN query on trajectories retrieves the constrained k nearest neighbors (CkNNs) of q at any time instance of T. We propose a suite of algorithms for processing CkNN queries and HCCkNN queries respectively, with different properties and advantages. In particular, we thoroughly investigate two types of CkNN queries, i.e., CkNN_P and CkNN_T, which are defined with respect to stationary query points and moving query trajectories, respectively; and two types of HCCkNN queries, namely, HCCkNN_P and HCCkNN_T, which are continuous counterparts of CkNN_P and CkNN_T, respectively. Our methods utilize an existing data-partitioning index for trajectory data (i.e., TB-tree) to achieve low I/O and CPU cost. Extensive experiments with both real and synthetic datasets demonstrate the performance of the proposed algorithms in terms of efficiency and scalability.     

DART+: Direction-aware bichromatic reverse k nearest neighbor query processing in spatial databases

This article presents a novel type of queries in spatial databases, called the direction-aware bichromatic reverse k nearest neighbor(DBRkNN) queries, which extend the bichromatic reverse nearest neighbor queries. Given two disjoint sets, P and S, of spatial objects, and a query object q in S, the DBRkNN query returns a subset P′ of P such that k nearest neighbors of each object in P′ include q and each object in P′ has a direction toward q within a pre-defined distance. We formally define the DBRkNN query, and then propose an efficient algorithm, called DART, for processing the DBRkNN query. Our method utilizes a grid-based index to cluster the spatial objects, and the B⁺-tree to index the direction angle. We adopt a filter-refinement framework that is widely used in many algorithms for reverse nearest neighbor queries. In the filtering step, DART eliminates all the objects that are away from the query object more than a pre-defined distance, or have an invalid direction angle. In the refinement step, remaining objects are verified whether the query object is actually one of the k nearest neighbors of them. As a major extension of DART, we also present an improved algorithm, called DART+, for DBRkNN queries. From extensive experiments with several datasets, we show that DART outperforms an R-tree-based naive algorithm in both indexing time and query processing time. In addition, our extension algorithm, DART+, also shows significantly better performance than DART.     

面向移动对象连续k近邻查询的双层索引结构

移动对象连续k近邻（CKNN）查询是指给定一个连续移动的对象集合,对于任意一个k近邻查询q,实时计算查询q的k近邻并在查询有效时间内对查询结果进行实时更新.现实生活中,交通出行、社交网络、电子商务等领域许多基于位置的应用服务都涉及移动对象连续k近邻查询这一基础问题.已有研究工作解决连续k近邻查询问题时,大多需要通过多次迭代确定一个包含k近邻的查询范围,而每次迭代需要根据移动对象的位置计算当前查询范围内移动对象的数量,整个迭代过程的计算代价占查询代价的很大部分.为此,提出了一种基于网络索引和混合高斯函数移动对象分布密度的双重索引结构（grid GMM index,GGI）,并设计了移动对象连续k近邻增量查询算法（incremental search for continuous k nearest neighbors,IS-CKNN）.GGI索引结构的底层采用网格索引对海量移动对象进行维护,上层构建混合高斯模型模拟移动对象在二维空间中的分布.对于给定的k近邻查询q,IS-CKNN算法能够基于混合高斯模型直接确定一个包含q的k近邻的查询区域,减少了已有算法求解该区域的多次迭代过程;当移动对象和查询q位置发生变化时,进一步提出一种高效的增量查询策略,能够最大限度地利用已有查询结果减少当前查询的计算量.最后,在滴滴成都网约车数据集以及两个模拟数据集上进行大量实验,充分验证了算法的性能.     

Efficient mutual nearest neighbor query processing for moving object trajectories

Given a set D of trajectories, a query object q, and a query time extent Γ, a mutual (i.e., symmetric) nearest neighbor (MNN) query over trajectories finds from D, the set of trajectories that are among the k₁ nearest neighbors (NNs) of q within Γ, and meanwhile, have q as one of their k₂ NNs. This type of queries is useful in many applications such as decision making, data mining, and pattern recognition, as it considers both the proximity of the trajectories to q and the proximity of q to the trajectories. In this paper, we first formalize MNN search and identify its characteristics, and then develop several algorithms for processing MNN queries efficiently. In particular, we investigate two classes of MNN queries, i.e., MNN_P and MNN_T queries, which are defined with respect to stationary query points and moving query trajectories, respectively. Our methods utilize the batch processing and reusing technology to reduce the I/O cost (i.e., number of node/page accesses) and CPU time significantly. In addition, we extend our techniques to tackle historical continuous MNN (HCMNN) search for moving object trajectories, which returns the mutual nearest neighbors of q (for a specified k₁ and k₂) at any time instance of Γ. Extensive experiments with real and synthetic datasets demonstrate the performance of our proposed algorithms in terms of efficiency and scalability.     

Multiple <Emphasis Type="Italic">k</Emphasis> nearest neighbor search

The problem of kNN (k Nearest Neighbor) queries has received considerable attention in the database and information retrieval communities. Given a dataset D and a kNN query q, the k nearest neighbor algorithm finds the closest k data points to q. The applications of kNN queries are board, not only in spatio-temporal databases but also in many areas. For example, they can be used in multimedia databases, data mining, scientific databases and video retrieval. The past studies of kNN query processing did not consider the case that the server may receive multiple kNN queries at one time. Their algorithms process queries independently. Thus, the server will be busy with continuously reaccessing the database to obtain the data that have already been acquired. This results in wasting I/O costs and degrading the performance of the whole system. In this paper, we focus on this problem and propose an algorithm named COrrelated kNN query Evaluation (COKE). The main idea of COKE is an “information sharing” strategy whereby the server reuses the query results of previously executed queries for efficiently processing subsequent queries. We conduct a comprehensive set of experiments to analyze the performance of COKE and compare it with the Best-First Search (BFS) algorithm. Empirical studies indicate that COKE outperforms BFS, and achieves lower I/O costs and less running time.     

Spatial inverse query processing

Traditional spatial queries return, for a given query object q, all database objects that satisfy a given predicate, such as epsilon range and k-nearest neighbors. This paper defines and studies inverse spatial queries, which, given a subset of database objects Q and a query predicate, return all objects which, if used as query objects with the predicate, contain Q in their result. We first show a straightforward solution for answering inverse spatial queries for any query predicate. Then, we propose a filter-and-refinement framework that can be used to improve efficiency. We show how to apply this framework on a variety of inverse queries, using appropriate space pruning strategies. In particular, we propose solutions for inverse epsilon range queries, inverse k-nearest neighbor queries, and inverse skyline queries. Furthermore, we show how to relax the definition of inverse queries in order to ensure non-empty result sets. Our experiments show that our framework is significantly more efficient than naive approaches.     

Fault trees for clusters tolerating failure or disconnectedness of a single node

Given a K-nodes cluster (subnetwork) in an N-nodes network, the (Boolean) fault tree function for the connectedness of at least K − 1 intact nodes out of the above K nodes is determined. This function is primarily formulated as a function of mutually dependent variables, viz., the top event variables of various point-to-point connectivity (so-called s,t-) problems. The minimization of the number of s,t-problems involved will be a major concern. The main contribution of this paper is seen in the conceptual clarity of the approach, whereas the computational complexity for real life problems still needs improvements. (The analysis of the fault trees found, resulting in system unavailability, MTTF, etc., is not pursued here.) A preliminary version of this paper was reviewed for and presented at EWDC-7 (European Workshop on Dependable Computing 1995; without proceedings).     

Extending cubic uniform B-splines by unified trigonometric and hyperbolic basis

In this paper, the trigonometric basis {sin t, cos t, t, 1} and the hyperbolic basis {sinh t, cosh t, t, 1} are unified by a shape parameter C (0 ≤ C < ∝). It yields the Functional B-splines (FB-splines) and its corresponding Subdivision B-splines (SB-splines). As well, a geometric proof of curvature continuity for SB-splines is provided. FB-splines and SB-splines inherited nearly all properties of B-splines, including the C² continuity, and can represent elliptic and hyperbolic arcs exactly. They are adjustable, and each control point b_i can have its unique shape parameter C_i. As C_i increases from 0 to ∝, the corresponding breakpoint of b_i on the curve is moved to the location of b_i, and the curvature of this breakpoint is increased from 0 to ∝ too. For a set of control points and their shape parameters, SB-spline and FB-spline have the same position, tangent, and curvature on each breakpoint. If two adjacent control points in the set have identical parameters, their SB-spline and FB-spline segments overlap. However, in general cases, FB-splines have no simple subdivision equation, and SB-splines have no common evaluation function. Furthermore, FB-splines and SB-splines can generate shape adjustable surfaces. They can represent the quadric surfaces precisely for engineering applications. However, the exact proof of C² continuity for the general SB-spline surfaces has not been obtained yet.     

A study of nonlinear dispersive equations with solitary-wave solutions having compact support

With the use of Adomian decomposition method, the prototypical, genuinely nonlinear K(m,n) equation, u_t+(u^m)_x+(uⁿ)_xxx=0, which exhibits compactons — solitons with finite wavelength — is solved exactly. Two numerical illustrations, K(2,2) and K(3,3), are investigated to illustrate the pertinent features of the proposed scheme. The technique is presented in a general way so that it can be used in nonlinear dispersive equations.     

Blind evaluation of location based queries using space transformation to preserve location privacy

In this paper we propose a fundamental approach to perform the class of Range and Nearest Neighbor (NN) queries, the core class of spatial queries used in location-based services, without revealing any location information about the query in order to preserve users’ private location information. The idea behind our approach is to utilize the power of one-way transformations to map the space of all objects and queries to another space and resolve spatial queries blindly in the transformed space. Traditional encryption based techniques, solutions based on the theory of private information retrieval, or the recently proposed anonymity and cloaking based approaches cannot provide stringent privacy guarantees without incurring costly computation and/or communication overhead. In contrast, we propose efficient algorithms to evaluate KNN and range queries privately in the Hilbert transformed space. We also propose a dual curve query resolution technique which further reduces the costs of performing range and KNN queries using a single Hilbert curve. We experimentally evaluate the performance of our proposed range and KNN query processing techniques and verify the strong level of privacy achieved with acceptable computation and communication overhead.     

Structural stability and electronic property of C68X4 (X = H,F, and Cl) fullerene compounds

A systematic study on the geometrical structures and electronic properties of C₆₈X₄ (X = H, F, and Cl) fullerene compounds has been carried out on the basis of density functional theory. In all classical C₆₈X₄ isomers with two adjacent pentagons and one quasifullerene isomer [C_s:C₆₈(f)] containing a heptagon in the framework, the C_s:0064 isomers are most favorable in energy. The addition reaction energies of C₆₈X₄ (C_s:0064) are high exothermic, and C₆₈F₄ is more thermodynamically accessible. The C₆₈X₄ (C_s:0064) possess strong aromatic character, with nucleus independent chemical shifts ranging from −22.0 to −26.1 ppm. Further investigations on electronic properties indicate that C₆₈F₄ and C₆₈Cl₄ could be excellent electron-acceptors for potential photonic/photovoltaic applications in consequence of their large vertical electron affinities (3.29 and 3.15 eV, respectively). The Mulliken charge populations and partial density of states are also calculated, which show that decorating C₆₈ fullerene with various X atoms will cause remarkably different charge distributions in C₆₈X₄ (C_s:0064) and affect their electronic properties distinctly. Finally, the infrared spectra of the most stable C₆₈X₄ (C_s:0064) molecules are simulated to assist further experimental characterization.     

Curves of Genus 2 with (N,N) Decomposable Jacobians

Let C be a curve of genus 2 and ψ₁: C  −  → E ₁  a map of degree n, from C to an elliptic curveE₁ , both curves defined over C. This map induces a degree n map φ₁:P¹  −  → P ¹  which we call a Frey–Kani covering. We determine all possible ramifications for φ₁. If ψ₁:C  −  → E ₁  is maximal then there exists a maximal map ψ₂: C  −  → E ₂  , of degree n, to some elliptic curveE₂ such that there is an isogeny of degree n²from the JacobianJ_C to E₁ × E₂. We say thatJ_C is (n, n)-decomposable. If the degree n is odd the pair (ψ₂, E₂) is canonically determined. For n =  3, 5, and 7, we give arithmetic examples of curves whose Jacobians are (n, n)-decomposable.     

GPU accelerated tensor contractions in the plaquette renormalization scheme

We use the graphical processing unit (GPU) to accelerate the tensor contractions, which is the most time consuming operations in the variational method based on the plaquette renormalized states. Using a frustrated Heisenberg J₁–J₂ model on a square lattice as an example, we implement the algorithm based on the compute unified device architecture (CUDA). For a single plaquette contraction with the bond dimensions C = 3 of each rank of the tensor, results are obtained 25 times faster on GPU than on a current CPU core. This makes it possible to simulate systems with the size 8 × 8 and larger, which are extremely time consuming on a single CPU. This technology successfully relieves the computing time dependence with C, while in the CPU serial computation, the total required time scales both with C and the system size.     

Approximate Solutions of Polynomial Equations

In this paper, we introduce “approximate solutions" to solve the following problem: given a polynomial F(x, y) over Q, where x represents an n -tuple of variables, can we find all the polynomials G(x) such that F(x, G(x)) is identically equal to a constant c in Q ? We have the following: let F(x, y) be a polynomial over Q and the degree of y in F(x, y) be n. Either there is a unique polynomial g(x)  ∈ Q [ x ], with its constant term equal to 0, such that F(x, y)  = ∑_j = 0ⁿc_j(y − g(x))^jfor some rational numbers c_j, hence, F(x, g(x)  + a)  ∈ Q for all a ∈ Q, or there are at most t distinct polynomials g₁(x),⋯ , g_t(x), t ≤ n, such that F(x, g_i(x))  ∈ Q for 1  ≤ i ≤ t. Suppose that F(x, y) is a polynomial of two variables. The polynomial g(x) for the first case, or g₁(x),⋯ , g_t(x) for the second case, are approximate solutions of F(x, y), respectively. There is also a polynomial time algorithm to find all of these approximate solutions. We then use Kronecker’s substitution to solve the case of F(x, y).     

Top-n query processing in spatial databases considering bi-chromatic reverse k-nearest neighbors

A reverse k-nearest neighbor (RkNN) query retrieves the data points which regard the query point as one of their respective k nearest neighbors. A bi-chromatic reverse k-nearest neighbor (BRkNN) query is a variant of the RkNN query, considering two types of data. Given two types of data G and C, a BRkNN query regarding a data point q in G retrieves the data points from C that regard q as one of their respective k-nearest neighbors among the data points in G. Many existing approaches answer either the RkNN query or the BRkNN query. Different from these approaches, in this paper, we make the first attempt to propose a top-n query based on the concept of BRkNN queries, which ranks the data points in G and retrieves the top-n points according to the cardinalities of the corresponding BRkNN answer sets. For efficiently answering this top-n query, we construct the Voronoi Diagram of G to index the data points in G and C. From the information associated with the Voronoi Diagram of G, the upper bound of the cardinality of the BRkNN answer sets for each data point in G can be quickly computed. Moreover, based on an existing approach to answering the RkNN query and the characteristics of the Voronoi Diagram of G, we propose a method to find the candidate region regarding a BRkNN query, which tightens the corresponding search space. Finally, based on the triangle inequality, we propose an efficient refinement algorithm for finding the exact BRkNN answers from the candidate regions. To evaluate our approach on answering the top-n query, it is compared with an approach which applies a state-of-the-art algorithm for answering the BRkNN query to each data point in G. The experiment results reveal that our approach has a much better performance.     

Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data

In this paper, we consider an ordinal on-line scheduling problem. A sequence of n independent jobs has to be assigned non-preemptively to two uniformly related machines. We study two objectives which are maximizing the minimum machine completion time, and minimizing the l_p norm of the completion times. It is assumed that the values of the processing times of jobs are unknown at the time of assignment. However it is known in advance that the processing times of arriving jobs are sorted in a non-increasing order. We are asked to construct an assignment of all jobs to the machines at time zero, by utilizing only ordinal data rather than actual magnitudes of jobs. For the problem of maximizing the minimum completion time we first present a comprehensive lower bound on the competitive ratio, which is a piecewise function of machine speed ratio s. Then, we propose an algorithm which is optimal for any s ⩾ 1. For minimizing the l_p norm, we study the case of identical machines (s = 1) and present tight bounds as a function of p.     

Direction-aware KNN queries for moving objects in a road network

Recently more and more people focus on k-nearest neighbor (KNN) query processing over moving objects in road networks, e.g., taxi hailing and ride sharing. However, as far as we know, the existing k-nearest neighbor (KNN) queries take distance as the major criteria for nearest neighbor objects, even without taking direction into consideration. The main issue with existing methods is that moving objects change their locations and directions frequently over time, so the information updates cannot be processed in time and they run the risk of retrieving the incorrect KNN results. They may fail to meet users’ needs in certain scenarios, especially in the case of querying k-nearest neighbors for moving objects in a road network. In order to find the top k-nearest objects moving toward a query point, this paper presents a novel algorithm for direction-aware KNN (DAKNN) queries for moving objects in a road network. In this method, R-tree and simple grid are firstly used as the underlying index structure, where the R-tree is used for indexing the static road network and the simple grid is used for indexing the moving objects. Then, it introduces the notion of “azimuth” to represent the moving direction of objects in a road network, and presents a novel local network expansion method to quickly judge the direction of the moving objects. By considering whether a moving object is moving farther away from or getting closer to a query point, the object that is definitely not in the KNN result set is effectively excluded. Thus, we can reduce the communication cost, meanwhile simplify the computation of moving direction between moving objects and query point. Comprehensive experiments are conducted and the results show that our algorithm can achieve real-time and efficient queries in retrieving objects moving toward query point in a road network.