On the “dimensionality curse” and the“self-similarity blessing”

Spatial queries in high-dimensional spaces have been studied extensively. Among them, nearest neighbor queries are important in many settings, including spatial databases (Find the k closest cities) and multimedia databases (Find the k most similar images). Previous analyses have concluded that nearest-neighbor search is hopeless in high dimensions due to the notorious “curse of dimensionality”. We show that this may be overpessimistic. We show that what determines the search performance (at least for R-tree-like structures) is the intrinsic dimensionality of the data set and not the dimensionality of the address space (referred to as the embedding dimensionality). The typical (and often implicit) assumption in many previous studies is that the data is uniformly distributed, with independence between attributes. However, real data sets overwhelmingly disobey these assumptions; rather, they typically are skewed and exhibit intrinsic (“fractal”) dimensionalities that are much lower than their embedding dimension, e.g. due to subtle dependencies between attributes. We show how the Hausdorff and Correlation fractal dimensions of a data set can yield extremely accurate formulas that can predict the I/O performance to within one standard deviation on multiple real and synthetic data sets     

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.     

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

An Augmented Lagrangian Method for <Emphasis Type="Italic">TV</Emphasis><Subscript><Emphasis Type="Italic">g</Emphasis></Subscript>+<Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>-norm Minimization

In this paper, the minimization of a weighted total variation regularization term (denoted TV _g ) with L ¹ norm as the data fidelity term is addressed using the Uzawa block relaxation method. The unconstrained minimization problem is transformed into a saddle-point problem by introducing a suitable auxiliary unknown. Applying a Uzawa block relaxation method to the corresponding augmented Lagrangian functional, we obtain a new numerical algorithm in which the main unknown is computed using Chambolle projection algorithm. The auxiliary unknown is computed explicitly. Numerical experiments show the availability of our algorithm for salt and pepper noise removal or shape retrieval and also its robustness against the choice of the penalty parameter. This last property is useful to attain the convergence in a reduced number of iterations leading to efficient numerical schemes. The specific role of the function g in TV _g is also investigated and we highlight the fact that an appropriate choice leads to a significant improvement of the denoising results. Using this property, we propose a whole algorithm for salt and pepper noise removal (denoted UBR-EDGE) that is able to handle high noise levels at a low computational cost. Shape retrieval and geometric filtering are also investigated by taking into account the geometric properties of the model.     

Stability‐ and performance‐robustness tradeoffs: MIMO mixed‐µ vs complex‐µ design

We present a non‐trivial case study designed to highlight some of the practical issues that arise when using mixed‐µ or complex‐µ robust synthesis methodologies. By considering a multi‐input multi‐output three‐cart mass–spring–dashpot (MSD) with uncertain parameters and dynamics, it is demonstrated that optimized performance (disturbance‐rejection) is reduced as the level of uncertainty in one or two real parameters is increased. Comparisons are made (a) in the frequency domain, (b) by RMS values of key signals and (c) in time‐domain simulations. The mixed‐µ controllers designed are shown to yield superior performance as compared with the classical complex‐µ design. The singular value decomposition analysis shows the directionality changes resulting from different uncertainty levels and from the use of different frequency weights. The nominal and marginal stability regions of the closed‐loop system are studied and discussed, illustrating how stability margins can be extended at the cost of reducing performance. Copyright © 2008 John Wiley & Sons, Ltd.     

Complementary meander‐line‐inspired dielectric resonator multiple‐input‐multiple‐output antenna for dual‐band applications

The communication presents a simple dielectric resonator (DR) multiple‐input‐multiple‐output (MIMO) dual‐band antenna. It utilizes two “I”‐shaped DR elements to construct an “I”‐shaped DR array antenna (IDRAA) for MIMO applications. The ground plane of the antenna is defected by two spiral complementary meander lines and two circular ground slots. In the configuration, two “I”‐shaped DR elements are placed with a separation of 0.098λ. The antenna covers dual‐band frequency spectra from 3.46 to 5.37 GHz (43.26%) and from 5.89 to 6.49 GHz (9.7%). It ensures the C‐band downlink (3.7‐4.2 GHz), uplink (5.925‐6.425 GHz), and WiMAX (5.15‐5.35 GHz) frequency bands. Each DR element is excited with a 50‐Ω microstrip line feed with aperture‐coupling mechanism. The antenna offers very high port isolation of around 18.5 and 20 dB in the lower band and upper band, respectively. The proposed structure is suitable to operate in the MIMO system because of its very nominal envelope correlation coefficient (<0.015) and high diversity gain (>9.8). The MIMO antenna provides very good mean effective gain value (±0.35 dB) and low channel capacity loss (<0.35 bit/s/Hz) throughout the entire operating bands. Simulated and measured results are in good agreement and they approve the suitability of the proposed IDRAA for C‐band uplink and downlink applications and WiMAX band applications.     

Embedding OWA under preference ranking for DEA cross-efficiency aggregation: Issues and procedures

Cross-efficiency (CE) evaluation is an extension of data envelopment analysis (DEA) used for fully ranking decision-making units (DMUs). The ranking process is normally performed on the matrix of CE scores. An ultimate efficiency score is computed for each DMU through an adequate amalgamation process. The preference ranking approach can be seen as an amalgamation technique based on the rank orders of the CE scores. In this paper, we review this approach by putting more emphasis on the aggregation aspect. We highlight the zero vote issue and we show that the latter has been neglected in the extant aggregation procedures. Consequently, we develop two ordered weighted averaging (OWA)-based procedures that attempt to meet effectively the requirements of an aggregation mechanism while exploiting the positive properties of the preference-ranking approach. The merits of the proposed procedures are evaluated on a sample of manufacturing systems by considering, for OWA weights generation, different OWA models with different orness degrees.     

View selection for <Emphasis Type="Italic">real</Emphasis> conjunctive queries

Given a query workload, a database and a set of constraints, the view-selection problem is to select views to materialize so that the constraints are satisfied and the views can be used to compute the queries in the workload efficiently. A typical constraint, which we consider in the present work, is to require that the views can be stored in a given amount of disk space. Depending on features of SQL queries (e.g., the DISTINCT keyword) and on whether the database relations on which the queries are applied are sets or bags, the queries may be computed under set semantics, bag-set semantics, or bag semantics. In this paper we study the complexity of the view-selection problem for conjunctive queries and views under these semantics. We show that bag semantics is the “easiest to handle” (we show that in this case the decision version of view selection is in NP), whereas under set and bag-set semantics we assume further restrictions on the query workload (we only allow queries without self-joins in the workload) to achieve the same complexity. Moreover, while under bag and bag-set semantics filtering views (i.e., subgoals that can be dropped from the rewriting without impacting equivalence to the query) are practically not needed, under set semantics filtering views can reduce significantly the query-evaluation costs. We show that under set semantics the decision version of the view-selection problem remains in NP only if filtering views are not allowed in the rewritings. Finally, we investigate whether the cgalg algorithm for view selection introduced in Chirkova and Genesereth (Linearly bounded reformulations of conjunctive databases, pp. 987–1001, 2000) is suitable in our setting. We prove that this algorithm is sound for all cases we examine here, and that it is complete under bag semantics for workloads of arbitrary conjunctive queries and under bag-set semantics for workloads of conjunctive queries without self-joins. Rada Chirkova’s work on this material has been supported by the National Science Foundation under Grant No. 0307072. The project is co-funded by the European Social Fund (75%) and National Resources (25%)- Operational Program for Educational and Vocational Training II (EPEAEK II) and particularly the program PYTHAGORAS. A preliminary version of this paper appears in F. Afrati, R. Chirkova, M. Gergatsoulis, V. Pavlaki. Designing Views to Efficiently Answer Real SQL Queries. In Proc. of SARA 2005, LNAI Vol. 3607, pages 332-346, Springer-Verlag, 2005.     

Development of flexible displays using back‐channel‐etched In–Sn–Zn–O thin‐film transistors and air‐stable inverted organic light‐emitting diodes

We developed flexible displays using back‐channel‐etched In–Sn–Zn–O (ITZO) thin‐film transistors (TFTs) and air‐stable inverted organic light‐emitting diodes (iOLEDs). The TFTs fabricated on a polyimide film exhibited high mobility (32.9 cm²/Vs) and stability by utilization of a solution‐processed organic passivation layer. ITZO was also used as an electron injection layer (EIL) in the iOLEDs instead of conventional air‐sensitive materials. The iOLED with ITZO as an EIL exhibited higher efficiency and a lower driving voltage than that of conventional iOLEDs. Our approach of the simultaneous formation of ITZO film as both of a channel layer in TFTs and of an EIL in iOLEDs offers simple fabrication process.     

Computer Anxiety: “Trait” or “State”?

A recurring question in the study of computer anxiety is whether computer anxiety is a relatively stable personality trait or a mutable, temporary state. The two studies reported examined this question in two groups of first year psychology students. These students were requested to complete a computer anxiety test, a trait anxiety test, and a state anxiety test. Some groups were administered the tests in a pen and paper format, while others were tested using computerized tests. In the first study, a Dutch version of the Profile of Mood States (POMS) was used; in the second study, a Dutch adaptation of the State-Trait Anxiety Inventory (STAI). The data were analyzed using structural equation modeling. In both studies, computer anxiety turned out to be related more strongly to trait anxiety than to state anxiety. In fact, there was no relationship between computer anxiety and state anxiety in the pen and paper format. In the computerized versions however, computer anxiety and state anxiety were related, suggesting that state anxiety in situations involving a computer is caused by pre-existing computer anxiety.     

Image Compression and Reconstruction Using pi<Subscript><Emphasis Type="Italic">t</Emphasis></Subscript>-Sigma Neural Networks

A high-order feedforward neural architecture, called pi _t -sigma (π _t σ) neural network, is proposed for lossy digital image compression and reconstruction problems. The π _t σ network architecture is composed of an input layer, a single hidden layer, and an output layer. The hidden layer is composed of classical additive neurons, whereas the output layer is composed of translated multiplicative neurons (π _t -neurons). A two-stage learning algorithm is proposed to adjust the parameters of the π _t σ network: first, a genetic algorithm (GA) is used to avoid premature convergence to poor local minima; in the second stage, a conjugate gradient method is used to fine-tune the solution found by GA. Experiments using the Standard Image Database and infrared satellite images show that the proposed π _t σ network performs better than classical multilayer perceptron, improving the reconstruction precision (measured by the mean squared error) in about 56%, on average.     

RWBO（pd, w）： A Novel Backoff Algorithm for IEEE 802.11 DCF

The Probability Distribution of Slot Selection (PDoSS) of IEEE 802.11 DCF is extremely uneven, which makes the packet collision probability very high. In this paper, the authors explore how to make the stations select the slots uniformly, and give an RWBO(pd,w) algorithm for 802.11 DCF to make the PDoSS even and decrease the packet collision probability. A Markov model is given to analyze the PDoSS of RWBO(pa, w). The performance of RWBO(pd, w) is evaluated by simulation in terms of saturation throughput and packet collision probability. The simulation results indicate that RWBO(pa, w) can decrease the packet contention probability to a large extent, and utilize the channel more efficiently as compared to the 802.11 DCF. Moreover, the relation between saturation throughput and walking probability (pd), the relation between saturation throughput and contention windows (w), the relation between packet collision probability and walking probability (pal), and the relation between packet collision probability and contention windows (w) are analyzed. The analysis indicates that RWBO(pd, w) has some remarkable features: its saturation throughout keeps high and packet collision probability keeps very low (under 0.1) in a large range of pd and w, which allow users to configure Pd and w more flexibly.     

Efficient Algorithms for Integer Programs with Two Variables per Constraint<Superscript><Emphasis Type="Italic">1</Emphasis></Superscript>

Given a bounded integer program with n variables and m constraints, each with two variables, we present an O(mU) time and O(m) space feasibility algorithm, where U is the maximal variable range size. We show that with the same complexity we can find an optimal solution for the positively weighted minimization problem for monotone systems. Using the local-ratio technique we develop an O(nmU) time and O(m) space 2 -approximation algorithm for the positively weighted minimization problem for the general case. We further generalize all results to nonlinear constraints (called axis-convex constraints ) and to nonlinear (but monotone) weight functions. Our algorithms are not only better in complexity than other known algorithms, but also considerably simpler, and they contribute to the understanding of these very fundamental problems. Received June 21, 1996; revised December 5, 1997.     

Metasurface‐based low‐profile high‐gain substrate‐integrated Fabry‐Pérot cavity antenna

A metasurface‐based substrate integrated Fabry‐Pérot cavity (FPC) antenna is presented for improved radiation performance associated with the low profile. A novel partially reflective planar (PRS) artificial magnetic conductor (AMC) structure is proposed as the upper reflector of the substrate integrated FP resonant cavity. A microstrip patch antenna is embedded inside the cavity as a feed. The proposed antenna is designed to operate at 9.35 GHz with the maximum realized gain of 14.2 dBi and the overall profile of λ₀/10 (λ₀ is the operating wavelength in free space). The low‐profile performance of the proposed design outperforms any previous substrate‐integrated FPC antenna design with this gain performance. The influences of the FP cavity on the reduction of the antenna profile and the enhancement of the antenna gain are also investigated. Good agreement between the measured and simulated results validates the feasibility of the analysis and design approach.     

Pre-compensator selection for <Emphasis Type="Italic">H</Emphasis><Subscript>∞</Subscript> loop shaping control

In this paper, an attempt has been made to address on the design of pre-compensator to obtain the solution of H _∞ loop-shaping control problem. Two different design techniques have been proposed where the first one is based on singular value decomposition (SVD) technique along with the matrix perturbation approach; the other one is focused in linear matrix inequality (LMI) framework leading to minimize the condition number of the pre-compensator that, in turn, reduces loop deterioration. A numerical example has been considered to illustrate the effectiveness of the proposed method.     

High‐transmittance in‐plane‐switching liquid‐crystal displays using a positive‐dielectric‐anisotropy liquid crystal

Abstract— The in‐plane‐switching (IPS) mode exhibits an inherently wide viewing angle and has been widely used for liquid‐crystal‐display (LCD) TVs. However, its transmittance is limited to ～76% compared to that of a twisted‐nematic (TN) cell if a positive‐dielectric‐anisotropy LC is employed. A special electrode configuration that fuses the switching mechanism of the conventional IPS and the fringe‐field switching (FFS) to boost the transmittance to ～90% using a positive LC has been developed. The new mode exhibits an equally wide viewing angle as the IPS and FFS modes.     

Nonblocking <Emphasis Type="Italic">k</Emphasis>-Compare-Single-Swap

The current literature offers two extremes of nonblocking software synchronization support for concurrent data structure design: intricate designs of specific structures based on single-location operations such as compare-and-swap (CAS), and general-purpose multilocation transactional memory implementations. While the former are sometimes efficient, they are invariably hard to extend and generalize. The latter are flexible and general, but costly. This paper aims at a middle ground: reasonably efficient multilocation operations that are general enough to reduce the design difficulties of algorithms based on CAS alone. We present an obstruction-free implementation of an atomic k -location-compare single-location-swap (KCSS) operation. KCSS allows for simple nonblocking manipulation of linked data structures by overcoming the key algorithmic difficulty in their design: making sure that while a pointer is being manipulated, neighboring parts of the data structure remain unchanged. Our algorithm is efficient in the common uncontended case: A successful k-location KCSS operation requires only two CAS operations, two stores, and 2k noncached loads when there is no contention. We therefore believe our results lend themselves to efficient and flexible nonblocking manipulation of list-based data structures in today’s architectures. A preliminary version of this paper appeared in the Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 314–323, San Diego, California, USA, 2003.     

A viewing‐angle‐controllable blue‐phase liquid‐crystal display

Abstract— A viewing‐angle‐controllable liquid‐crystal display (LCD) is proposed. When the device is only driven by an in‐plane electric field, it exhibits a wide‐viewing‐angle (WVA) mode. And it exhibits narrow‐viewing‐angle (NVA) mode when it is driven by a vertical electric field as well as an in‐plane electric field. In this manner, the viewing angle of the device can be controlled from 100° to 30°. The device exhibits a good viewing‐angle‐controlling characteristic and high transmittance.     

MAX-SNP hardness of MIN-PC and MASC-GP(<Emphasis Type="Italic">n</Emphasis>) problems

It is known that the problem on the minimal covering of a finite number of points in a plane by a set of straight lines (MIN-PC) and the problem on the minimal affine separating committee formulated in a fixed dimension space within n > 1 (MASC-GP(n)) are NP-hard in the strong sense. In the present work, it is shown that these problems are MAX-SNP-hard.     

The “runs” conjecture

The “runs” conjecture, proposed by Kolpakov and Kucherov (1999) [7], states that the number of occurrences of maximal repetitions (runs) in a string of length n, runs(n), is at most n. We almost solve the conjecture by proving that runs(n)?1.029n. This bound is obtained using a combination of theory and computer verification.