On multi-type reverse nearest neighbor search

This paper presents a study of the Multi-Type Reverse Nearest Neighbor (MTRNN) query problem. Traditionally, a reverse nearest neighbor (RNN) query finds all the objects that have the query point as their nearest neighbor. In contrast, an MTRNN query finds all the objects that have the query point in their multi-type nearest neighbors. Existing RNN queries find an influence set by considering only one feature type. However, the influence from multiple feature types is often critical for strategic decision making in many business scenarios, such as site selection for a new shopping center. To that end, we first formalize the notion of the MTRNN query by considering the influence of multiple feature types. We also propose R-tree based algorithms to find the influence set for a given query point and multiple feature types. Finally, experimental results are provided to show the strength of the proposed algorithms as well as design decisions related to performance tuning.     

<Emphasis Type="Italic">k</Emphasis>-Nearest-Neighbor Clustering and Percolation Theory

Let P be a realization of a homogeneous Poisson point process in ℝ ^d with density 1. We prove that there exists a constant k _d , 1<k _d <∞, such that the k-nearest neighborhood graph of P has an infinite connected component with probability 1 when k≥k _d . In particular, we prove that k ₂≤213. Our analysis establishes and exploits a close connection between the k-nearest neighborhood graphs of a Poisson point set and classical percolation theory. We give simulation results which suggest k ₂=3. We also obtain similar results for finite random point sets. Part of the work was done while S.-H. Teng was at Xerox Palo Alto Research Center and MIT. The work of F.F. Yao was supported in part by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China [Project No. CityU 1165/04E].     

The Stationary Characteristics of the <Emphasis Type="Italic">G</Emphasis>/<Emphasis Type="Italic">MSP</Emphasis>/1/<Emphasis Type="Italic">r</Emphasis> Queueing System

A single-server queueing system with recurrent input flow and Markov service process is considered. Both the cases of finite and infinite buffers are investigated. The analysis of this system is based on the method of embedded Markov chain. The main stationary characteristics of system performance are derived.     

<Emphasis Type="Italic">Wissensmanagement</Emphasis>

In dieser Arbeit wird anhand von zwei konkreten Beispielen erl?utert, was Wissensmanagement (WM) ist und warum WM eine so wichtige Rolle in der Zukunft spielen wird. Dies gilt freilich nur, wenn es sich bei WM um mehr handelt als die Verwendung von Informationssystemen oder verteilten Datenbanken für anspruchsvolle Aufgaben.     

Parallel bisecting <Emphasis Type="Italic">k</Emphasis>-means with prediction clustering algorithm

In this paper, we propose a new parallel clustering algorithm, named Parallel Bisecting k-means with Prediction (PBKP), for message-passing multiprocessor systems. Bisecting k-means tends to produce clusters of similar sizes, and according to our experiments, it produces clusters with smaller entropy (i.e., purer clusters) than k-means does. Our PBKP algorithm fully exploits the data-parallelism of the bisecting k-means algorithm, and adopts a prediction step to balance the workloads of multiple processors to achieve a high speedup. We implemented PBKP on a cluster of Linux workstations and analyzed its performance. Our experimental results show that the speedup of PBKP is linear with the number of processors and the number of data points. Moreover, PBKP scales up better than the parallel k-means with respect to the dimension and the desired number of clusters. This research was supported in part by AFRL/Wright Brothers Institute (WBI).     

The Jamiołkowski Isomorphism and a Simplified Proof for the Correspondence Between Vectors Having Schmidt Number <Emphasis Type="Italic">k</Emphasis> and <Emphasis Type="Italic">k</Emphasis>-Positive Maps

Positive maps which are not completely positive are used in quantum information theory as witnesses for convex sets of states, in particular as entanglement witnesses and, more generally, as witnesses for states having Schmidt number not greater than k. Such maps and witnesses are related to k-positive maps, and their properties may be investigated by making use of the Jamiołkowski isomorphism. In this article we review the properties of this isomorphism, noting that there are actually two related mappings bearing that name. As a new result, we give a simplified proof for the correspondence between vectors having Schmidt number k and k-positive maps and thus for the Jamiołkowski criterion for complete positivity. Another consequence is a special case of a result by Choi, namely that k-positivity implies complete positivity, if k is the dimension of the smaller one of the Hilbert spaces on which the operators act.     

<Emphasis Type="Italic">Post-PC-Ära</Emphasis>

Ohne Zusammenfassung     

Parallel <Emphasis Type="Italic">LL</Emphasis> parsing

A deterministic parallel LL parsing algorithm is presented. The algorithm is based on a transformation from a parsing problem to parallel reduction. First, a nondeterministic version of a parallel LL parser is introduced. Then, it is transformed into the deterministic version—the LLP parser. The deterministic LLP(q,k) parser uses two kinds of information to select the next operation — a lookahead string of length up to k symbols and a lookback string of length up to q symbols. Deterministic parsing is available for LLP grammars, a subclass of LL grammars. Since the presented deterministic and nondeterministic parallel parsers are both based on parallel reduction, they are suitable for most parallel architectures.     

<Emphasis Type="Italic">O</Emphasis>(log*<Emphasis Type="Italic">n</Emphasis>) algorithms on a Sum-CRCW PRAM

We present work- and cost-optimal O(log*n) algorithms for prefix sums and linear integer sorting on a Sum-CRCW PRAM.     

Extensions of fuzzy hyperideals in <Emphasis Type="Italic">H</Emphasis><Subscript><Emphasis Type="Italic">V</Emphasis></Subscript>-semigroups

The object of the present paper is the investigation and study of (fuzzy) hyperideals in H _v - semigroups. Regular equivalence relations play in H _v - semigroup theory a role analogous to congruences in semigroup theory, so we introduce fuzzy regular equivalence relations on H _v -semigroups and then we study fuzzy Rees regular relations on H _v -semigroups. Using this ideas, we establish a relation between fuzzy hyperideal of an H _v -semigroup H and fuzzy hyperideal of a quotient H _v -semigroup of H. Some characterizations of them are then shown.      

<Emphasis Type="Italic">Ontologie(n)</Emphasis>

Ontologie ist ein überlieferter Begriff aus der Philosophie und steht dort für die Lehre vom Sein – genauer: von den M?glichkeiten und Bedingungen des Seienden –, ist also eng verwandt mit der Erkenntnistheorie, die sich mit den M?glichkeiten und Grenzen menschlichen Wahrnehmens und Erkennens auseinander setzt. Vorschl?ge an Prof. Dr. Frank <puppe@informatik.uni-wuerzburg.de> oder Dieter Steinbauer <dieter.steinbauer@schufa.de> Alle „Aktuellen Schlagw?rter” seit 1988 finden Sie unter www.ai-wuerzburg.de/as     

Estimation of a Local Lipschitz Constant of the <Emphasis Type="Italic">B</Emphasis><Subscript><Emphasis Type="Italic">q</Emphasis></Subscript>-Entropy

A method for estimating a Lipschitz constant of the entropy operator of the Boltzmann type is suggested. Examples of the use of the obtained estimates in problems for restoring images by projections are given.__________Translated from Avtomatika i Telemekhanika, No. 7, 2005, pp. 54–65.Original Russian Text Copyright © 2005 by Popkov, Rublev.This work was supported by the Program “Branch of Information Technologies and Computer Systems” and the Russian Foundation for Basic Research, project no. 02-01-00198a.     

Qualitative analysis of dynamic systems with the <Emphasis Type="Italic">B</Emphasis><Subscript><Emphasis Type="Italic">q</Emphasis></Subscript> entropy operator

The method is suggested for the investigation of the existence, uniqueness, and localization of singular points of the DSEO class under consideration. The stability conditions are found “in the small” and “in the large.” Examples of the use of the obtained conditions are given.     

Torsion classes of <Emphasis Type="Italic">MV</Emphasis>-algebras

 Torsion classes of MV-algebras are defined as radical classes which are closed with respect to homomorphisms; in this paper we investigate their relations to radical classes of lattice ordered groups and to varieties of MV-algebras. Supported by Grant VEGA 1/9056/02.     

From word to sentence: a pregroup analysis of the object pronoun <Emphasis Type="Italic">who</Emphasis>(<Emphasis Type="Italic">m</Emphasis>)

We explore a computational algebraic approach to grammar via pregroups, that is, partially ordered monoids in which each element has both a left and a right adjoint. Grammatical judgements are formed with the help of calculations on types. These are elements of the free pregroup generated by a partially ordered set of basic types, which are assigned to words, here of English. We concentrate on the object pronoun who(m).     

Fault Identification in System-Level Diagnosis: a Logic-Based Framework and an <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>2</Superscript>\sqrt{τ}/{\log <Emphasis Type="Italic">n</Emphasis>}) Algorithm

Much research has been devoted to system-level diagnosis—SLD. Two issues have been addressed. The first of these is diagnosability, i.e., provide necessary and sufficient conditions for a system of n units to be diagnosable provided that the number of faulty units does not exceed τ . The second is the design of fault identification algorithms, assuming that the system being considered is diagnosable. This paper focuses on the second of these concerns, discussing several algorithms of which the most efficient runs in O(n ^2.5 ) . By considering a logical framework, this paper investigates the process of fault identification and proposes a fault identification algorithm which runs in O( n ² \sqrt τ / \sqrt log n ) , τ < n/2 . Received January 10, 2000; revised August 3, 2000.