Topological relations between spatial objects are the most important kind of qualitative spatial information. Dozens of relation models have been proposed in the past two decades. These models usually make a small number of distinctions and therefore can only cope with spatial information at a fixed granularity of spatial knowledge. In this paper, we propose a topological relation model in which the topological relation between two convex plane regions can be uniquely represented as a circular string over the alphabet {u; v; x; y}. A linear algorithm is given to compute the topological relation between two convex polygons. The infinite relation calculus could be used in hierarchical spatial reasoning as well as in qualitative shape description.

We present and implement a Weighted Partial MaxSAT solver based on successive calls to a SAT solver. We prove the correctness of our algorithm and compare our solver with other Weighted Partial MaxSAT solvers.

We introduce a new discriminative piecewise linear model for classification. A two-step method is developed to construct the model. In the first step, we sample some boundary points that lie between positive and negative data, as well as corresponding directions from negative data to positive data. The sampling result gives a discriminative nonparametric decision surface, which preserves enough information to correctly classify all training data. To simplify this surface, in the second step we propose a nonparametric approach for linear surface segmentation using Dirichlet process mixtures. The final result is a piecewise linear model, in which the number of linear surface pieces is automatically determined by the Bayesian inference according to data. Experiments on both synthetic and real data verify the effectiveness of the proposed model.

We further develop Object matching, or alignment, is an underlying problem a semi-supervised "bootstrapping" variant of kernelized for many natural language processing tasks, including document sorting that addresses the problem of noise. We compare alignment (Vu, Aw, and Zhang 2009), sentence alignment kernelized sorting with matching canonical correlation (Gale and Church 1991; Rapp 1999) and transliteration analysis (MCCA) (Haghighi et al. 2008) on a wide variety mining (Hermjakob, Knight, and Daumé III 2008; of tasks and data sets and show that these strategies are Udupa et al. 2009). For example, in document alignment, sufficient to turn kernelized sorting from an approach with we have English documents (objects) and French documents highly unpredictable performance into a viable approach for (objects) and our goal is to discover a matching between NLP problems.

In this abstract, we compare semantic search (in the RDF model) with keyword search (in the relational model), and illustrate how these two search paradigms are different. This comparison addresses the following questions: (1) What can semantic search achieve that keyword search can not (in terms of behavior)? (2) Why is it difficult to simulate semantic search, using keyword search on the relational data model? We use the term keyword search, when the search is performed on data stored in the relational data model, as in traditional relational databases, and an example of keyword search in databases is [Hri02]. We use the term semantic search, when the search is performed on data stored in the RDF data model. Note that when the data is modeled in RDF, it inherently contains explicit typed relations or semantics, and hence the use of the term “semantic search.” Let us begin with an example, to illustrate the differences between semantic search and keyword search.

As the semantic web grows in popularity and enters the mainstream of computer technology, RDF (Resource Description Framework) datasets are becoming larger and more complex. Advanced semantic web ontologies, especially in medicine and science, are developing. As more complex ontologies are developed, there is a growing need for efficient queries that handle inference. In areas such as research, it is vital to be able to perform queries that retrieve not just facts but also inferred knowledge and uncertain information. OWL (Web Ontology Language) defines rules that govern provable inference in semantic web datasets. In this paper, we detail a database schema using bit vectors that is designed specifically for RDF datasets. We introduce a framework for materializing and storing inferred triples. Our bit vector schema enables storage of inferred knowledge without a query performance penalty. Inference queries are simplified and performance is improved. Our evaluation results demonstrate that our inference solution is more scalable and efficient than the current state-of-the-art. There are also standards being developed for representing probabilistic reasoning within OWL ontologies. We specify a framework for materializing uncertain information and probabilities using these ontologies. We define a multiple vector schema for representing probabilities and classifying uncertain knowledge using thresholds. This solution increases the breadth of information that can be efficiently retrieved.

Diffusion processes taking place in social networks are used to model a number of phenomena, such as the spread of human or computer viruses, and the adoption of products in viral marketing campaigns. It is generally difficult to obtain accurate information about how such spreads actually occur, so a variety of stochastic diffusion models are used to simulate spreading processes in networks instead. We show that a canonical genetic algorithm with a spatially distributed population, when paired with specific forms of Holland's synthetic hyperplane-defined objective functions, can simulate a large and rich class of diffusion models for social networks. These include standard diffusion models, such as the Independent Cascade and Competing Processes models. In addition, our Genetic Algorithm Diffusion Model (GADM) can also model complex phenomena such as information diffusion. We demonstrate an application of the GADM to modeling information flow in a large, dynamic social network derived from e-mail headers.

Goal-directed path planning is one of the basic and widely studied problems in the field of mobile robotics. Homotopy classes of trajectories, arising due to the presence of obstacles, are defined as sets of trajectories that can be transformed into each other by gradual bending and stretching without colliding with obstacles. The problem of finding least-cost paths restricted to a specific homotopy class or finding least-cost paths that do not belong to certain homotopy classes arises frequently in such applications as predicting paths for dynamic entities and computing heuristics for path planning with dynamic constraints. In the present work, we develop a compact way of representing homotopy classes and propose an efficient method of graph search-based optimal path planning with constraints on homotopy classes. The method is based on representing the environment of the robot as a complex plane and making use of the Cauchy Integral Theorem. We prove optimality of the method and show its efficiency experimentally.

We show how the situation calculus can be reformulated in terms of the first-order stable model semantics. A further transformation into answer set programs allows us to use an answer set solver to perform propositional reasoning about the situation calculus. We also provide an ASP style encoding method for Reiter's basic action theories, which tells us how the solution to the frame problem in ASP is related to the solution in the situation calculus.

The bare minimum lexical resource required to translate between a pair of languages is a translation dictionary. Unfortunately, dictionaries exist only between a tiny fraction of the 49 million possible language-pairs making machine translation virtually impossible between most of the languages. This paper summarizes the last four years of our research motivated by the vision of panlingual communication. Our research comprises three key steps. First, we compile over 630 freely available dictionaries over the Web and convert this data into a single representation – the translation graph. Second, we build several inference algorithms that infer translations between word pairs even when no dictionary lists them as translations. Finally, we run our inference procedure offline to construct PANDICTIONARY– a sense-distinguished, massively multilingual dictionary that has translations in more than 1000 languages. Our experiments assess the quality of this dictionary and find that we have 4 times as many translations at a high precision of 0.9 compared to the English Wiktionary, which is the lexical resource closest to PANDICTIONARY.