Maximum <Emphasis Type="Italic">k</Emphasis>-Splittable <Emphasis Type="Italic">s</Emphasis>,<Emphasis Type="Italic">t</Emphasis>-Flows

Given a graph with a source and a sink node, the NP-hard maximum k-splittable s,t-flow (M k SF) problem is to find a flow of maximum value from s to t with a flow decomposition using at most k paths. The multicommodity variant of this problem is a natural generalization of disjoint paths and unsplittable flow problems. Constructing a k-splittable flow requires two interdepending decisions. One has to decide on k paths (routing) and on the flow values for the paths (packing). We give efficient algorithms for computing exact and approximate solutions by decoupling the two decisions into a first packing step and a second routing step. Usually the routing is considered before the packing. Our main contributions are as follows: (i) We show that for constant k a polynomial number of packing alternatives containing at least one packing used by an optimal M k SF solution can be constructed in polynomial time. If k is part of the input, we obtain a slightly weaker result. In this case we can guarantee that, for any fixed ε>0, the computed set of alternatives contains a packing used by a (1−ε)-approximate solution. The latter result is based on the observation that (1−ε)-approximate flows only require constantly many different flow values. We believe that this observation is of interest in its own right. (ii) Based on (i), we prove that, for constant k, the M k SF problem can be solved in polynomial time on graphs of bounded treewidth. If k is part of the input, this problem is still NP-hard and we present a polynomial time approximation scheme for it.     

(Weak) Dual hyper <Emphasis Type="Italic">K</Emphasis>-ideals

In this note by considering the notion of (weak) dual hyper K-ideal, we obtain some related results. After that we determine the relationships between (weak) dual hyper K-ideals and (weak) hyper K-ideals. Finally, we give a characterization of hyper K-algebras of order 3 or 4 based on the (weak) dual hyper K-ideals.     

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.      

Intuitionistic (<Emphasis Type="Italic">S</Emphasis>, <Emphasis Type="Italic">T</Emphasis>)-fuzzy hyperquasigroups

The concept of intuitionistic fuzzy subhyperquasigroups in a hyperquasigroup with respect to an s-norm and a t-norm on intuitionistic fuzzy sets is introduced and their properties of such hyperquasigroups are studied. Intuitionistic (S, T)-fuzzy relations on a hyperquasigroup G are discussed. In particular, we investigate connections hyperquasigroups with binary quasigroups.     

The Zariski topology on the spectrum of prime <Emphasis Type="Italic">L</Emphasis>-submodules

Let R be a commutative ring with identity and let M be an R-module. We topologize L − Spec(M), the collection of all prime L-submodules of M, analogous to that for FSpec(R), the spectrum of fuzzy prime ideals of R, and investigate the properties of this topological space. In particular, we will study the relationship between L − Spec(M) and L − Spec(R/Ann(M)) and obtain some results.     

Panconnectivity and edge-pancyclicity of 3-ary <Emphasis Type="Italic">N</Emphasis>-cubes

We study two topological properties of the 3-ary n-cube Q _n ³. Given two arbitrary distinct nodes x and y in Q _n ³, we prove that there exists an x–y path of every length ranging from d(x,y) to 3 ⁿ −1, where d(x,y) is the length of a shortest path between x and y. Based on this result, we prove that Q _n ³ is edge-pancyclic by showing that every edge in Q _n ³ lies on a cycle of every length ranging from 3 to 3 ⁿ .

EP<Emphasis Type="Italic">n</Emphasis>P: An Accurate <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis>) Solution to the P<Emphasis Type="Italic">n</Emphasis>P Problem

We propose a non-iterative solution to the PnP problem—the estimation of the pose of a calibrated camera from n 3D-to-2D point correspondences—whose computational complexity grows linearly with n. This is in contrast to state-of-the-art methods that are O(n ⁵) or even O(n ⁸), without being more accurate. Our method is applicable for all n≥4 and handles properly both planar and non-planar configurations. Our central idea is to express the n 3D points as a weighted sum of four virtual control points. The problem then reduces to estimating the coordinates of these control points in the camera referential, which can be done in O(n) time by expressing these coordinates as weighted sum of the eigenvectors of a 12×12 matrix and solving a small constant number of quadratic equations to pick the right weights. Furthermore, if maximal precision is required, the output of the closed-form solution can be used to initialize a Gauss-Newton scheme, which improves accuracy with negligible amount of additional time. The advantages of our method are demonstrated by thorough testing on both synthetic and real-data.     

Continually Answering Constraint <Emphasis Type="Italic">k</Emphasis>-<Emphasis Type="Italic">NN</Emphasis> Queries in Unstructured P2P Systems

We consider the problem of efficiently computing distributed geographical k-NN queries in an unstructured peer-to-peer （P2P） system, in which each peer is managed by an individual organization and can only communicate with its logical neighboring peers. Such queries are based on local filter query statistics, and require as less communication cost as possible which makes it more difficult than the existing distributed k-NN queries. Especially, we hope to reduce candidate peers and degrade communication cost. In this paper, we propose an efficient pruning technique to minimize the number of candidate peers to be processed to answer the k-NN queries. Our approach is especially suitable for continuous k-NN queries when updating peers, including changing ranges of peers, dynamically leaving or joining peers, and updating data in a peer. In addition, simulation results show that the proposed approach outperforms the existing Minimum Bounding Rectangle （MBR）-based query approaches, especially for continuous queries.     

Structural optimization of a full-text <Emphasis Type="Italic">n</Emphasis>-gram index using relational normalization

As the amount of text data grows explosively, an efficient index structure for large text databases becomes ever important. The n-gram inverted index (simply, the n-gram index) has been widely used in information retrieval or in approximate string matching due to its two major advantages: language-neutral and error-tolerant. Nevertheless, the n-gram index also has drawbacks: the size tends to be very large, and the performance of queries tends to be bad. In this paper, we propose the two-level n-gram inverted index (simply, the n-gram/2L index) that significantly reduces the size and improves the query performance by using the relational normalization theory. We first identify that, in the (full-text) n-gram index, there exists redundancy in the position information caused by a non-trivial multivalued dependency. The proposed index eliminates such redundancy by constructing the index in two levels: the front-end index and the back-end index. We formally prove that this two-level construction is identical to the relational normalization process. We call this process structural optimization of the n-gram index. The n-gram/2L index has excellent properties: (1) it significantly reduces the size and improves the performance compared with the n-gram index with these improvements becoming more marked as the database size gets larger; (2) the query processing time increases only very slightly as the query length gets longer. Experimental results using real databases of 1 GB show that the size of the n-gram/2L index is reduced by up to 1.9–2.4 times and, at the same time, the query performance is improved by up to 13.1 times compared with those of the n-gram index. We also compare the n-gram/2L index with Makinen’s compact suffix array (CSA) (Proc. 11th Annual Symposium on Combinatorial Pattern Matching pp. 305–319, 2000) stored in disk. Experimental results show that the n-gram/2L index outperforms the CSA when the query length is short (i.e., less than 15–20), and the CSA is similar to or better than the n-gram/2L index when the query length is long (i.e., more than 15–20).     

Fuzzy <Emphasis Type="Italic">R</Emphasis>-subgroups with thresholds of near-rings and implication operators

Using the belongs to relation (∈) and quasi-coincidence with relation (q) between fuzzy points and fuzzy sets, the concept of (α, β)-fuzzy R-subgroup of a near-ring where α , β are any two of {∈, q, ∈∨q , ∈∧q} with α ≠ ∈∧q is introduced and related properties are investigated. We also introduce the notion of a fuzzy R-subgroup with thresholds which is a generalization of an ordinary fuzzy R-subgroup and an (∈, ∈∨q)-fuzzy R-subgroup. Finally, we give the definition of an implication-based fuzzy R-subgroup.     

Three-dimensional analysis of Marangoni flow and radial segregation in Ge<Subscript><Emphasis Type="Italic">x</Emphasis></Subscript>Si<Subscript>1-<Emphasis Type="Italic">x</Emphasis></Subscript> melt with Czochralski configuration

In order to examine the flow field and the radial segregation of silicon (Si) in a Ge _x Si_1-x melt with an idealized Czochralski (Cz) configuration, we conducted a series of unsteady three-dimensional (3-D) numerical simulations under zero-gravity conditions. The effect of convection driven by surface tension on the free surface of the melt was included in the model, by considering thermal, as well as solutal Marangoni convection. The concentration and flow fields at several stages during crystal growth are presented for several temperature differences, driving the Marangoni convection. The simulation results indicate that the flow and concentration fields are axisymmetric for Ma _T < 625 and become oscillatory and 3-D for higher values. It was found that the maximum Si concentration difference at the growth interface decreases as thermal Marangoni number increases due to higher flow velocities in the vicinity of the interface. However, temporal fluctuations of Si concentration at the interface increase at higher thermal Marangoni numbers. The effects of aspect ratio (A _r) were also considered in the model. It was found that the aspect ratio of the melt in the crucible has a prominent influence on the flow pattern in the melt which, in turn, effects the Si concentration at the growth interface.     

States on <Emphasis Type="Italic">R</Emphasis><Subscript>0</Subscript> algebras

The aim of this paper is to introduce the notion of states on R ₀ algebras and investigate some of their properties. We prove that every R ₀ algebra possesses at least one state. Moreover, we investigate states on weak R ₀ algebras and give some examples to show that, in contrast to R ₀ algebras, there exist weak R ₀ algebras which have no states. We also derive the condition under which finite linearly ordered weak R ₀ algebras have a state. This work is supported by NSFC (No.60605017).     

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).     

Composite Distance Transformation for Indexing and k-Nearest-Neighbor Searching in High-Dimensional Spaces

Due to the famous dimensionality curse problem, search in a high-dimensional space is considered as a ＂hard＂ problem. In this paper, a novel composite distance transformation method, which is called CDT, is proposed to support a fast κ-nearest-neighbor （κ-NN） search in high-dimensional spaces. In CDT, all （n） data points are first grouped into some clusters by a κ-Means clustering algorithm. Then a composite distance key of each data point is computed. Finally, these index keys of such n data points are inserted by a partition-based B^＋-tree. Thus, given a query point, its κ-NN search in high-dimensional spaces is transformed into the search in the single dimensional space with the aid of CDT index. Extensive performance studies are conducted to evaluate the effectiveness and efficiency of the proposed scheme. Our results show that this method outperforms the state-of-the-art high-dimensional search techniques, such as the X-Tree, VA-file, iDistance and NB-Tree.     

Exact bootstrap <Emphasis Type="Italic">k</Emphasis>-nearest neighbor learners

Bootstrap aggregation, or bagging, is a method of reducing the prediction error of a statistical learner. The goal of bagging is to construct a new learner which is the expectation of the original learner with respect to the empirical distribution function. In nearly all cases, the expectation cannot be computed analytically, and bootstrap sampling is used to produce an approximation. The k-nearest neighbor learners are exceptions to this generalization, and exact bagging of many k-nearest neighbor learners is straightforward. This article presents computationally simple and fast formulae for exact bagging of k-nearest neighbor learners and extends exact bagging methods from the conventional bootstrap sampling (sampling n observations with replacement from a set of n observations) to bootstrap sub-sampling schemes (with and without replacement). In addition, a partially exact k-nearest neighbor regression learner is developed. The article also compares the prediction error associated with elementary and exact bagging k-nearest neighbor learners, and several other ensemble methods using a suite of publicly available data sets.     

<Emphasis Type="Italic">FC</Emphasis>-normal and extended stratified logic program

This paper investigates the consistency property ofFC-normal logic program and presents an equivalent deciding condition whether a logic programP is anFC-normal program. The deciding condition describes the characterizations ofFC-normal program. By the Petri-net presentation of a logic program, the characterizations of stratification ofFC-normal program are investigated. The stratification ofFC-normal program motivates us to introduce a new kind of stratification, extended stratification, over logic program. It is shown that an extended (locally) stratified logic program is anFC-normal program. Thus, an extended (locally) stratified logic program has at least one stable model. Finally, we have presented algorithms about computation of consistency property and a few equivalent deciding methods of the finiteFC-normal program.     

Taut-String Algorithm and Regularization Programs with <Emphasis Type="Italic">G</Emphasis>-Norm Data Fit

In this paper we derive a unified framework for the taut-string algorithm and regularization with G-norm data fit. The G-norm data fit criterion (popularized in image processing by Y. Meyer) has been paid considerable interest in regularization models for pattern recognition. The first numerical work based on G-norm data fit has been proposed by Osher and Vese. The taut-string algorithm has been developed in statistics (Mammen and van de Geer and Davies and Kovac) for denoising of one dimensional sample data of a discontinuous function. Recently Hinterberger et al. proposed an extension of the taut-string algorithm to higher dimensional data by introducing the concept of tube methods. Here we highlight common features between regularization programs with a G-norm data fit term and taut-string algorithms (respectively tube methods). This links the areas of statistics, regularization theory, and image processing. Otmar Scherzer received his Ph.D. in Mathematics from the University of Linz, Austria, in 1990. Till 1999 he has been at the Industrial Mathematics Institute at the University of Linz. From 1999–2000 he visited the University of Munich (Germany) and from 2000–2001 he was Professor at the University of Bayreuth (Germany). Since 2001 he is Professor at the Department of Computer Science at the University of Innsbruck (Austria). From 1995 to 1996 he had an Erwin Schrödinger Scholarship of the Austrian Science Foundation (FWF) for visiting Texas A&M University and the University of Delaware (USA). Otmar Scherzer received the Award of the Austrian Mathematical Society (1998) and the START-price of the FWF in (1999). He is in the editorial board of Numerical Functional Analysis and Optimization and Inverse Problems. His research interest include image processing and inverse problems.This revised version was published online in June 2005 with correction to CoverDate     

Efficient k-Nearest-Neighbor Search Algorithms for Historical Moving Object Trajectories

κ Nearest Neighbor （κNN） search is one of the most important operations in spatial and spatio-temporal databases. Although it has received considerable attention in the database literature, there is little prior work on κNN retrieval for moving object trajectories. Motivated by this observation, this paper studies the problem of efficiently processing κNN （κ≥ 1） search on R-tree-like structures storing historical information about moving object trajectories. Two algorithms are developed based on best-first traversal paradigm, called BFPκNN and BFTκNN, which handle the κNN retrieval with respect to the static query point and the moving query trajectory, respectively. Both algorithms minimize the number of node access, that is, they perform a single access only to those qualifying nodes that may contain the final result. Aiming at saving main-memory consumption and reducing CPU cost further, several effective pruning heuristics are also presented. Extensive experiments with synthetic and real datasets confirm that the proposed algorithms in this paper outperform their competitors significantly in both efficiency and scalability.     

A simple generator for the <Emphasis Type="Italic">t</Emphasis> distribution

Summary A new algorithm for generating random variates from the t distribution is presented. It is based on a generalization of the ratio of uniforms method for the Cauchy distribution. It is simple, short and uniformly fast for all degrees of freedom.      

Ordinal,Continuous and Heterogeneous <Emphasis Type="Italic">k</Emphasis>-Anonymity Through Microaggregation

k-Anonymity is a useful concept to solve the tension between data utility and respondent privacy in individual data (microdata) protection. However, the generalization and suppression approach proposed in the literature to achieve k-anonymity is not equally suited for all types of attributes: (i) generalization/suppression is one of the few possibilities for nominal categorical attributes; (ii) it is just one possibility for ordinal categorical attributes which does not always preserve ordinality; (iii) and it is completely unsuitable for continuous attributes, as it causes them to lose their numerical meaning. Since attributes leading to disclosure (and thus needing k-anonymization) may be nominal, ordinal and also continuous, it is important to devise k-anonymization procedures which preserve the semantics of each attribute type as much as possible. We propose in this paper to use categorical microaggregation as an alternative to generalization/suppression for nominal and ordinal k-anonymization; we also propose continuous microaggregation as the method for continuous k-anonymization. Editor: Geoff Webb