A Time-Optimal Multiple Search Algorithm on Enhanced Meshes,with Applications

Given a sorted sequence A = a₁, a₂, ..., a_n of items from a totally ordered universe, along with an arbitrary sequence Q = q₁, q₂, ..., q_m (1 ≤ m ≤ n) of queries, the multiple search problem involves computing for every q_j (1 ≤ j ≤ m) the unique a_i for which a_i−1 ≤ q_j < a_i. In this paper we propose a time-optimal algorithm to solve the multiple search problem on meshes with multiple broadcasting. More specifically, on a [formula] × [formula] mesh with multiple broadcasting, our algorithm runs in [formula] time which is shown to be time-optimal. We also present some surprising applications of the multiple search algorithm to computer graphics, image processing, robotics, and computational geometry.     

Lower Bounds on Performance of Metric Tree Indexing Schemes for Exact Similarity Search in High Dimensions

Within a mathematically rigorous model, we analyse the curse of dimensionality for deterministic exact similarity search in the context of popular indexing schemes: metric trees. The datasets X are sampled randomly from a domain Ω, equipped with a distance, ρ, and an underlying probability distribution, μ. While performing an asymptotic analysis, we send the intrinsic dimension d of Ω to infinity, and assume that the size of a dataset, n, grows superpolynomially yet subexponentially in d. Exact similarity search refers to finding the nearest neighbour in the dataset X to a query point ω∈Ω, where the query points are subject to the same probability distribution μ as datapoints. Let denote a class of all 1-Lipschitz functions on Ω that can be used as decision functions in constructing a hierarchical metric tree indexing scheme. Suppose the VC dimension of the class of all sets {ω:f(ω)≥a}, a∈? is o(n ^1/4/log² n). (In view of a 1995 result of Goldberg and Jerrum, even a stronger complexity assumption d ^O(1) is reasonable.) We deduce the Ω(n ^1/4) lower bound on the expected average case performance of hierarchical metric-tree based indexing schemes for exact similarity search in (Ω,X). In paricular, this bound is superpolynomial in d.     

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.     

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.     

Geometric complexity of some location problems

Given a set ofn demand points with weightW _i ,i = 1,2,...,n, in the plane, we consider several geometric facility location problems. Specifically we study the complexity of the Euclidean 1-line center problem, discrete 1-point center problem and a competitive location problem. The Euclidean 1-line center problem is to locate a line which minimizes the maximum weighted distance from the line (or the center) to the demand points. The discrete 1-point center problem is to locate one of the demand points so as to minimize the maximum unweighted distance from the point to other demand points. The competitive location problem studied is to locate a new facility point to compete against an existing facility so that a certain objective function is optimized. An Ω(n logn) lower bound is proved for these problems under appropriate models of computation. Efficient algorithms for these problems that achieve the lower bound and other related problems are also given.     

Quasi-optimal upper bounds for simplex range searching and new zone theorems

This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a setP ofn points in ?^d so that, given any query simplexq, the points inP ∩q can be counted or reported efficiently. Ifm units of storage are available (n <m <n ^d ), then we show that it is possible to answer any query inO(n ^1+?/m ^1/d ) query time afterO(m ^1+?) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieveO(logn) query time at the expense ofO(n ^d+?) storage for any fixed ? > 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.     

数据仓库系统中层次式Cube存储结构

区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(log^dn),综合性能为O((logn)^2d)(使用C_qC_u模型)或O(K(logn)^d)(使用C_qn_q+C_un_u模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构.     

Reverse Furthest Neighbors Query in Road Networks

Given a road network G = (V,E), where V (E) denotes the set of vertices(edges) in G, a set of points of interest P and a query point q residing in G, the reverse furthest neighbors (Rfn _R ) query in road networks fetches a set of points p ∈ P that take q as their furthest neighbor compared with all points in P ∪ {q}. This is the monochromatic Rfn _R (Mrfn _R ) query. Another interesting version of Rfn _R query is the bichromatic reverse furthest neighbor (Brfn _R ) query. Given two sets of points P and Q, and a query point q ∈ Q, a Brfn _R query fetches a set of points p ∈ P that take q as their furthest neighbor compared with all points in Q. This paper presents efficient algorithms for both Mrfn _R and Brfn _R queries, which utilize landmarks and partitioning-based techniques. Experiments on real datasets confirm the efficiency and scalability of proposed algorithms.     

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.     

A new fast heuristic for labeling points

In the point site labeling problem, we are given a set P={p₁,p₂,…,pn} of point sites in the plane. The label of a point pi is an axis-parallel rectangle of specified size. The objective is to label the maximum number of points on the map so that the placed labels are mutually non-overlapping. Here, we investigate a special class of the point site labeling problem where (i) height of the labels of all the points are same but their lengths may differ, (ii) the label of a point pi touches the point at one of its four corners, and (iii) the label of one point does not obscure any other point in P. We describe an efficient heuristic algorithm for this problem which runs in time in the worst case. We run our algorithm as well as the algorithm Rules proposed by Wagner et al. on randomly generated point sets and on the available benchmarks. The results produced by our algorithm are almost the same as Rules in most of the cases. But our algorithm is faster than Rules in dense instance. We have also computed the optimum solutions for all the examples we have considered by designing an algorithm, which performs an exhaustive search in the worst case. We found that the exhaustive search algorithm runs reasonably fast for most of the examples we have considered.     

Learning context-sensitive similarity by shortest path propagation

In this paper, we introduce a novel shape/object retrieval algorithm shortest path propagation (SSP). Given a query object q and a target database object p, we explicitly find the shortest path between them in the distance manifold of the database objects. Then a new distance measure between q and p is learned based on the database objects on the shortest path to replace the original distance measure. The promising results on both MEPG-7 shape dataset and a protein dataset demonstrate that our method can significantly improve the ranking of the object retrieval.     

Small Space Representations for Metric Min-sum k-Clustering and Their Applications

The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ?P such that $\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q)The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ⊆P such that ?_i=1^k?_{p,q ? Ci}d(p,q)\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q) is minimized. We show the first efficient construction of a coreset for this problem. Our coreset construction is based on a new adaptive sampling algorithm. With our construction of coresets we obtain two main algorithmic results.     

Fast computation of smallest enclosing circle with center on a query line segment

Here we propose an efficient algorithm for computing the smallest enclosing circle whose center is constrained to lie on a query line segment. Our algorithm preprocesses a given set of n points P={p₁,p₂,…,pn} such that for any query line or line segment L, it efficiently locates a point c on L that minimizes the maximum distance among the points in P from c. Roy et al. [S. Roy, A. Karmakar, S. Das, S.C. Nandy, Constrained minimum enclosing circle with center on a query line segment, in: Proc. of the 31st Mathematical Foundation of Computer Science, 2006, pp. 765-776] have proposed an algorithm that solves the query problem in O(log²n) time using O(nlogn) preprocessing time and O(n) space. Our algorithm improves the query time to O(logn); but the preprocessing time and space complexities are both O(n²).     

Fast exact k nearest neighbors search using an orthogonal search tree

The problem of k nearest neighbors (kNN) is to find the nearest k neighbors for a query point from a given data set. In this paper, a novel fast kNN search method using an orthogonal search tree is proposed. The proposed method creates an orthogonal search tree for a data set using an orthonormal basis evaluated from the data set. To find the kNN for a query point from the data set, projection values of the query point onto orthogonal vectors in the orthonormal basis and a node elimination inequality are applied for pruning unlikely nodes. For a node, which cannot be deleted, a point elimination inequality is further used to reject impossible data points. Experimental results show that the proposed method has good performance on finding kNN for query points and always requires less computation time than available kNN search algorithms, especially for a data set with a big number of data points or a large standard deviation.     

A simple approach to the problem of 3-D reconstruction

A relatively simple mathematical procedure for the reconstruction of the 3-dimensional (3D) image of the left ventricle (LV) of the heart is presented. The method is based on the assumption that every ray whoch emanates from the midpoint of the long axis of the 3D body crosses the surface boundary of the ventricle at one and only one point. The coordinates r_i, φ_i, θ_i of the data points on, say, the outer boundary, (i.e., the epicardium) are calculated in a spherical coordinate system having its origin in the midpoint of the long axis. The problem of defining the coordinates of a prescribed grid point on the boundary is treated as an interpolation problem for the function r = r(φ, θ), defined in the rectangle 0 ≤ φ ≤ 2π; 0 ≤ θ ≤ π with r_i given in the points (φ_i, θ_i).     

Efficient image retrieval through vantage objects

We describe a new indexing structure for general image retrieval that relies solely on a distance function giving the similarity between two images. For each image object in the database, its distance to a set of m predetermined vantage objects is calculated; the m-vector of these distances specifies a point in the m-dimensional vantage space. The database objects that are similar (in terms of the distance function) to a given query object can be determined by means of an efficient nearest-neighbor search on these points. We demonstrate the viability of our approach through experimental results obtained with two image databases, one consisting of about 5200 raster images of stamps, the other containing about 72,000 hieroglyphic polylines.     

The region approach for computing relative neighbourhood graphs in the Lp metric

The following geometrical proximity concepts are discussed: relative closeness and geographic closeness. Consider a setV={v ₁,v ₂, ...,v _n } of distinct points in atwo-dimensional space. The pointv _j is said to be arelative neighbour ofv _i ifd _p (v _i ,v _j )≤max{d _p (v _j ,v _k ),d _p (v _j ,v _k )} for allv _k ∈V, whered _p denotes the distance in theL _p metric, 1≤p≤∞. After dividing the space around the pointv _i into eight sectors (regions) of equal size, a closest point tov _i in some region is called anoctant (region, orgeographic) neighbour ofv _i. For anyL _p metric, a relative neighbour ofv _i is always an octant neighbour in some region atv _i. This gives a direct method for computing all relative neighbours, i.e. for establishing therelative neighbourhood graph ofV. For every pointv _i ofV, first search for the octant neighbours ofv _i in each region, and then for each octant neighbourv _j found check whether the pointv _j is also a relative neighbour ofv _i. In theL _p metric, 1<p<∞, the total number of octant neighbours is shown to be θ(n) for any set ofn points; hence, even a straightforward implementation of the above method runs in θn ²) time. In theL ₁ andL _∞ metrics the method can be refined to a θ(n logn+m) algorithm, wherem is the number of relative neighbours in the output,n-1≤m≤n(n-1). TheL ₁ (L _∞) algorithm is optimal within a constant factor.     

Optimal algorithm for a special point-labeling problem

A special class of map labeling problem is studied. Let P={p₁,p₂,…,p_n} be a set of point sites distributed on a 2D map. A label associated with each point p_i is an axis-parallel rectangle r_i of specified width. The height of all are same. The placement of r_i must contain p_i at its top-left or bottom-left corner, and it does not obscure any other point in P. The objective is to label the maximum number of points on the map so that the placed labels are mutually non-overlapping. We first consider a simple model for this problem. Here, for each point p_i, the corner specification (i.e., whether the point p_i would appear at the top-left or bottom-left corner of the label) is known a priori. We show that the time complexity of this problem is , and then propose an algorithm for this problem which runs in O(nlogn) time. If the corner specifications of the points in P are not known, our algorithm is a 2-approximation algorithm. Here we propose an efficient heuristic algorithm that is easy to implement. Experimental evidences show that it produces optimal solutions for most of the randomly generated instances and for all the standard benchmarks available in http://www.math-inf.uni-greifswald.de/map-labeling/.     

A lower bound for computing Oja depth

Let S={s₁,…,sn} be a set of points in the plane. The Oja depth of a query point θ with respect to S is the sum of the areas of all triangles (θ,si,sj). This depth may be computed in O(nlogn) time in the RAM model of computation. We show that a matching lower bound holds in the algebraic decision tree model. This bound also applies to the computation of the Oja gradient, the Oja sign test, and to the problem of computing the sum of pairwise distances among points on a line.     

Approximate algorithms for static and continuous range queries in mobile navigation

For many years, spatial range search has been applied to computational geometry and multimedia problems to find interest objects within a given radius. Range search query has traditionally been used to return all objects within a given radius. However, having all objects is not necessary, especially when there are already enough objects closer to the query point. Furthermore, expanding the radius may give users better results, especially when there are a lot of objects just outside the search boundary. Therefore, in this paper, we focus on approximate range search, where the query results are approximate, rather than exact. We propose approximate static range search (ARS) which combines two approaches, namely (i) lowerbound approximate range search, and (ii) upperbound approximate range search. Using ARS, we are able to deliver a better performance, together with low false hit and reasonable false miss. We also extend ARS in the context of a continuous query setting, in which the query moves. This is particularly important in spatial databases as a mobile user who invokes the query is moving. In terms of continuous range search, the intention is to find split points—the locations where the query results will be updated. Accordingly, we propose two methods for approximate continuous range search, namely (i) range search minimization, and (ii) split points minimization. Our performance evaluation which compares our methods with the traditional continuous range search shows that our methods considerably reduce the number of split points, thereby improving overall performance.