The Computational Complexity of Some Julia Sets

Numerous computer programs have been written to compute sets of points which approximate Julia sets [4]. Usually, no error estimations are added so that it remains unclear, how good such approximations are. Furthermore, high precision pictures are unreliable because of rounding errors, since the realizing computer programs use fixed length floating point numbers. Computable error estimation w.r.t. the Hausdorff metric d_H means that the set is recursive [10]. Many Julia sets J are recursive [11]. Recursive compact subsets of the Euclidean plane have a computable Turing machine time complexity [10]. In this paper we prove that the Julia set of a complex function f(z) = z² + c for c < 1/4 can be computed locally in time O(k²M(k)) (where M(k) is a time bound for multiplication of k-bit integers). Roughly speaking, the local time complexity is the number of Turing machine steps to decide for a single point whether it belongs to a grid K_k (2^−k · )² such that d_H(K_k,J) ≤ = 2^−k.     

A Dynamic k-Nearest Neighbor Method for WLAN-Based Positioning Systems

The static k-Nearest Neighbor (k-NN) method for localization has limitations in accuracy due to the fixed k value in the algorithm. To address this problem, and achieve better accuracy, we propose a new dynamic k-Nearest Neighbor (Dk-NN) method in which the optimal k value changes based on the topologies and distances of its nearest neighbors. The proposed method has been validated using the WLAN-fingerprint data sets collected at COEX, one of the largest convention centers in Seoul, Korea. The proposed method significantly reduced both the mean error distances and the standard deviations of location estimations, leading to a significant improvement in accuracy by ~ 23% compared to the cluster filtered k-NN (CFK) method, and ~ 17% compared to the k-NN (k = 1) method.     

Visualizing the Stability of 2D Point Sets from Dimensionality Reduction Techniques

We use k-order Voronoi diagrams to assess the stability of k-neighbourhoods in ensembles of 2D point sets, and apply it to analyse the robustness of a dimensionality reduction technique to variations in its input configurations. To measure the stability of k-neighbourhoods over the ensemble, we use cells in the k-order Voronoi diagrams, and consider the smallest coverings of corresponding points in all point sets to identify coherent point subsets with similar neighbourhood relations. We further introduce a pairwise similarity measure for point sets, which is used to select a subset of representative ensemble members via the PageRank algorithm as an indicator of an individual member's value. The stability information is embedded into the k-order Voronoi diagrams of the representative ensemble members to emphasize coherent point subsets and simultaneously indicate how stable they lie together in all point sets. We use the proposed technique for visualizing the robustness of t-distributed stochastic neighbour embedding and multi-dimensional scaling applied to high-dimensional data in neural network layers and multi-parameter cloud simulations.     

The <Emphasis Type="Italic">k</Emphasis>-Nearest Neighbour Join: Turbo Charging the KDD Process

The similarity join has become an important database primitive for supporting similarity searches and data mining. A similarity join combines two sets of complex objects such that the result contains all pairs of similar objects. Two types of the similarity join are well-known, the distance range join, in which the user defines a distance threshold for the join, and the closest pair query or k-distance join, which retrieves the k most similar pairs. In this paper, we propose an important, third similarity join operation called the k-nearest neighbour join, which combines each point of one point set with its k nearest neighbours in the other set. We discover that many standard algorithms of Knowledge Discovery in Databases (KDD) such as k-means and k-medoid clustering, nearest neighbour classification, data cleansing, postprocessing of sampling-based data mining, etc. can be implemented on top of the k-nn join operation to achieve performance improvements without affecting the quality of the result of these algorithms. We propose a new algorithm to compute the k-nearest neighbour join using the multipage index (MuX), a specialised index structure for the similarity join. To reduce both CPU and I/O costs, we develop optimal loading and processing strategies.     

On constructing disjoint linear codes

To produce a highly nonlinear resilient function, the disjoint linear codes were originally proposed by Johansson and Pasalic in IEEE Trans. Inform. Theory, 2003, 49(2): 494–501. In this paper, an effective method for finding a set of such disjoint linear codes is presented. When n ⩾ 2k, we can find a set of [n,k]disjoint linear codes with cardinality 2^n-k +⌊(n-k)/k⌊; When n < 2k, no set of disjoint linear codes exists with cardinality at least 2. We also describe a result on constructing a set of [n, k] disjoint linear codes with minimum distance at least some fixed positive integer.     

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

On sets turing reducible to p-selective sets

We consider sets Turing reducible to p-selective sets under various resource bounds and a restricted number of queries to the oracle. We show that there is a hierarchy among the sets polynomial-time Turing reducible to p-selective sets with respect to the degree of a polynomial bounding the number of adaptive queries used by a reduction. We give a characterization of EXP/poly in terms of exponential-time Turing reducibility to p-selective sets. Finally we show that EXP cannot be reduced to the p-selective sets under 2 ^lin time reductions with at mostn ^k queries for anyfixed k ε N.     

A linear-time algorithm to construct a rectilinear Steiner minimal tree fork-extremal point sets

Ak-extremal point set is a point set on the boundary of ak-sided rectilinear convex hull. Given ak-extremal point set of sizen, we present an algorithm that computes a rectilinear Steiner minimal tree in timeO(k ⁴ n). For constantk, this algorithm runs inO(n) time and is asymptotically optimal and, for arbitraryk, the algorithm is the fastest known for this problem.     

带间隔约束的Top-k对比序列模式挖掘

对比序列模式能够表达序列数据集合间的差异,在商品推荐、用户行为分析和电力供应预测等领域有广泛的应用.已有的对比序列模式挖掘算法需要用户设定正例支持度阈值和负例支持度阈值.在不具备足够先验知识的情况下,用户难以设定恰当的支持度阈值,从而可能错失一些对比显著的模式.为此,提出了带间隔约束的top-k对比序列模式挖掘算法kDSP-Miner(top-k distinguishing sequential patterns with gap constraint miner).kDSP-Miner中用户只需设置期望发现的对比最显著的模式个数,从而避免了直接设置对比支持度阈值.相应地,挖掘算法更容易使用,并且结果更易于解释.同时,为了提高算法执行效率,设计了若干剪枝策略和启发策略.进一步设计了kDSP-Miner的多线程版本,以提高其对高维序列元素情况的处理能力.通过在真实世界数据集上的详实实验,验证了算法的有效性和执行效率.     

A new approach for online multiobjective optimization of mechatronic systems

We present a new concept for online multiobjective optimization and its application to the optimization of the operating point assignment for a doubly-fed linear motor. This problem leads to a time-dependent multiobjective optimization problem. In contrast to classical optimization where the aim is to find the (global) minimum of a single function, we want to simultaneously minimize k objective functions. The solution to this problem is given by the set of optimal compromises, the so-called Pareto set. In the case of the linear motor, there are two conflicting aims which both have to be maximized: the degree of efficiency and the inverter utilization factor. The objective functions depend on velocity, force and power, which can be modeled as time-dependent parameters. For a fixed point of time, the entire corresponding Pareto set can be computed by means of a recently developed set-oriented numerical method. An online computation of the time-dependent Pareto sets is not possible, because the computation itself is too complex. Therefore, we combine the computation of the Pareto set with numerical path following techniques. Under certain smoothness assumptions the set of Pareto points can be characterized as the set of zeros of a certain function. Here, path following allows to track the evolution of a given solution point through time.     

Computing small partial coverings

We study the generalization of covering problems such as the set cover problem to partial covering problems. Here we only want to cover a given number k of elements rather than all elements. For instance, in the k-partial (weighted) set cover problem, we wish to compute a minimum weight collection of sets that covers at least k elements. As a main result, we show that the k-partial set cover problem and its special cases like the k-partial vertex cover problem are all fixed parameter tractable (with parameter k). As a second example, we consider the minimum weight k-partial t-restricted cycle cover problem.     

Minimum polygonal separation

In this paper we study the problem of polygonal separation in the plane, i.e., finding a convex polygon with minimum number k of sides separating two given finite point sets (k-separator), if it exists. We show that for k = Θ(n), Ω(n log n) is a lower bound to the running time of any algorithm for this problem, and exhibit two algorithms of distinctly different flavors. The first relies on an O(n log n)-time preprocessing task, which constructs the convex hull of the internal set and a nested star-shaped polygon determined by the external set; the k-separator is contained in the annulus between the boundaries of these two polygons and is constructed in additional linear time. The second algorithm adapts the prune-and-search approach, and constructs, in each iteration, one side of the separator; its running time is O(kn), but the separator may have one more side than the minimum.     

Pattern classification based on k locally constrained line

A simple yet effective learning algorithm, k locally constrained line (k-LCL), is presented for pattern classification. In k-LCL, any two prototypes of the same class are extended to a constrained line (CL), through which the representational capacity of the training set is largely improved. Because each CL is adjustable in length, k-LCL can well avoid the “intersecting” of training subspaces in most traditional feature classifiers. Moreover, to speed up the calculation, k-LCL classifies an unknown sample focusing only on its local CLs in each class. Experimental results, obtained on both synthetic and real-world benchmark data sets, show that the proposed method has better accuracy and efficiency than most existing feature line methods.     

A Restricted Second Order Logic for Finite Structures

We introduce a restricted version of second order logic SO^ωin which the second order quantifiers range over relations that are closed under the equivalence relation ≡^kofkvariable equivalence, for somek. This restricted second order logic is an effective fragment of the infinitary logicL^ω_∞ω, but it differs from other such fragments in that it is not based on a fixed point logic. We explore the relationship of SO^ωwith fixed point logics, showing that its inclusion relations with these logics are equivalent to problems in complexity theory. We also look at the expressibility of NP-complete problems in this logic.     

High-dimensional kNN joins with incremental updates

The k Nearest Neighbor (kNN) join operation associates each data object in one data set with its k nearest neighbors from the same or a different data set. The kNN join on high-dimensional data (high-dimensional kNN join) is a very expensive operation. Existing high-dimensional kNN join algorithms were designed for static data sets and therefore cannot handle updates efficiently. In this article, we propose a novel kNN join method, named kNNJoin ⁺, which supports efficient incremental computation of kNN join results with updates on high-dimensional data. As a by-product, our method also provides answers for the reverse kNN queries with very little overhead. We have performed an extensive experimental study. The results show the effectiveness of kNNJoin⁺ for processing high-dimensional kNN joins in dynamic workloads.     

Strong convergence theorems for a new iterative method of -strictly pseudo-contractive mappings in Hilbert spaces

In this paper, we introduce a new iterative method of a k-strictly pseudo-contractive mapping for some 0≤k<1 and prove that the sequence {x_n} converges strongly to a fixed point of T, which solves a variational inequality related to the linear operator A. Our results have extended and improved the corresponding results of Y.J. Cho, S.M. Kang and X. Qin [Some results on k-strictly pseudo-contractive mappings in Hilbert spaces, Nonlinear Anal. 70 (2008) 1956–1964], and many others.     

A Fast Algorithm for k-Nearest Neighbor Problem on a Reconfigurable Mesh Computer

Given a set S of m points stored on a reconfigurable mesh computer of size n×n, one point per processing element (PE). In this paper we present a parallel method for solving the k-Nearest Neighbor problem (k-NN). This method permits each point of S to know its k-NN (0<k<m). The corresponding algorithm requires that each PE must have 2k registers where it stores the (x,y) coordinates of its k-NN in a given order. This algorithm has a complexity of O(logh+k ²) times, where h is a maximal number of points within a row of the mesh. This complexity is reduced to O(k ²) times, using an appropriate procedure which demonstrates the power of the reconfiguration operations carried out by the processors, and the polymorphic properties of the mesh.     

Generalised Stream X-Machines and Cooperating Distributed Grammar Systems

Stream X-machines are a general and powerful computational model. By coupling the control structure of a stream X-machine with a set of formal grammars a new machine called a generalised stream X-machine with underlying distributed grammars, acting as a translator, is obtained. By introducing this new mechanism a hierarchy of computational models is provided. If the grammars are of a particular class, say regular or context-free, then finite sets are translated into finite sets, when ?k, = k derivation strategies are used, and regular or context-free sets, respectively, are obtained for ?k, * and terminal derivation strategies. In both cases, regular or context-free grammars, the regular sets are translated into non-context-free languages. Moreover, any language accepted by a Turing machine may be written as a translation of a regular set performed by a generalised stream X-machine with underlying distributed grammars based on context-free rules, under = k derivation strategy. On the other hand the languages generated by some classes of cooperating distributed grammar systems may be obtained as images of regular sets through some X-machines with underlying distributed grammars. Other relations of the families of languages computed by generalised stream X-machines with the families of languages generated by cooperating distributed grammar systems are established. At the end, an example dealing with the specification of a scanner system illustrates the use of the introduced mechanism as a formal specification model. Received September 1999 / Accepted in revised form October 2000     

Linear Transformation Groups and Shape Space

The problem of modelling variabilities of ensembles of objects leads to the study of the shape of point sets and of transformations between point sets. Linear models are only able to amply describe variabilities between shapes that are sufficiently close and require the computation of a mean configuration. Olsen and Nielsen (2000) introduced a Lie group model based on linear vector fields and showed that this model could describe a wider range of variabilities than linear models. The purpose of this paper is to investigate the mathematics of this Lie group model further and determine its expressibility. This is a necessary foundation for any future work on inference techniques in this model.Let ^k _m denote Kendall's shape space of sets of k points in m-dimensional Euclidean space (k > m): this consists of point sets up to equivalence under rotation, scaling and translation. Not all linear transformations on point sets give well-defined transformations of shapes. However, we show that a subgroup of transformations determined by invertible real matrices of size k – 1 does act on ^k _m. For m > 2, this group is maximal, whereas for m = 2, the maximal group consists of the invertible complex matrices. It is proved that these groups are able to transform any generic shape to any other. Moreover, we establish that for k > m + 1 this may be done via one-parameter subgroups. Each one-parameter subgroup is given by exponentiation of an arbitrary (k – 1) × (k – 1) matrix. Shape variabilities may thus be modelled by elements of a (k – 1)²-dimensional vector space.     

Structured squaring down and zero assignment

The problem of zero assignment by squaring down is considered for a system of p-inputs, n-outputs and n-states (m?>?p), where not all outputs are free variables for design. We consider the case where a k-subset of outputs is preserved in the new output set, and the rest are recombined to produce a total new set of p-outputs. New invariants for the problem are introduced which include a new class of fixed zeros and the methodology of the global linearization, developed originally for the output feedback pole assignment problem, is applied to this restricted form of the squaring down problem. It is shown that the problem can be solved generically if (p???k)(m???p)?>?δ*, where k (k?p) is the number of fixed outputs and δ* is a system and compensation scheme invariant, which is defined as the restricted Forney degree.