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.     

基于固定网格划分和面向类对象的四分树空间索引机制

本文针对地理信息系统中的空间对象形态的不同规则性和空间查询区域的不规则性。提出了一种基于固定网格划分的四分树空间索引机制。     

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.     

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.     

An Object Model of Direction and Its Implications

Direction is an important spatial concept that is used in many fields such as geographic information systems(GIS) and image interpretation. It is also frequently used as a selection condition in spatial queries. Previous work has modeled direction as a relational predicate between spatial objects. Conversely, in this paper, we model direction as a new kind of spatial object using the concepts of vectors, points and angles. The basic approach is to model direction as a unit vector. This novel view of direction has several obvious advantages: Being modeled as a spatial object, a direction object can have its own attributes and operation set. Secondly, new spatial data types such as oriented spatial objects and open spatial objects can be defined at the abstract object level. Finally, the object view of direction makes direction reasoning easy and also reduces the need for a large number of inference rules. These features are important in spatial query processing and optimization. The applicability of the direction model is demonstrated by geographic query examples.     

Pictorial Query Specification for Browsing Through Spatially Referenced Image Databases

A pictorial query specification technique that enables the formulation of complex pictorial queries for browsing through a collection of spatially referenced images is presented. It is distinguished from most other methods by the fact that in these methods the query image specifies a target database image in its entirety whereas in our approach the query image specifies the combination of objects that the target database image should contain rather than being treated as a whole image. The query objects are represented by shape features although other features such as color, texture or wavelets could also be used. Using our technique, it is possible to specify which particular objects should appear in the target images as well as how many occurrences of each object are required. Moreover, it is possible to specify the minimum required certainty of matching between query-image objects and database-image objects, as well as to impose spatial constraints that specify bounds on the distance between objects and the relative direction between them. These spatial constraints can also be used to specify other topological relations such as enclosure, intersection, overlap, etc. Each pictorial query is composed of one or more query images. Each query image is constructed by selecting the required query objects and positioning them according to the desired spatial configuration. Boolean combinations of two or more query images are also possible by use of AND and OR operators. A query image may be negated in order to specify conditions that should not be satisfied by the database images that are retrieved successfully. In addition, a capability is provided to specify whether the same instance of an object is to be used when it appears in more than one of the query images that make up the pictorial query, or whether two different instances are allowed. Several example queries are given that demonstrate the expressive power of this query specification method. An algorithm for retrieving all database images that conform to a given pictorial query specification is presented. The user interface for using this pictorial query specification method to browse the results in a map image database application is described and illustrated via screen shots.     

A top-k spatial join querying processing algorithm based on spark

Aiming at the problem of top-k spatial join query processing in cloud computing systems, a Spark-based top-k spatial join (STKSJ) query processing algorithm is proposed. In this algorithm, the whole data space is divided into grid cells of the same size by a grid partitioning method, and each spatial object in one data set is projected into a grid cell. The Minimum Bounding Rectangle (MBR) of all spatial objects in each grid cell is computed. The spatial objects overlapping with these MBRs in another spatial data set are replicated to the corresponding grid cells, thereby filtering out spatial objects for which there are no join results, thus reducing the cost of subsequent spatial join processing. An improved plane sweeping algorithm is also proposed that speeds up the scanning mode and applies threshold filtering, thus greatly reducing the communication and computation costs of intermediate join results in subsequent top-k aggregation operations. Experimental results on synthetic and real data sets show that the proposed algorithm has clear advantages, and better performance than existing top-k spatial join query processing algorithms.     

ALSBIR: A local-structure-based image retrieval

The general-purpose shape retrieval problem is a challenging task. Particularly, an ideal technique, which can work in clustered environment, meet the requirements of perceptual similarity measure on partial query and overcoming dimensionality curse and adverse environment, is in demand. This paper reports our study on one local structural approach that addresses these issues. Shape representation and indexing are two key points in shape retrieval. The proposed approach combines a novel local-structure-based shape representation and a new histogram indexing structure. The former makes possible partial shape matching of objects without the requirement of segmentation (separation) of objects from complex background, while the latter has an advantage on indexing performance. The search time is linearly proportional to the input complexity. In addition, the method is relatively robust under adverse environments. It is able to infer retrieval results from incomplete information of an input by first extracting consistent and structurally unique local neighborhood information from inputs or models, and then voting on the optimal matches. Thousands of images have been used to test the proposed concepts on sensitivity analysis, similarity-based retrieval, partial query and mixed object query. Very encouraging experimental results with respect to efficiency and effectiveness have been obtained.     

On the Repeatability and Quality of Keypoints for Local Feature-based 3D Object Retrieval from Cluttered Scenes

3D object recognition from local features is robust to occlusions and clutter. However, local features must be extracted from a small set of feature rich keypoints to avoid computational complexity and ambiguous features. We present an algorithm for the detection of such keypoints on 3D models and partial views of objects. The keypoints are highly repeatable between partial views of an object and its complete 3D model. We also propose a quality measure to rank the keypoints and select the best ones for extracting local features. Keypoints are identified at locations where a unique local 3D coordinate basis can be derived from the underlying surface in order to extract invariant features. We also propose an automatic scale selection technique for extracting multi-scale and scale invariant features to match objects at different unknown scales. Features are projected to a PCA subspace and matched to find correspondences between a database and query object. Each pair of matching features gives a transformation that aligns the query and database object. These transformations are clustered and the biggest cluster is used to identify the query object. Experiments on a public database revealed that the proposed quality measure relates correctly to the repeatability of keypoints and the multi-scale features have a recognition rate of over 95% for up to 80% occluded objects.     

基于逻辑规则的语义缓存查询处理优化技术

语义缓存在移动计算环境中有着非常广阔的应用前景．查询处理是语义缓存的一个关键问题，但是现有的查询处理算法在时空效率和裁剪结果的复杂度两个方面存在很大的局限性，这在一定程度上限制了语义缓存的实用性．为了克服这些缺陷，作者首先给出并证明了用于优化查询裁剪的逻辑规则；基于这些规则，给出了剩余查询的裁剪算法；最终给出了只需进行剩余查询裁剪的优化查询处理算法．算法分析从理论上证明了该优化机制的有效性，同时，仿真实验的性能比较也表明该优化方法在提高查询裁剪时空效率和降低剩余查询复杂度等方面都要明显优于没有优化的方法．     

Graph-based representation for similarity retrieval of symbolic images

Image retrieval from an image database by the image objects and their spatial relationships has emerged as an important research subject in these decades. To retrieve images similar to a given query image, retrieval methods must assess the similarity degree between a database image and the query image by the extracted features with acceptable efficiency and effectiveness. This paper proposes a graph-based model SRG (spatial relation graph) to represent the semantic information of the contained objects and their spatial relationships in an image with no file annotation. In an SRG graph, the image objects are symbolized by the predefined class names as vertices and the spatial relations between object pairs are represented as arcs. The proposed model assesses the similarity degree between two images by calculating the maximum common subgraph of two corresponding SRG’s through intersection, which has quadratic time complexity owing to the characteristics of SRG. Its efficiency remains quadratic regardless of the duplication rate of the object symbols. The extended model SRG_T is also proposed, with the same time complexity, for the applications that need to consider the topological relations among objects. A synthetic symbolic image database and an existing image dataset are used in the conducted experiments to verify the performance of the proposed models. The experimental results show that the proposed models have compatible retrieval quality with remarkable efficiency improvements compared with three well-known methods LCS_Clique, SIM_R, and 2D Be-string, where LCS_Clique utilizes the number of objects in the maximum common subimage as its similarity function, SIM_R uses accumulation-based similarity function of similar object pairs, and 2D Be-string calculates the similarity of 2D patterns by the linear combination of two 1D similarities.     

Window Query Processing in Linear Quadtrees

The linear quadtree is a spatial access method that is built by decomposing the spatial objects in a database into quadtree blocks and storing these quadtree blocks in a B-tree. The linear quadtree is very useful for geographic information systems because it provides good query performance while using existing B-tree implementations. An algorithm and a cost model are presented for processing window queries in linear quadtrees. The algorithm can handle query windows of any shape in the general case of spatial databases with overlapping objects. The algorithm recursively decomposes the space into quadtree blocks, and uses the quadtree blocks overlapping the query window to search the B-tree. The cost model estimates the I/O cost of processing window queries using the algorithm. The cost model is also based on a recursive decomposition of the space, and it uses very simple parameters that can easily be maintained in the database catalog. Experiments with real and synthetic data sets verify the accuracy of the cost model.     

面向2D对象形状识别的空间模糊查询研究

基于空间形状的查询与认知主体的空间推理密切相关。从空间认知的角度,通常希望查询结果是一类形状结构相似的对象集合。以形状的不确定性表达和模糊查询为研究内容,提出一种面向2D对象形状识别的空间查询方法--向心包络算法。算法将对象划分为以最大内径中心为公共点的三角形集合,在此基础上建立相应的形状度量方法,通过提取所有顶点关于对象整体结构的形状影响因子求得对象之间的形状相似度,并建立与模糊形状谓词的匹配关系。实验表明,该方法可以实现2D对象的空间模糊查询,且查询结果与模糊形状谓词基本一致。     

Spatial query processing for fuzzy objects

Range and nearest neighbor queries are the most common types of spatial queries, which have been investigated extensively in the last decades due to its broad range of applications. In this paper, we study this problem in the context of fuzzy objects that have indeterministic boundaries. Fuzzy objects play an important role in many areas, such as biomedical image databases and GIS communities. Existing research on fuzzy objects mainly focuses on modeling basic fuzzy object types and operations, leaving the processing of more advanced queries largely untouched. In this paper, we propose two new kinds of spatial queries for fuzzy objects, namely single threshold query and continuous threshold query, to determine the query results which qualify at a certain probability threshold and within a probability interval, respectively. For efficient single threshold query processing, we optimize the classical R-tree-based search algorithm by deriving more accurate approximations for the distance function between fuzzy objects and the query object. To enhance the performance of continuous threshold queries, effective pruning rules are developed to reduce the search space and speed up the candidate refinement process. The efficiency of our proposed algorithms as well as the optimization techniques is verified with an extensive set of experiments using both synthetic and real datasets.     

Cost modeling of spatial operators using non-parametric regression

In an object-relational database management system, a query optimizer requires users to provide cost models of user-defined functions. The traditional approach is analytical, that is, it builds a cost model generated as a result of analyzing the query processing steps. This analytical approach is difficult, however, especially for spatial query operators because of the complexity of the processing steps. In this paper, a new approach that uses non-parametric regression is proposed. This approach significantly simplifies the process of building a cost model, while achieving highly accurate cost estimation. We demonstrate the simplicity and efficacy of this approach through experiments for three spatial operators—the range query, the window query, and the k-nearest neighbor query—commonly used in spatial databases, using both real and synthetic data sets.     

基于位置-文本关系的空间对象top-k查询与排序方法

针对普通的空间关键字查询通常会导致多查询结果的问题。本文提出了一种基于空间对象位置-文本相关度的top- k 查询与排序方法,用于获取与给定空间关键字查询在文本上相关且位置上相近的典型空间对象。该方法分为离线处理和在线查询处理2个阶段。在离线阶段,根据空间对象之间的位置相近性和文本相似性,度量任意一对空间对象之间的位置-文本关系紧密度。在此基础上,提出了基于概率密度的代表性空间对象选取算法,根据空间对象之间的位置-文本关系为每个代表性空间对象构建相应的空间对象序列。在线查询处理阶段,对于一个给定的空间关键字查询,利用Cosine相似度评估方法计算查询条件与代表性空间对象之间的相关度,然后使用阈值算法（threshold algorithm,TA）在预先创建的空间对象序列上快速选出top- k 个满足查询需求的典型空间对象。实验结果表明:提出的空间对象top- k 查询与排序方法能够有效地满足用户查询需求,并且具有较高的准确性、典型性和执行效率。     

Spatial Plateau Algebra for implementing fuzzy spatial objects in databases and GIS: Spatial plateau data types and operations

Many geographical applications have to deal with spatial objects that reveal an intrinsically vague or fuzzy nature. A spatial object is fuzzy if locations exist that cannot be assigned completely to the object or to its complement. Spatial database systems and Geographical Information Systems (GIS) are currently unable to cope with this kind of data. Based on an available abstract data model of fuzzy spatial data types for fuzzy points, fuzzy lines, and fuzzy regions that leverages fuzzy set theory and fuzzy point set topology, this article proposes a Spatial Plateau Algebra that provides spatial plateau data types as an implementation of fuzzy spatial data types. Each spatial plateau object consists of a finite number of crisp counterparts that are all adjacent or disjoint to each other, are associated with different membership values, and hence form different plateaus. The formal framework and the implementation are based on well known, exact models and implementations of crisp spatial data types. Spatial plateau operations as geometric operations on spatial plateau objects are expressed as a combination of geometric operations on the underlying crisp spatial objects. This article offers a conceptually clean foundation for implementing a database extension for fuzzy spatial objects and their operations, and demonstrates the embedding of these new data types as attribute data types in a database schema as well as the incorporation of fuzzy spatial operations into a database query language.     

Continuous monitoring of range spatial keyword query over moving objects

In this paper, we propose an efficient solution for processing continuous range spatial keyword queries over moving spatio-textual objects (namely, CRSK-mo queries). Major challenges in efficient processing of CRSK-mo queries are as follows: (i) the query range is determined based on both spatial proximity and textual similarity; thus a straightforward spatial proximity based pruning of the search space is not applicable as any object far from a query location with a high textual similarity score can still be the answer (and vice versa), (ii) frequent location updates may invalidate a query result, and thus require frequent re-computing of the result set for any object updates. To address these challenges, the key idea of our approach is to exploit the spatial and textual upper bounds between queries and objects to form safe zones (at the client-side) and buffer regions (at the server-side), and then use these bounds to quickly prune objects and queries through smart in-memory data structures. We conduct extensive experiments with a synthetic dataset that verify the effectiveness and efficiency of our proposed algorithm.     

基于面向对象数据库的三维GIS实验系统

基于面向对象GIS模型和空间数据库技术,在面向对象数据库Jasmine的基础上建立了基本的空间数据库系统．通过实现空间索引结构V—Reactive树、空间查询等技术,设计和实现了一个三维GIS实验系统．该系统能够实现三维GIS的一些典型功能,包括细节层次可视化、多比例尺、空间查询等．     

Shapeme histogram projection and matching for partial object recognition

Histograms of shape signature or prototypical shapes, called shapemes, have been used effectively in previous work for 2D/3D shape matching and recognition. We extend the idea of shapeme histogram to recognize partially observed query objects from a database of complete model objects. We propose representing each model object as a collection of shapeme histograms and match the query histogram to this representation in two steps: 1) compute a constrained projection of the query histogram onto the subspace spanned by all the shapeme histograms of the model and 2) compute a match measure between the query histogram and the projection. The first step is formulated as a constrained optimization problem that is solved by a sampling algorithm. The second step is formulated under a Bayesian framework, where an implicit feature selection process is conducted to improve the discrimination capability of shapeme histograms. Results of matching partially viewed range objects with a 243 model database demonstrate better performance than the original shapeme histogram matching algorithm and other approaches.