Surface k-NN query processing

A k-NN query finds the k nearest-neighbors of a given point from a point database. When it is sufficient to measure object distance using the Euclidian distance, the key to efficient k-NN query processing is to fetch and check the distances of a minimum number of points from the database. For many applications, such as vehicle movement along road networks or rover and animal movement along terrain surfaces, the distance is only meaningful when it is along a valid movement path. For this type of k-NN queries, the focus of efficient query processing is to minimize the cost of computing distances using the environment data (such as the road network data and the terrain data), which can be several orders of magnitude larger than that of the point data. Efficient processing of k-NN queries based on the Euclidian distance or the road network distance has been investigated extensively in the past. In this paper, we investigate the problem of surface k-NN query processing, where the distance is calculated from the shortest path along a terrain surface. This problem is very challenging, as the terrain data can be very large and the computational cost of finding shortest paths is very high. We propose an efficient solution based on multiresolution terrain models. Our approach eliminates the need of costly process of finding shortest paths by ranking objects using estimated lower and upper bounds of distance on multiresolution terrain models.

BM+-tree: A hyperplane-based index method for high-dimensional metric spaces

In this paper, we propose a novel high-dimensional index method, the BM+-tree, to support efficient processing of similarity search queries in high-dimensional spaces. The main idea of the proposed index is to improve data partitioning efficiency in a high-dimensional space by using a rotary binary hyperplane, which further partitions a subspace and can also take advantage of the twin node concept used in the M+-tree. Compared with the key dimension concept in the M+-tree, the binary hyperplane is more effective in data filtering. High space utilization is achieved by dynamically performing data reallocation between twin nodes. In addition, a post processing step is used after index building to ensure effective filtration. Experimental results using two types of real data sets illustrate a significantly improved filtering efficiency.

An empirical study of Hoelfding Racing for model selction in K-nearest neighbor classification

Racing algorithms have recently been proposed as a general-purpose method for performing model selection in machine teaming algorithms. In this paper, we present an empirical study of the Hoeffding racing algorithm for selecting the k parameter in a simple k-nearest neighbor classifier. Fifteen widely-used classification datasets from UCI are used and experiments conducted across different confidence levels for racing. The results reveal a significant amount of sensitivity of the k-nn classifier to its model parameter value. The Hoeffding racing algorithm also varies widely in its performance, in terms of the computational savings gained over an exhaustive evaluation. While in some cases the savings gained are quite small, the racing algorithm proved to be highly robust to the possibility of erroneously eliminating the optimal models. All results were strongly dependent on the datasets used.

A multiresolution terrain model for efficient visualization query processing

Multiresolution Triangular Mesh (MTM) models are widely used to improve the performance of large terrain visualization by replacing the original model with a simplified one. MTM models, which consist of both original and simplified data, are commonly stored in spatial database systems due to their size. The relatively slow access speed of disks makes data retrieval the bottleneck of such terrain visualization systems. Existing spatial access methods proposed to address this problem rely on main-memory MTM models, which leads to significant overhead during query processing. In this paper, we approach the problem from a new perspective and propose a novel MTM called direct mesh that is designed specifically for secondary storage. It supports available indexing methods natively and requires no modification to MTM structure. Experiment results, which are based on two real-world data sets, show an average performance improvement of 5-10 times over the existing methods.

A scaleless data model for direct and progressive spatial query processing

A progressive spatial query retrieves spatial data based on previous queries (e.g., to fetch data in a more restricted area with higher resolution). A direct query, on the other side, is defined as an isolated window query. A multi-resolution spatial database system should support both progressive queries and traditional direct queries. It is conceptually challenging to support both types of query at the same time, as direct queries favour location-based data clustering, whereas progressive queries require fragmented data clustered by resolutions. Two new scaleless data structures are proposed in this paper. Experimental results using both synthetic and real world datasets demonstrate that the query processing time based on the new multiresolution approaches is comparable and often better than multi-representation data structures for both types of queries.

Dissecting query performance in logical data models: Parsimony vs. greater ontological clarity

Even when data repositories exhibit near perfect data quality, users may formulate queries that do not correspond to the information requested. Users’ poor information retrieval performance may arise from either problems understanding of the data models that represent the real world systems, or their query skills. This research focuses on users’ understanding of the data structures, i.e., their ability to map the information request and the data model. The Bunge-Wand-Weber ontology was used to formulate three sets of hypotheses. Two laboratory experiments (one using a small data model and one using a larger data model) tested the effect of ontological clarity on users’ performance when undertaking component, record, and aggregate level tasks. The results indicate for the hypotheses associated with different representations but equivalent semantics that parsimonious data model participants performed better for component level tasks but that ontologically clearer data model participants performed better for record and aggregate level tasks.

Review of Interpersonal adaptation: Dyadic interaction patterns By Judee K. Burgoon, Lesa

In this ambitious book, Burgoon, Stern, and Dillman present the most comprehensive coverage of the literature on interpersonal adaptation that I have seen in recent years. Their mission is to make a critical examination of this whole area from both theoretical and methodological perspectives, and then to present their own synthetic theory (interpersonal adaptation theory, IAT) and research agenda. Such a mission produces very high expectations in readers, and inevitably some readers will feel that the authors do not achieve all of it. Personally, I was impressed by how much they do achieve, and I was intrigued by the questions they did not answer. One can ask no more than this of any single book.

Morphine has a dual concentration-dependent effect on K+-evoked substance P release from rat peripheral airways

Our previous investigations of possible lung mechanisms underlying the effectiveness of nebulized morphine for the relief of dyspnoea, have shown a high density of non-conventional opioid binding sites in rat airways with similar binding characteristics (opioid alkaloid-sensitive, opioid peptide-insensitive) to that of putative mu(3)-opioid receptors on immune cells. To investigate whether these lung opioid binding sites are functional receptors, this study was designed to determine (using superfusion) whether morphine modulates the K+-evoked release of the pro-inflammatory neuropeptide, substance P (SP), from rat peripheral airways. Importantly, K+-evoked SP release was Ca2+-dependent, consistent with vesicular release. Submicromolar concentrations of morphine (1 and 200 nM) inhibited K+-evoked SP release from rat peripheral airways in a naloxone (1 mu M) reversible manner. By contrast, 1 mu M morphine enhanced K+-evoked SP release and this effect was not reversed by 1 mu M naloxone. However, 100 mu M naloxone not only antagonized the facilitatory effect of 1 mu M morphine on K+-evoked SP release from rat peripheral airways but it inhibited release to a similar extent as 200 nM morphine. It is possible that these latter effects are mediated by non-conventional opioid receptors located on mast cells, activation of which causes naloxone-reversible histamine release that in turn augments the release of SP from sensory nerve terminals in the peripheral airways. Clearly, further studies are required to investigate this possibility. (C) 1997 Academic Press Limited.

PCR bias toward the wild-type k-ras and p53 sequences: Implications for PCR detection of mutations and cancer diagnosis

PCR-based cancer diagnosis requires detection of rare mutations in k-ras, p53 or other genes. The assumption has been that mutant and wild-type sequences amplify with near equal efficiency, so that they are eventually present in proportions representative of the starting material. Work factor IX suggests that this assumption is invalid for one case of near-sequence identity To test the generality of this phenomenon and its relevance to cancer diagnosis, primers distant from point mutations in p53 and k-ras were used to amplify, wild-type and mutant sequences from these genes. A substantial bias against PCR amplification of mutants was observed for two regions of the p53 gene and one region of k-ras. For kras and p53, bias was observed when the wild-type and mutant sequences were amplified separately or when mixed in equal proportions before PCR. Bias was present with proofreading and non-proofreading polymerases. Mutant and wild-type segments of the factor V cystic fibrosis transmembrane conductance regulator and prothrombin genes were amplified and did not exhibit PCR bias. Therefore, the assumption of equal PCR efficiency for point mutant and wild-type sequences is invalid in several systems. Quantitative or diagnostic PCR will require validation for each locus, and enrichment strategies may be needed to optimize detection of mutants.

5-cycle systems of K-v-F with a hole

Recently the problem of the existence of a 5-cycle system of K-v with a hole of size u was completely solved. In this paper we prove necessary and sufficient conditions on v and u for the existence of a 5-cycle system of K-v - F, with a hole of size u.

Programming internet based DAI applications in Qu-Prolog

This paper presents the unique collection of additional features of Qu-Prolog, a variant of the Al programming language Prolog, and illustrates how they can be used for implementing DAI applications. By this we mean applications comprising communicating information servers, expert systems, or agents, with sophisticated reasoning capabilities and internal concurrency. Such an application exploits the key features of Qu-Prolog: support for the programming of sound non-clausal inference systems, multi-threading, and high level inter-thread message communication between Qu-Prolog query threads anywhere on the internet. The inter-thread communication uses email style symbolic names for threads, allowing easy construction of distributed applications using public names for threads. How threads react to received messages is specified by a disjunction of reaction rules which the thread periodically executes. A communications API allows smooth integration of components written in C, which to Qu-Prolog, look like remote query threads.

Maximum packings of K-v-K-u with triples

We construct, for all positive integers u, and v with u less than or equal to v, a decomposition of K-v - K-u (the complete graph on v vertices with a. hole of size u) into the maximum possible number of edge disjoint triangles.

Bonding effects and the crystal structures of (NH4)(2)[Cu(H2O)(6)](SO4)(2) and its (H2O)-O-18 substituted form at 9.5 K

The crystal structures of the Tutton salts (NH4)(2)[Cu(H2O)(6)](SO4)(2), diammonium hexaaquacopper disulfate, formed with normal water and isotopically substituted (H2O)-O-18, have been determined by X-ray diffraction at 9.5 K and are very similar, with Cu-O(7) the longest of the Cu-O bonds of the Jahn-Teller distorted octahedral [Cu(H2O)(6)](2+) complex. It is known that structural differences accompany deuteration of (NH4)(2)[Cu(H2O)(6)](SO4)(2), the most dramatic of which is a switch to Cu-O(8) as the longest such bond. The present result suggests that the structural differences are associated with hydrogen-bonding effects rather than with increased mass of the water ligands affecting the Jahn-Teller coupling. The Jahn-Teller distortions and hydrogen-bonding contacts in the compounds are compared with those reported for other Tutton salts at ambient and high pressure.

Measuring the interaction forces between protein inclusion bodies and an air bubble using an atomic force microscope

Interaction forces between protein inclusion bodies and an air bubble have been quantified using an atomic force microscope (AFM). The inclusion bodies were attached to the AFM tip by covalent bonds. Interaction forces measured in various buffer concentrations varied from 9.7 nN to 25.3 nN (+/- 4-11%) depending on pH. Hydrophobic forces provide a stronger contribution to overall interaction force than electrostatic double layer forces. It also appears that the ionic strength affects the interaction force in a complex way that cannot be directly predicted by DLVO theory. The effects of pH are significantly stronger for the inclusion body compared to the air bubble. This study provides fundamental information that will subsequently facilitate the rational design of flotation recovery system for inclusion bodies. It has also demonstrated the potential of AFM to facilitate the design of such processes from a practical viewpoint.