Зарубежная периодика по тематике ИПИ РАН
Выпуск № 2, июнь 2006 г.
Материалы подготовлены лаб. 13
Журнал IEEE Transactions on Automatic Control
Jan2005, Vol. 50 Issue 1
Труды Института Инженеров по Электротехнике и Электронике (США)
«Автоматическое управление»
Том 50, вып. 1 (Январь 2005 г.)
СТАТЬИ
1. Нелинейная нормированная по входу реализация, основанная на дифференциальной собственной структуре операторов Ханкеля.
Nonlinear Input-Normal Realizations. Based on the Differential Eigenstructure of Hankel : Fujimoto, Kenji; Scherpen, Jacquelien M. A.. p2-18, 17p
Ключевые слова: NONLINEAR systems, PARAMETE estimation, PROBABILITIES, STOCHASTIC processes, STOCHASTIC systems, SYSTEM analysis
Abstract: We study the problem of globally stabilizing through measurement feedback a class of uncertain stochastic nonlinear systems in feedforward (or upper triangular) form, with state equations affected by a Wiener process adapted to a given filtration of σ-algebras and measurements affected by a sample continuous and strongly Markov stochastic process adapted to the same filtration of σ-algebras. We propose a step-by step design, based on splitting the system Σ into one-dimensional interconnected systems Σ<sub>j</sub>, j = 1,…, n. Moreover, we introduce the notion of practical stability in probability, which corresponds to having a large probability of being the state small in norm whenever the noise affecting the measurements has a "small" second order moment. [ABSTRACT FROM AUTHOR]
2. Управление с прогнозированием и оценкой в Гамильтониановских системах. Часть 1. Матрица решений ARE в длящемся времени.
H∞ Control and Estimation With Preview -- Part 1: Matrix ARE Solutions in Continuous : Tadmor, Gilead; Mirkin, Leonid. p19-28, 10p
Ключевые слова: DIFFERENTIABLE dynamical systems, DIFFERENTIAL equations, GAME theory, HAMILTON-Jacobi equations, HAMILTONIAN systems, LINEAR systems.
Abstract: Preview control and fixed-lag smoothing allow a non-causal component in the controller/estimator. Time domain variational analysis is used in a reduction to an open loop differential game, leading to a complete, necessary and sufficient characterization of suboptimal values and an explicit state space design, in terms of a parameterized (nonstandard) algebraic matrix Riccati equation in a general continuous time linear system setting. The solution offers insight into the appropriate structure of the associated Hamiltonian, where the state and co-state are not the usual state of the original dynamic system and that of its adjoint. Rather, the state and co-state are selected to capture the respective lumped effects of Initial data and future input selection in the allied game. [ABSTRACT FROM AUTHOR]
3. Управление с прогнозированием и оценкой в Гамильтониановских системах. Часть 2. Решения ARE фиксированного размера в дискретном времени.
H∞ Control and Estimation With Preview -- Part II: Fixed-Size ARE Solutions in Discrete : Tadmor, Gilead; Mirkin, Leonid. p29-40, 12p
Ключевые слова: DIFFERENTIAL equations, GAME theory, LINEAR systems, LINEAR time invariant systems, NUMERICAL analysis, RICCATI equation.
Abstract: H<sup>∞</sup> preview control and fixed-lag smoothing problems are solved in general discrete time linear systems, via a reduction to equivalent open-loop differential games. To prevent high order Riccati equations, found in some solutions, the state of the Hamilton--Jacobi system resides in a quotient space of an auxiliary extended state space system. The dimension of that auxiliary space is equal to the state space dimension of the original system (ignoring the delay). [ABSTRACT FROM AUTHOR]
4. Обобщенная лемма Калмана - Якубовича-Попова: неравенства для унифицированного частотного домена
Generalized KYP Lemma: Unified Frequency Domain Inequalities With Design : Iwasaki, Tetsuya; Hara, Shinji. P 41-59, 19p
Ключевые слова: DIGITAL electronics, ENGINEERING -- Study & teaching, FOURIER analysis, FOURIER transformations, MACHINE theory, SYSTEM analysis.
Abstract: The celebrated Kalman--Yakubovič--Popov (KYP) lemma establishes the equivalence between a frequency domain inequality (FDI) and a linear matrix inequality, and has played one of the most fundamental roles in systems and control theory. This paper first develops a necessary and sufficient condition for an S-procedure to be lossless, and uses the result to generalize the KYP lemma in two aspects--the frequency range and the class of systems--and to unify various existing versions by a single theorem. In particular, our result covers FDIs in finite frequency intervals for both continuous/discrete-tune settings as opposed to the standard infinite frequency range. The class of systems for which FDIs are considered is no longer constrained to be proper, and nonproper transfer functions including polynomials can also be treated. We study implications of this generalization, and develop a proper interface between the basic result and various engineering applications. Specifically, it is shown that our result allows us to solve a certain class of system design problems with multiple specifications on the gain/phase properties in several frequency ranges. The method is illustrated by numerical design examples of digital filters and proportional-integral-derivative controllers. [ABSTRACT FROM AUTHOR]
5. Стабилизация переходного процесса в многомашинной энергетической системе, характеризующейся нетривиальными передаточными проводимостями.
Transient Stabilization of Multimachine Power Systems With Nontrivial Transfer : Ortega, Romeo; Galaz, Martha; Astolfi, Alessandro; Sun, Yuanzhang; Shen, Tielong. p60-75, 16p
Ключевые слова: AUTOMATIC control, CONTROL theory, DIFFERENTIAL equations, ELECTRIC lines, LYAPUNOV functions, LYAPUNOV stability.
Abstract: In this paper, we provide a solution to the long-standing problem of transient stabilization of multimachine power systems with nonnegligible transfer conductances. More specifically, we consider the full 3 n-dimensional model of the n-generator system with lossy transmission lines and loads and prove the existence of a nonlinear static state feedback law for the generator excitation field that ensures asymptotic stability of the operating point with a well-defined estimate of the domain of attraction provided by a bona fide Lyapunov function. To design the control law we apply the recently introduced interconnection and damping assignment passivity-based control methodology that endows the closed-loop system with a port-controlled Hamiltonian structure with desired total energy function. The latter consists of terms akin to kinetic and potential energies, thus has a clear physical interpretation. Our derivations underscore the deleterious effects of resistive elements which, as is well known, hamper the assignment of simple "gradient" energy functions and compel us to include nonstandard cross terms. A key step in the construction is the modification of the energy transfer between the electrical and the mechanical parts of the system which is obtained via the introduction of state-modulated interconnections that play the role of multipliers in classical passivity theory. [ABSTRACT FROM AUTHOR]
6. Безопасная синхронизация класса хаотических систем по отношению к нелинейному наблюдению.
Secure Synchronization of a Class of Chaotic Systems From a Nonlinear Observer : Čelikovaský, Sergej; Guanrong Chen. p76-82, 7p
Ключевые слова: AUTOMATIC control, CONTROL theory, DISCOURSE analysis, METHODOLOGY, SYNCHRONIZATION, TIME measurements
Abstract: The aim of this note is two-fold. First, it discusses synchronization of chaotic systems from a control theoretic point of view and introduces the concept of secure synchronization, i. e., a communication scheme that resists possible intrusion based on either adaptive or robust control techniques. Second, for a large class of chaotic systems, i. e., the generalized Lorenz system, global exponential synchronization via a scalar communication signal is suggested and its security is analyzed from a control theoretic viewpoint. Both theoretical analysis and numerical simulations are provided, verifying the proposed chaos-synchronization-based secure communication design principle and methodology. [ABSTRACT FROM AUTHOR]
7. Статическая стабилизация с помощью обратной связи по выходу: необходимые условия для контроллеров с множественными задержками.
Static Output Feedback Stabilization: Necessary Conditions for Multiple Delay : Kharitonov, Vladimir L.; Niculescu, Silviu-Iulian; Moreno, Jaime; Michiels, Wim. p82-86, 5p; DOI: 10.1109/TAC.2004.841137; (AN )
Ключевые слова: ELECTRONIC analog computers, INTEGRATORS, MATHEMATICAL instruments, OSCILLATORS, Transistor, PLANIMETER
Abstract: This note focuses on the static output feedback stabilization problem for a class of single-input--single-output systems when the control law includes multiple (distinct) delays. We are interested in giving necessary conditions for the existence of such stabilizing controllers, illustrative examples (second-order system, chain of integrators, or chain of oscillators) are presented, and, discussed. [ABSTRACT FROM AUTHOR]
8. Оптимальное пороговое управление незагруженными транспортными средствами, перераспределяемыми между двумя обслуживающими депо.
Optimal Threshold Control of Empty Vehicle Redistribution in Two Depot Service : Dong-Ping Song. p87-90, 4p
Ключевые слова: CHEMICAL reactions, COST control, EXCHANGE reactions, ION exchange, TERMINALS (Transportation), TRANSPORTATION.
Abstract: In this note, we consider the empty vehicle redistribution problem in a two-depot service system with random demands and uncertain transportation times. It is shown that the optimal stationary policy is of threshold control-type when the long-run average cost is to be minimized. The explicit form of the average cost under threshold controls is presented, which can be used to calculate the optimal threshold values. The sufficient and necessary conditions for the existence of the steady-state are provided. The results are then used to construct suboptimal policies for a more realistic model. [ABSTRACT FROM AUTHOR]
9. Адаптивное слежение и подавление возмущений в нелинейных системах с неопределенными параметрами.
Adaptive Tracking and Disturbance Rejection for Uncertain Nonlinear : Marino, Riccardo; Tomei, Patrizio. p90-95, 6p
Ключевые слова: ASYMPTOTES, ASYMPTOTIC expansions, CURVES, Plane, ECONOMIC forecasting, NONLINEAR systems, SYSTEM theory
Abstract: This note addresses the problem of asymptotic tracking of arbitrary smooth bounded reference output signals, with simultaneous rejection of disturbances generated by an unknown linear exosystem. The problem is globally solved by output feedback for the class of nonlinear systems with output dependent nonlinearities and unknown linear parameters, under the assumptions that the system is minimum phase and the relative degree, an upper bound on the system order, the sign of the high-frequency gain are known. [ABSTRACT FROM AUTHOR]
10. Новые результаты по управлению, зависящему от задержки, в системах с задержкой по времени.
New Results on Delay-Dependent Control of Time-Delay Systems.
By: Mahmoud, Magdi S.; Ismail, Abdulla. p95-100, 6p
Ключевые слова: ALGEBRA, ALGEBRA, Abstract, MATRICES, MECHANICS, SPECIFICATIONS, STATICS
Abstract: This note presents new results pertaining to the delay-dependent stability and control design of a class of linear time-delay systems. A new state transformation is introduced to exhibit the delay-dependent dynamics For stability, we construct an appropriate Lyapunov functional to derive delay-dependent linear matrix inequality-based sufficient condition. For the feedback control design, we establish schemes based on quadratic H<sub>2</sub> performance, H<sub>∞</sub>, criteria and simultaneous H<sub>2</sub>/H<sub>∞</sub> synthesis. Under the developed transformation, both the instantaneous and delayed feedback control yield identical results. Numerical examples are presented to illustrate the analytical development. [ABSTRACT FROM AUTHOR]
11. Стохастическая стабилизация с упреждением в нелинейных системах при наличии шума на выходах.
Stochastic Stabilization of Nonlinear Systems in Feedforward Form With Noisy Outputs.
By: Battilotti, Stefano. p100-105, 6p
Ключевые слова: PARAMETER estimation, PROBABILITIES, STOCHASTIC processes, STOCHASTIC systems, SYSTEM analysis
Abstract: We study the problem of globally stabilizing through measurement feedback a class of uncertain stochastic nonlinear systems in feedforward (or upper triangular) form, with state equations affected by a Wiener process adapted to a given filtration of σ-algebras and measurements affected by a sample continuous and strongly Markov stochastic process adapted to the same filtration of σ-algebras. We propose a step-by step design, based on splitting the system Σ into one-dimensional interconnected systems Σ<sub>j</sub>, j = 1,…, n. Moreover, we introduce the notion of practical stability in probability, which corresponds to having a large probability of being the state small in norm whenever the noise affecting the measurements has a "small" second order moment. [ABSTRACT FROM AUTHOR]
12. Подавление эффекта «скручивания» путем гарантированной зоны стабилизации: подход, основанный на построении матрицы линейных неравенств (Linear Matrix Inequalities - LMI).
Antiwindup Design With Guaranteed Regions of Stability: An LMI-Based Approach.
By: Da Silva Jr., João Marioel Gomes; Tarbouriech, Sophie. p106-111, 6p
Ключевые слова: DIFFERENTIAL equations, DIFFERENTIAL equations, Linear, ECONOMIC forecasting, LINEAR systems, MATRICES, SYSTEM theory.
Abstract: This note addresses the design of antiwindup gains for obtaining larger regions of stability for linear systems with saturating inputs. Considering that a linear dynamic output feedback has been designed to stabilize the linear system (without saturation), a method is proposed for designing an antiwindup gain that maximizes an estimate of the basin of attraction of the closed-loop system. It is shown that the closed-loop system obtained from the controller plus the antiwindup gain can be modeled by a linear system with a deadzone nonlinearity. A modified sector condition is then used to obtain stability conditions based on quadratic Lyapunov functions. Differently from previous works these conditions are directly in linear matrix inequality form. Some numerical examples illustrate the effectiveness of the proposed design technique when compared with the previous ones. [ABSTRACT FROM AUTHOR]
13. Отслеживание обратной связи по выходу: подход, основанный на принципах разделения сигнала.
Output Feedback Tracking: A Separation Principle Approach.
By: Maggiore, Manfredi; Passino, Kevin M.. p111-117, 7p; DOI: 10.1109/TAC.2004.841126
Ключевые слова: DIFFERENTIAL equations, Linear, ECONOMIC forecasting, GEOMETRY, NONLINEAR systems, SYSTEM theory.
Abstract: We study the practical and asymptotic tracking problems for nonlinear systems when only the output of the plant and the reference signal are available for feedback. We provide sufficient conditions and a control topology yielding practical tracking. In the special case when the reference signal is generated by an exosystem and there exists an internal model satisfying suitable observability properties, tracking becomes asymptotic. [ABSTRACT FROM AUTHOR]
14. Глобальное робастное управление для систем с обратной связью по выходу.
Global Robust Output Regulation for Output Feedback Systems.
By: Zhiyong Chen; Jie Huang. p117-121, 5p
Ключевые слова: APPROXIMATION theory, EULER polynomials, HALL polynomials, NONLINEAR systems, POLYNOMIALS, SYSTEM theory.
Abstract: The global robust output regulation problem for the class of nonlinear systems in output feedback form has been studied under the assumption that the solution of the regulator equations is polynomial. This assumption essentially requires these systems contain only polynomial non-linearity and is due to the failure of finding a nonlinear internal model to account for more complex nonlinearities than polynomials. Recently, it was found that a nonlinear internal model can be constructed under some assumption much milder than the polynomial assumption. In this note, we will apply this type of internal model to solve the global robust output regulation problem for the class of nonlinear systems in output feedback form. [ABSTRACT FROM AUTHOR]
15. Необходимые и достаточные условия на сенсорном диграфе для управления образованием унициклов.
Necessary and Sufficient Graphical Conditions for Formation Control of Unicycles.
By: Zhiyun Lin; Francis, Bruce; Maggiore, Manfredi. p121-127, 7p
Ключевые слова: CYCLING, DETECTORS, ENGINEERING instruments, GRAPH theory, UNICYCLES, VEHICLES
Abstract: The feasibility problem is studied of achieving a specified formation among a group of autonomous unicycles by local distributed control. The directed graph defined by the information flow plays a key role. It is proved that formation stabilization to a point is feasible if and only if the sensor digraph has a globally reachable node. A similar result is given for formation stabilization to a line and to more general geometric arrangements. [ABSTRACT FROM AUTHOR]
16. Слежение за наземными целями при помощи измерений индикаторов движения наземных целей (GMTI) и диапазона с высоким разрешением (HRR) на основе локальных характеристик движения.
Local Motion Feature Aided Ground Moving Target Tracking With GMTI and HRR Measurements.
By: Lang Hong; Ningzhou Cui; Pronobis, Mark; Scott, Stephen. p127-133, 7p
Ключевые слова: DIAGNOSIS, Electron microscopic, ELECTRON microscopic, immunocytochemistry, ELECTRON microscopy, FRACTOGRAPHY, MICROSCOPY, HIGH resolution electron microscopy.
Abstract: Tracking ground moving targets with ground moving target indicator (GMTI) measurements only could face a potential problem of losing tracks or track mingling, if the targets move together within the range of GMTI sensing uncertainty for an extended period of time. We propose a remedy for this problem by using local motion features extracted from high resolution range (HRR) profiles to assist data association. Unlike other HRR features, the new local motion features carry both spatial and temporal information and are ideal for feature aided tracking. A probabilistic logic based tracker is developed for local motion feature aided tracking. [ABSTRACT FROM AUTHOR]
17. Обзор книги «Математика в управлении перегрузками в сетях Интернет».
The Mathematics of Internet Congestion Control -- R.
By: Derong Liu. p134-135, 2p
Ключевые слова: BOOKS – Reviews, INTERNET, NONFICTION.
Abstract: Reviews the book "The Mathematics of Internet Congestion Control-R," by R. Srikant.
Журнал IEEE Transactions on Computers
Jan 2005, Vol. 54 Issue 1
Труды Института Инженеров по Электротехнике и Электронике (США)
«Вычислительная техника»
Том 54, вып. 1 (Январь 2005 г.)
СТАТЬИ
1. Коды обнаружения ошибок: алгоритмы и оперативное использование.
Error-Detection Codes: Algorithms and Fast Implementation.
By: Nguyen, Gam D.. p1-11, 11p;
Ключевые слова: CIPHERS, COMPUTER algorithms, FORMS, Binary, COMPUTER programming, COMPUTER systems, ENCODING
Author-Supplied Keywords: Hamming code, CRC, checksum, Fast error-detection code.
Abstract: Binary CRCs are very effective for error detection, but their software implementation is not very efficient. Thus, many binary non-CRC codes (which are not as strong as CRCs, but can be more efficiently implemented in software) are proposed as alternatives to CRCs. The non-CRC codes include WSC, CXOR, one's-complement checksum, Fletcher checksum, and block-parity code. In this paper, we present a general algorithm for constructing a family of binary error-detection codes. This family is large because it contains all these non-CRC codes, CRCs, perfect codes, as well as other linear and nonlinear codes. In addition to unifying these apparently disparate codes, our algorithm also generates some non-CRC codes that have minimum distance 4 (like CRC5) and efficient software implementation. [ABSTRACT FROM AUTHOR]
2. Аппаратная реализация алгоритма для модульного умножения / деления.
A Hardware Algorithm for Modular Multiplication/Division.
By: Kaihara, Marcelo E.; Takagi, Naofumi. p12-21, 10p;
Ключевые слова: ANALOG multipliers, COMPUTER algorithms, COMPUTER input-output equipment, ELECTRONIC digital computers – Programming, INTEGRATED circuits -- Very large scale integration, MODULAR programming
Author-Supplied Keywords: hardware algorithm, modular multiplication, modular division, redundant representation, cryptography, Computer arithmetic.
Abstract: A mixed radix-4/2 algorithm for modular multiplication/division suitable for VLSI implementation is proposed. The algorithm is based on Montgomery method for modular multiplication and on the extended Binary GCD algorithm for modular division. Both algorithms are modified and combined into the proposed algorithm so that almost all the hardware components are shared. The new algorithm carries out both calculations using simple operations such as shifts, additions, and subtractions. The radix-2 signed-digit representation is used to avoid carry propagation in all additions and subtractions. A modular multiplier/divider based on the algorithm performs an n-bit modular multiplication/division in O(n) clock cycles where the length of the clock cycle is constant and independent of n. The modular multiplier/divider has a linear array structure with a bit-slice feature and can be implemented with much smaller hardware than that necessary to implement both multiplier and divider separately. [ABSTRACT FROM AUTHOR]
3. Кэш трассировки программ.
Software Trace Cache.
By: Ramirez, Alex; Larriba-Pey, Josep L.; Valero, Mateo. p22-35, 14p;
Ключевые слова: CACHE memory, CIPHERS, COMPUTER algorithms, COMPUTER storage devices, COMPUTER programming, ENCODING
Author-Supplied Keywords: instruction fetch compiler optimizations, branch prediction, trace cache, Pipeline processors
Abstract: This paper explores the use of compiler optimizations which optimize the layout of instructions in memory. The target is to enable the code to make better use of the underlying hardware resources regardless of the specific details of the processor/ architecture in order to increase fetch performance. The Software Trace Cache (STC) is a code layout algorithm with a broader target than previous layout optimizations. We target not only an improvement in the instruction cache hit rate, but also an increase in the effective fetch width of the fetch engine. The STC algorithm organizes basic blocks into chains trying to make sequentially executed basic blocks reside in consecutive memory positions, then maps the basic block chains in memory to minimize conflict misses in the important sections of the program. We evaluate and analyze in detail the impact of the STC, and code layout optimizations in general, on the three main aspects of fetch performance the instruction cache hit rate, the effective fetch width, and the branch prediction accuracy. Our results show that layout optimized codes have some special characteristics that make them more amenable for high-performance instruction fetch: They have a very high rate of not-taken branches and execute long chains of sequential instructions; also, they make very effective use of instruction cache lines, mapping only useful instructions which will execute close in time, increasing both spatial and temporal locality. [ABSTRACT FROM AUTHOR]
4. Потоки с локационной поддержкой: энергосберегающий протокол передачи данных в беспроводных сенсорных сетях.
Location-Aided Flooding: An Energy-Efficient Data Dissemination Protocol for Wireless Sensor Networks.
By: Sabbinen, Harshavardhan; Chakrabarty, Krishnendu. p36-46, 11p;
Ключевые слова: COMPUTER network protocols, DETECTORS, DIFFUSION of innovations, WIRELESS communication systems, SENSOR networks, INFORMATION dissemination
Author-Supplied Keywords: location, energy management, information dissemination, flooding, Communication protocol
Abstract: We present a new information dissemination protocol for wireless sensor networks. This protocol uses location information to reduce redundant transmissions, thereby saving energy. The sensor network is divided into virtual grids and each sensor node associates itself with a virtual grid based on its location. Sensor nodes within a virtual grid are classified as either gateway nodes or internal nodes. While gateway nodes are responsible for forwarding the data across virtual grids, internal nodes forward the data within a virtual grid. The proposed approach, termed location-aided flooding (LAF), achieves energy savings by reducing the redundant transmissions of the same packet by a node. We study the performance of LAF for different grid sizes and different node densities and compare it to other well-known methods. We show that LAF can save a significant amount of energy compared to prior methods. [ABSTRACT FROM AUTHOR]
5. Расписание позиционирования компонентно - ориентированных фазированных антенн радаров в режиме реального времени.
Real-Time Dwell Scheduling of Component-Oriented Phased Array Radars.
By: Tel-Wel Kuo; Yung-Sheng Chao; Chin-Fu Kuo; Cheng Chang. p47-60, 14p;
Ключевые слова: ELECTRONIC systems, PHASED array antennas, RADAR, REAL-time programming, SIMULATION methods, SURVEILLANCE radar
Author-Supplied Keywords: real-time dwell scheduling, rate-based scheduling, radar control computer, Phased array radar
Abstract: A multifunction phased array radar must search and track suspicious targets in its surveillance space in a real-time fashion. With inefficient scheduling implementations in many traditional systems, much radar resource is wasted with a very limited performance gain. This paper targets one of the most important issues in the design of modern phased array radars: real-time dwell scheduling. We formalize the typical workload of a modern phased array radar and propose a rate-based approach to schedule radar dwells in a real-time fashion. We show how to reserve radar resources to guarantee the minimum radar operation without sacrificing the stability of the system. The strength of our approach is verified by a series of simulation experiments based on a real phased array radar for air defense frigates [9]. A significant improvement in the performance of phased array radars was shown. [ABSTRACT FROM AUTHOR]
6. Построение оптимально детерминированной схемы разбиений (Partitionings) в основанной на сканировании встроенной системы самотестирования (BIST) диагностики ошибок: математические основы и эффективное использование.
The Construction of Optimal Deterministic Partitionings in Scan-Based BIST Fault Diagnosis: Mathematical Foundations and Cost-Effective Implementations.
By: Bayraktaroglu, Ismet; Orailoglu, Alex. p61-75, 15p;
Ключевые слова: COST control, COST effectiveness, MATHEMATICAL analysis, PARTITIONS (Mathematics), COMPUTER programming, SIMULATION methods
Author-Supplied Keywords: scan-based BIST, finite field arithmetic, Fault diagnosis
Abstract: Partitioning techniques enable identification of fault-embedding scan cells in scan-based BIST. We introduce, in this paper, deterministic partitioning techniques capable of resolving the location of the fault-embedding scan cells. We outline a complete mathematical analysis that identifies the class of deterministic partitioning structures and complement this rigorous mathematical analysis with an exposition of the appropriate cost-effective implementation techniques. We validate the superiority of the deterministic techniques both in an average-case sense by conducting simulation experiments and in a worst-case sense through a thorough mathematical analysis. [ABSTRACT FROM AUTHOR]
7. Принудительная организация данных в кэше для предотвращения сбоев при конфликтном сжатии в встроенных мультимедийных приложениях.
Cache Conscious Data Layout Organization for Conflict Miss Reduction in Embedded Multimedia Applications.
By: Kulkarni, C.; Ghez, C.; Miranda, M.; Catthoor, F.; de Man, H.. p76-81, 6p;
Ключевые слова: CACHE memory, COMPUTER algorithms, EMBEDDED computer systems, HEURISTIC programming, MULTIMEDIA systems, COMPUTER systems
Author-Supplied Keywords: VLIW architectures, VLSI systems, RISC/CISC
Abstract: Cache misses form a major bottleneck for real-time multimedia applications due to the off-chip accesses to the main memory. This results in both a major access bandwidth overhead (and related power consumption) as well as performance penalties. In this paper, we propose a new technique for organizing data in the main memory for data dominated multimedia applications so as to reduce the majority of the conflict cache misses. The focus of this paper is on the formal and heuristic algorithm we use to steer the data layout decisions and the experimental results obtained using a prototype tool. Experiments on real-life demonstrators illustrate that we are able to reduce up to 82 percent of the conflict misses for applications which are already aggressively transformed at source - level. At the same time, we also reduce the off-chip data accesses by up to 78 percent. In addition, we are able to reduce up to 20 percent more conflict misses compared to existing techniques. [ABSTRACT FROM AUTHOR]
8. Пропорциональное увеличение мультипроцессорного чипа «Атлас».
Scaling Up the Atlas Chip-Multiprocessor.
By: Sassone, Peter G.; Wills, D. Scott. p82-87, 6p;
Ключевые слова: COMMUNICATION, ELECTRONIC data processing, ELECTRONIC digital computers, INFORMATION science, INTEGRATED circuits, MULTIPROCESSORS
Author-Supplied Keywords: chip-multiprocessor, scaling, Dynamic multithreading
Abstract: Atlas, a dynamically multithreading chip-multiprocessor (CMP), gains little complexity as processing elements are added. When the model is scaled up with strategic layouts and realistic latencies area and power efficiency surpass that of an aggressive out-of-order processor, though results are sensitive to global communication delay. [ABSTRACT FROM AUTHOR]
9. Параллельное декодирование корректирующих кодов пакета циклической ошибки.
Parallel Decoding Cyclic Burst Error Correcting Codes.
By: Umanesan, Ganesan; Fujiwara, Eiji. p87-92, 6p;
Ключевые слова: DIGITAL electronics, ELECTRONIC circuits, LOGIC design, SHIFT registers, DECODERS & decoding, ENCODING
Author-Supplied Keywords: Fire codes, parallel decoding, companion matrix, Cyclic burst error correcting codes
Abstract: Burst error correcting codes, such as Fire codes, have traditionally been decoded using Linear Feedback Shift Registers (LFSR). However, such sequential decoding schemes are not suitable for modern ultra high-speed channels that demand high-speed parallel decoding employing only combinational logic circuitry. This paper proposes a parallel decoding method for cyclic burst error correcting codes. Under this method, a binary companion matrix T defines the entire decoding process. Hence, the decoding method can be implemented using only combinational logic. [ABSTRACT FROM AUTHOR]
Журнал IEEE Transactions on Knowledge and Data Engineering
Jan 2005, Vol. 17 Issue 1
Труды Института Инженеров по Электротехнике и Электронике (США)
«Инженерия знаний и информации»
Том 17, вып. 1 (Январь 2005 г.)
СТАТЬИ
1. Передовая статья Главного редактора.
EIC Editorial.
By: Yu, Philip S.. p1-2, 2p;
Ключевые слова: ARTIFICIAL intelligence, COMPUTER science, COMPUTER scientists, INFORMATION resources management, PERIODICALS, DATA mining, KNOWLEDGE management
Abstract: The article focuses on Xindong Wu, chairman of the Department of Computer Science at the University of Vermont in Burlington, Vermont, and computer scientist Jeffrey Xu Yu. Xindong Wu will be the new editor-in-chief (EIC) of the journal IEEE Transactions on Knowledge and Data Engineering (TKDE) replacing the present editor. He received a doctorate in artificial intelligence from the University of Edinburgh in Great Britain. His research interests include data mining, knowledge-based systems, and Web information exploration. He has published extensively in these areas in various journals and conferences. Xindong Wu is the executive editor (1 January 1999-31 December 2004) and an honorary editor-in-chief (starting, 1 January 2005) of Knowledge and Information Systems (a peer-reviewed archival journal published by Springer-Verlag). Jeffrey Xu Yu received the BE, ME and PhD degrees in computer science from the University of Tsukuba, Japan in 1985, 1987, and 1990, respectively. His major research interests include data mining, data stream mining/processing, apart from other disciplines.
2. Обращение к читателям вновь назначенного главного редактора.
Editorial: A Message from the New Editor-in-Chief.
By: Wu, Xindong. p3-3, 1p;
Ключевые слова: COMPUTER science, INFORMATION resources management, PERIODICAL editors, PERIODICALS, KNOWLEDGE management
Abstract: The article presents a message by the article author who is the new editor-in-chief of the journal "IEEE Transactions on Knowledge and Data Engineering" (TKDE) as the journal has completed its 16 years of publication. He has regarded the hard work and outstanding efforts of the four previous editors-in-chief, associate editors, reviewers, authors, and support staff from the IEEE Computer Society Publications Office. He said that TKDE is commonly recognized as the premier journal in the field of knowledge and data engineering, including database data mining, and knowledge engineering. The activities planned by the new EIC include revising TKDE topic areas to cover new emerging areas and technological advancements, and organizing special issues on promising topics when the need arises; inviting well-recognized researchers in TKDE areas to serve on the Editorial Board and minimizing the delay in publication by reducing the backlog of accepted papers. He has invited all authors and readers to share their comments and advice on how to further enhance the journal's value to the wider research community in knowledge and data engineering.
3. Обобщенная временная модель управления, базирующаяся на ролевом доступе.
A Generalized Temporal Role-Based Access Control Model.
By: Joshi, James B. D.; Bertino, Elisa; Latif, Usman; Ghafoor, Arif. p4-23, 20p;
Ключевые слова: ROLE playing, SECURITY systems, SEMANTICS, SOCIAL role, ACCESS control, SECURITY management
Author-Supplied Keywords: role-based, temporal constraints, role hierarchy, separation of duty.
Abstract: Role-based access control (ABAC) models have generated a great interest in the security community as a powerful and generalized approach to security management. In many practical scenarios, users may be restricted to assume roles only at predefined time periods. Furthermore, roles may only be invoked on prespecified intervals of time depending upon when certain actions are permitted. To capture such dynamic aspects of a role, a temporal RBAC (TRBAC) model has been recently proposed. However, the TRBAC model addresses the role enabling constraints only. In this paper, we propose a Generalized Temporal Role-Based Access Control (GTRBAC) model capable of expressing a wider range of temporal constraints. In particular, the model allows expressing periodic as well as duration constraints on roles, user-role assignments, and role-permission assignments. In an interval, activation of a role can further be restricted as a result of numerous activation constraints including cardinality constraints and maximum active duration constraints. The GTRBAC model extends the syntactic structure of the IRBAC model and its event and trigger expressions subsume those of TRBAC. Furthermore, GTRBAC allows expressing role hierarchies and separation of duty (SoD) constraints for specifying fine-grained temporal semantics. [ABSTRACT FROM AUTHOR]
4. Выбор именованных выводимых таблиц в хранилище данных.
Selection of Views to Materialize in a Data Warehouse.
By: Gupta, Himanshu; Mumick, Inderpal Singh. p24-43, 20p;
Ключевые слова: ALGORITHMS, DATABASE management, HEURISTIC, DATA warehousing, OLAP technology, MAINTENANCE costs
Author-Supplied Keywords: view selection, data warehouse, materialization.
Abstract: A data warehouse stores materialized views of data from one or more sources, with the purpose of efficiently implementing decision-support or OLAP queries. One of the most important decisions in designing a data warehouse is the selection of materialized views to be maintained at the warehouse. The goal is to select an appropriate set of views that minimizes total query response time and the cost of maintaining the selected views, given a limited amount of resource, e. g., materialization time, storage space, etc. In this article, we have developed a theoretical framework for the general problem of selection of views in a data warehouse. We present polynomial-time heuristics for a selection of views to optimize total query response time under a disk-space constraint, for some important special cases of the general data warehouse scenario, viz.: 1) an AND view graph, where each query/view has a unique evaluation, e. g., when a multiple-query optimizer can be used to general a global evaluation plan for the queries, and 2) an OR view graph, in which any view can be computed from any one of its related views, e. g., data cubes. We present proofs showing that the algorithms are guaranteed to provide a solution that is fairly close to (within a constant factor ratio of) the optimal solution. We extend our heuristic to the general AND-OR view graphs. Finally, we address in detail the view-selection problem under the maintenance cost constraint and present provably competitive heuristics. [ABSTRACT FROM AUTHOR]
5. Семантическая аппроксимация соединений потоков данных.
Semantic Approximation of Data Stream Joins.
By: Das, Abhinandan; Gehrke, Johannes; Riedewald, Mirek. p44-59, 16p;
Ключевые слова: ALGORITHMS, ARCHITECTURAL models, INFORMATION storage & retrieval systems, REAL-time data processing, ONLINE algorithms, RESOURCE management
Author-Supplied Keywords: approximation algorithms, semantic load shedding, set approximation, error metric, join processing.
Abstract: We consider the problem of approximating sliding window joins over data streams in a data stream processing system with limited resources. In our model, we deal with resource constraints by shedding load in the form of dropping tuples from the data streams. We make two main contributions. First, we define the problem space by discussing architectural models for data stream join processing and surveying suitable measures for the quality of an approximation of a set-valued query result. Second, we examine in detail a large part of this problem space. More precisely, we consider the number of generated result tuples as the quality measure and we propose optimal off line and fast online algorithms for it. In a thorough experimental study with synthetic and real data, we show the efficacy of our solutions. [ABSTRACT FROM AUTHOR]
6. Сжатие и визуализация обобщенных ассоциативных правил в параллельных координатах.
Pruning and Visualizing Generalized Association Rules in Parallel Coordinates.
By: Yang, Li. p60-70, 11p;
Ключевые слова: COORDINATES, Curvilinear, DATABASE selection, LATTICE theory, POLYNOMIALS, DATA warehousing, TAXONOMY
Author-Supplied Keywords: data visualization, data mining, interactive data exploration, mining methods and algorithms.
Abstract: One fundamental problem for visualizing frequent itemsets and association rules is how to present a long border of frequent itemsets in an itemset lattice. Another problem comes from the lack of an effective visual metaphor to represent many-to-many relationships. This paper proposes an approach for visualizing frequent itemsets and many-to-many association rules by a novel use of parallel coordinates. An association rule is visualized by connecting items in the rule, one item on each parallel coordinate, with continuous polynomial curves. In the presence of item taxonomy, each coordinate can be used to visualize an item taxonomy tree which can be expanded or shrunk by user interaction. This user interaction introduces a border, which separates displayable itemsets from nondisplayable ones, in the generalized itemset lattice. Only those itemsets that are both frequent and displayable are considered to be displayed. This approach of visualizing frequent itemsets and association rules has the following features: 1) It is capabIe of visualizing many-to-many rules and itemsets with many items. 2) It is capable of visualizing a large number of itemsets or rules by displaying only those ones whose items are selected by the user. 3) The closure properties of frequent itemsets and association rules are inherently supported such that the implied ones are not displayed. Usefulness of this approach is demonstrated through examples. [ABSTRACT FROM AUTHOR]
7. Алгоритмы распараллеливания данных в совместно используемой памяти: программный интерфейс и эффективность.
Shared Memory Parallelization Data Algorithms: Techniques, Programming Interface, and Performance.
By: Jin, Ruoming; Yang, Ge; Agrawal, Gagan. p71-89, 19p;
Ключевые слова: ALGORITHMS, COMPUTER storage devices, DATA transmission systems, DECISION trees, DATA mining, DATA warehousing, BANDWIDTHS
Author-Supplied Keywords: programming interfaces, association mining, clustering, decision tree construction. Shared memory parallelization
Abstract: With recent technological advances, shared memory parallel machines have become more scalable, and offer large main memories and high bus bandwidths. They are emerging as good platforms for data warehousing and data mining, in this paper, we focus on shared memory parallelization of data mining algorithms. We have developed a series of techniques for parallelization of data mining algorithms, including full replication, full locking, fixed locking, optimized full locking, and cache-sensitive locking. Unlike previous work on shared memory parallelization of specific data mining algorithms, all of our techniques apply to a large number of popular data mining algorithms. In addition, we propose a reduction-object-based interface for specifying a data mining algorithm. We show how our runtime system can apply any of the techniques we have developed starting from a common specification of the algorithm. We have carried out a detailed evaluation of the parallelization techniques and the programming interface. We have experimented with apriori and fp-tree-based association mining, k-means clustering, k-nearest neighbor classifier, and decision tree construction. The main results from our experiments are as follows: 1) Among full replication, optimized full locking, and cache-sensitive locking, there is no clear winner. Each of these three techniques can outperform others depending upon machine and dataset parameters. These three techniques perform significantly better than the other two techniques. 2) Good parallel efficiency is achieved for each of the four algorithms we experimented with, using our techniques and runtime system. 3) The overhead of the interface is within 10 percent in almost all cases. 4) In the case of decision tree construction, combining different techniques turned out to be crucial for achieving high performance. [ABSTRACT FROM AUTHOR]
8. Построение дерева суффиксов в гигабайтных последовательностях для мегабайтной памяти.
Constructing Suffix Tree for Gigabyte Sequences with Megabyte Memory.
By: Cheung, Ching-Fung; Yu, Jeffrey Xu; Lu, Hongjun. p90-105, 16p;
Ключевые слова: COMPUTER algorithms, COMPUTER storage devices, DATA structures (Computer science), DNA, GENETIC engineering, GENOMES, DNA data banks
Author-Supplied Keywords: database index and suffix tree. Biological sequences
Abstract: Mammalian genomes are typically 3Gbps (gibabase pairs) in size. The largest public database NCBI (National Center for Biotechnology Information (http://www. ncbi. nlm. nih. gov)) of DNA contains more than 20 Gbps. Suffix trees are widely acknowledged as a data structure to support exact/approximate sequence matching queries as well as repetitive structure finding efficiently when they can reside in main memory. But, it has been shown as difficult to handle long DNA sequences using suffix trees due to the so-cafled memory bottleneck problems. The most space efficient main-memory suffix tree construction algorithm takes nine hours and 45 GB memory space to index the human genome [19]. In this paper, we show that suffix trees for long DNA sequences can be efficiently constructed on disk using small bounded main memory space and, therefore, all existing algorithms based on suffix trees can be used to handle long DNA sequences that cannot be held in main memory. We adopt a two-phase strategy to construct a suffix tree on disk: 1) to construct a diskbase suffix-tree without suffix links and 2) rebuild suffix links upon the suffix-tree being constructed on disk, if needed. We propose a new disk-based suffix tree construction algorithm, called DynaCluster, which shows O(nlogn) experimental behavior regarding CPU cost and linearity for I/O cost. DynaCluster needs 16MB main memory only to construct more than 200Mbps DNA sequences and significantly outperforms the existing disk-based suffix-tree construction algorithms using prepartitioning techniques in terms of both construction cost and query processing cost. We conducted extensive performance studies and report our findings in this paper. [ABSTRACT FROM AUTHOR]
9. Улучшение доступности и быстродействия посредством учета специфики Интернет-приложений и системы резервирования и восстановления данных.
Improving Availability and Performance with Application-Specific Data Replication.
By: Gao, Lel; Dahlin, Mike; Nayate, Amol; Zheng, Jiandan; Iyengar, Arun. p106-120, 15p;
Ключевые слова: DATABASES PERFORMANCE, REACTION time, WIDE area networks (Computer networks), DATA replication, WEB services
Author-Supplied Keywords: data replication, distributed objects, edge services, Wide Area Networks (WAN).
Abstract: The emerging edge services architecture promises to improve the availability and performance of Web services by replicating servers at geographically distributed sites. A key challenge in such systems is data replication and consistency, so that edge server code can manipulate shared data without suffering the availability and performance penalties that would be incurred by accessing a traditional centralized database. This article explores using a distributed object architecture to build an edge service data replication system for an e-commerce application, the TPC-W benchmark, which simulates an online bookstore. We take advantage of application-specific semantics to design distributed objects that each manages a specific subset of shared information using simple and effective consistency models. Our experimental results show that by slightly relaxing consistency within individual distributed objects, our application realizes both high availability and excellent performance. For example, in one experiment, we find that our object-based edge server system provides five times better response time over a traditional centralized cluster architecture and a factor of nine improvement over an edge service system that distributes code but retains a centralized database. [ABSTRACT FROM AUTHOR]
10. Иинтерпретируемая иерархическая кластеризация при помощи построения неуправляемого дерева решений.
Interpretable Hierarchical Clustering by Constructing an Unsupervised Decision Tree.
By: Basak, Jayanta; Krishnapuram, Raghu. p121-132, 12p;
Ключевые слова: ALGORITHMS, DECISION making, DECISION trees, ENTROPY (Physics), PERFORMANCE, RULES
Author-Supplied Keywords: entropy data set segmentation. Unsupervised decision tree
Abstract: In this paper, we propose a method for hierarchical clustering based on the decision tree approach. As in the case of supervised decision tree, the unsupervised decision tree is interpretable in terms of rules, he., each leaf node represents a cluster, and the path from the root node to a leaf node represents a rule. The branching decision at each node of the tree is made based on the clustering tendency of the data available at the node. We present four different measures for selecting the most appropriate attribute to be used for splitting the data at every branching node (or decision node), and two different algorithms for splitting the data at each decision node. We provide a theoretical basis for the approach and demonstrate the capability of the unsupervised decision tree for segmenting various data sets. We also compare the performance of the unsupervised decision tree with that of the supervised one. [ABSTRACT FROM AUTHOR]
11. Линейные временные последовательности и их интерпретация с использованием отношений средней точки.
Linear Temporal Sequences and Their Interpretation Using Midpoint Relationships.
By: Roddick, John F.; Mooney, Carl H. p133-135, 3p;
Ключевые слова: ARTIFICIAL intelligence, COMPUTER science, DATABASES, SELF-organizing systems, MODIFICATIONS, MODEL validation
Author-Supplied Keywords: temporal uncertainty, Allen temporal relationships, Freksa semi-intervals. Temporal reasoning
Abstract: The temporal interval relationships formalized by Allen, and later extended to accommodate semi-intervals by Freksa, have been widely utilized in both data modeling and artificial intelligence research to facilitate reasoning between the relative temporal ordering of events. In practice, however, some modifications to the relationships are necessary when linear temporal sequences are provided, when event times are aggregated, or when data m supplied to a granularity which is larger than required. This paper discusses these modifications and outlines a solution to this problem which accommodates any available knowledge of interval midpoints. [ABSTRACT FROM AUTHOR]
12. Извлечение секвенциальных моделей из многомерных последовательностей данных.
Mining Sequential Patterns from Multidimensional Sequence Data.
By: Chung-Ching Yu; Chen, Yen-Liang. p136-140, 5p;
Ключевые слова: ALGORITHMS, DATABASES, DIMENSIONS, ONLINE databases, WORLD Wide Web, WEB sites, DATA mining
Author-Supplied Keywords: sequential patterns, sequence data, data mining. Frequent pattern
Abstract: The problem addressed in this paper is to discover the frequently occurred sequential patterns from databases. Although much work has been devoted to this subject, to the best of our knowledge, no previous research was able to find sequential patterns from d-dimensional sequence data, where d > 2. Without such a capability, many practical data would be impossible to mine. For example, an online stock-trading site may have a customer database, where each customer may visit a Web site in a series of days; each day takes a series of sessions and each session visits a series of Web pages. Then, the data for each customer forms a 3-dimensional list, where the first dimension is days, the second is sessions, and the third is visited pages. To mine sequential patterns from this kind of sequence data, two efficient algorithms have been developed in this paper. [ABSTRACT FROM AUTHOR]
