The space complexity of unbounded timestamps

The timestamp problem captures a fundamental aspect of asynchronous distributed computing. It allows processes to label events throughout the system with timestamps that provide information about the real-time ordering of those events. We consider the space complexity of wait-free implementations of timestamps from shared read-write registers in a system of n processes. We prove an lower bound on the number of registers required. If the timestamps are elements of a nowhere dense set, for example the integers, we prove a stronger, and tight, lower bound of n. However, if timestamps are not from a nowhere dense set, this bound can be beaten: we give an implementation that uses n − 1 (single-writer) registers. We also consider the special case of anonymous implementations, where processes are programmed identically and do not have unique identifiers. In contrast to the general case, we prove anonymous timestamp implementations require n registers. We also give an implementation to prove that this lower bound is tight. This is the first anonymous timestamp implementation that uses a finite number of registers.     

应急仿真中的碰撞检测算法研究

以应急仿真场景为背景,针对其中大量物体碰撞检测过程的需求,提出了层次包围盒与空间划分方法结合的实时碰撞检测算法,可以在完全不降低碰撞检测精度的同时,大大改进了仿真环境碰撞检测的效率,减轻了计算负担,提高了系统的实时性。     

River Networks for Instant Procedural Planets

Realistic terrain models are required in many applications, especially in computer games. Commonly, procedural models are applied to generate the corresponding models and let users experience a wide variety of new environments. Existing algorithms generate landscapes immediately with view‐dependent resolution and without preprocessing. Unfortunately, landscapes generated by such algorithms lack river networks and therefore appear unnatural. Algorithms that integrate realistic river networks are computationally expensive and cannot be used to generate a locally adaptive high resolution landscape during a fly‐through. In this paper, we propose a novel algorithm to generate realistic river networks. Our procedural algorithm creates complete planets and landscapes with realistic river networks within seconds. It starts with a coarse base geometry of a planet without further preprocessing and user intervention. By exploiting current graphics hardware, the proposed algorithm is able to generate adaptively refined landscape geometry during fly‐throughs.     

Logical Representation of a Conceptual Model for Spatial Data Warehouses

The MultiDimER model is a conceptual model used for representing a multidimensional view of data for Data Warehouse (DW) and On-Line Analytical Processing (OLAP) applications. This model includes a spatial extension allowing spatiality in levels, hierarchies, fact relationships, and measures. In this way decision-making users can represent in an abstract manner their analysis needs without considering complex implementation issues and spatial OLAP tools developers can have a common vision for representing spatial data in a multidimensional model. In this paper we propose the transformation of a conceptual schema based on the MultiDimER constructs to an object-relational schema. We based our mapping on the SQL:2003 and SQL/MM standards giving examples of commercial implementation using Oracle 10g with its spatial extension. Further we use spatial integrity constraints to ensure the semantic equivalence of the conceptual and logical schemas. We also show some examples of Oracle spatial functions, including aggregation functions required for the manipulation of spatial data. The described mappings to the object-relational model along with the examples using a commercial system show the feasibility of implementing spatial DWs in current commercial DBMSs. Further, using integrated architectures, where spatial and thematic data is defined within the same DBMS, facilitates the system management simplifying data definition and manipulation.

Towards Efficient Execution of MPI Applications on the Grid: Porting and Optimization Issues

The message passing interface (MPI) is a standard used by many parallel scientific applications. It offers the advantage of a smoother migration path for porting applications from high performance computing systems to the Grid. In this paper Grid-enabled tools and libraries for developing MPI applications are presented. The first is MARMOT, a tool that checks the adherence of an application to the MPI standard. The second is PACX-MPI, an implementation of the MPI standard optimized for Grid environments. Besides the efficient development of the program, an optimal execution is of paramount importance for most scientific applications. We therefore discuss not only performance on the level of the MPI library, but also several application specific optimizations, e.g., for a sparse, parallel equation solver and an RNA folding code, like latency hiding, prefetching, caching and topology-aware algorithms.     

基于三层结构的GSM网络优化系统研究与设计

GSM网络优化在日常运行维护中,是较为复杂繁琐、等级要求较高的工作。如何通过恰当的计算机综合应用技术,来提高网络优化的效率,是值得探讨的问题。该文对基于三层结构的GSM网络优化系统的开发设计进行了深入探讨。     

碰撞检测技术研究综述

碰撞检测在图形学、仿真、动画和虚拟现实等技术中得到广泛的研究,这些研究具有十分重要的意义。文章对二维空间中多边形等面模型间相交,以及三维空间中多面体等体模型间干涉的角度对碰撞检测技术的研究和发展作了较为全面的论述,并对几种常用的碰撞检测算法进行了分析和比较,最后对碰撞检测算法的发展方向提出了几点建议。     

基于规则面向属性的数据库归纳的无回溯算法

该文提出了基于规则的面向属性知识发现方法的无回溯算法.把背景知识理解为特殊的逻辑程序,并把它的子句展开为完全归结子句,然后按照用户要求,定义并确定每个属性的恰当层次.每个属性的多个值归纳为恰当层次中的值,只需一遍扫描,因此无需回溯.     

POLITICAL PARADOXES OF MAJORITY RULE VOTING AND HIERARCHICAL SYSTEMS

The use of majority rule voting is believed to be instrumental to establish democratic operating of political organizations. However in this work it is shown that, while applied to hierarchical systems, it leads to political paradoxes. To substantiate these findings a model to construct self-directed pyramidal structures from bottom up to the top is presented. Using majority rules it is shown that a minority and even a majority can be systematically self-eliminated from top leadership, provided the hierarchy has a minimal number of levels. In some cases, 70% of the population is found to have zero representation after 6 hierarchical levels. Results are discussed with respect to internal operating of political organizations.     

Neighborhood systems and approximate retrieval

An approximate retrieval model is proposed based on the notion of neighborhood systems. The knowledge used in the model consists of an information table, in which each object is represented by its values on a finite set of attributes, and neighborhood systems on attribute values, which provide semantic similarity or closeness of different values. An information table can be used for exact retrieval. With the introduction of neighborhood systems to information tables, one is able to perform approximate retrieval. Operations on neighborhood systems are introduced based on power algebras. An ordering relation representing the information of a neighborhood system is suggested and examined. Approximate retrieval is carried out by the relaxation of the original query using neighborhood systems, and the combination of intermediate results using neighborhood system operations. The final retrieval results are presented according to the proposed ordering relation. In contrast to many existing systems, a main advantage of the proposed model is that the retrieval results are a non-linear ordering of objects.