Fast multicast on multistage interconnection networks using multi-head worms

1IntroductionMulticastcommunication,whichreferstothedeliveryofamessagefromasinglesourcenodetoanumberofdestinationnodes,isfrequentlyusedindistributed-memoryparallelcomputersystemsandnetworks[1].Efficientimplementationofmulticastcommunicationiscriticaltotheperformanceofmessage-basedscalableparallelcomputersandswitch-basedhighspeednetworks.Switch-basednetworksorindirectnetworks,basedonsomevariationsofmultistageiDterconnectionnetworks(MINs),haveemergedasapromisingnetworkajrchitectureforconstruct…     

GigaE PM: a high performance communication facility using a Gigabit Ethernet

A high performance communication facility, called theGigaE PM, has been designed and implemented for parallel applications on clusters of computers using a Gigabit Ethernet. The GigaE PM provides not only a reliable high bandwidth and low latency communication, but also supports existing network protocols such as TCP/IP. A reliable communication mechanism for a parallel application is implemented on the firmware on a NIC while existing network protocols are handled by an operating system kernel. A prototype system has been implemented using an Essential Communications Gigabit Ethernet card. The performance results show that a 58.3 μs round trip time for a four byte user message, and 56.7 MBytes/sec bandwidth for a 1,468 byte message have been achieved on Intel Pentium II 400 MHz PCs. We have implemented MPICH-PM on top of the GigaE PM, and evaluated the NAS parallel benchmark performance. The results show that the IS class S performance on the GigaE PM is 1.8 times faster than that on TCP/IP. Shinji Sumimoto: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. He received BS degree in electrical engineering from Doshisha University. His research interest include parallel and distributed systems, real-time systems, and high performance communication facilities. He is a member of Information Processing Society of Japan. Hiroshi Tezuka: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. His research interests include real-time systems and operating system kernel. He is a member of the Information Processing Society of Japan, and Japan Society for Software Science and Technology. Atsushi Hori, Ph.D.: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. His current research interests include parallel operating system. He received B.S. and M.S. degrees in Electrical Engineering from Waseda University, and received Ph.D. from the University of Tokyo. He worked as a researcher in Mitsubishi Research Institute from 1981 to 1992. Hiroshi Harada: He is a Senior Researcher of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. His research interests include distributed/parallel systems and distributed shared memory. He received BS degree in physics from Science University of Tokyo. He is a member of ACM and Information Processing Society of Japan. Toshiyuki Takahashi: He is a Researcher at Real World Computing Partnership since 1998. He received his B.S. and M.S. from the Department of Information Sciences of Science University of Tokyo in 1993 and 1995. He was a student of the Information Science Department of the University of Tokyo from 1995 to 1998. His current interests are in meta-level architecture for programming languages and high-performance software technologies. He is a member of Information Processing Society of Japan. Yutaka Ishikawa, Ph.D.: He is the chief of Parallel and Distributed System Software Laboratory at Real World Computing Partnership, JAPAN. He is currently temporary retirement from Electrotechnical Laboratory, MITI. His research interests include distributed/parallel systems, object-oriented programming languages, and real-time systems. He received the B.S., M.S. and Ph.D degrees in electrical engineering from Keio University. He is a member of the IEEE Computer Society, ACM, Information Processing Society of Japan, and Japan Society for Software Science and Technology.     

A grid-oriented genetic algorithm framework for bioinformatics

In this paper, we propose a framework for enabling for researchers of genetic algorithms (GAs) to easily develop GAs running on the Grid, named “Grid-Oriented Genetic algorithms (GOGAs)”, and actually “Gridify” a GA for estimating genetic networks, which is being developed by our group, in order to examine the usability of the proposed GOGA framework. We also evaluate the scalability of the “Gridified” GA by applying it to a five-gene genetic network estimation problem on a grid testbed constructed in our laboratory. Hiroaki Imade: He received his B.S. degree in the department of engineering from The University of Tokushima, Tokushima, Japan, in 2001. He received the M.S. degree in information systems from the Graduate School of Engineering, The University of Tokushima in 2003. He is now in Doctoral Course of Graduate School of Engineering, The University of Tokushima. His research interests include evolutionary computation. He currently researches a framework to easily develop the GOGA models which efficiently work on the grid. Ryohei Morishita: He received his B.S. degree in the department of engineering from The University of Tokushima, Tokushima, Japan, in 2002. He is now in Master Course of Graduate School of Engineering, The University of Tokushima, Tokushima. His research interest is evolutionary computation. He currently researches GA for estimating genetic networks. Isao Ono, Ph.D.: He received his B.S. degree from the Department of Control Engineering, Tokyo Institute of Technology, Tokyo, Japan, in 1994. He received Ph.D. of Engineering at Tokyo Institute of Technology, Yokohama, in 1997. He worked as a Research Fellow from 1997 to 1998 at Tokyo Institute of Technology, and at University of Tokushima, Tokushima, Japan, in 1998. He worked as a Lecturer from 1998 to 2001 at University of Tokushima. He is now Associate Professor at University of Tokushima. His research interests include evolutionary computation, scheduling, function optimization, optical design and bioinformatics. He is a member of JSAI, SCI, IPSJ and OSJ. Norihiko Ono, Ph.D.: He received his B.S. M.S. and Ph.D. of Engineering in 1979, 1981 and 1986, respectively, from Tokyo Institute of Technology. From 1986 to 1989, he was Research Associate at Faculty of Engineering, Hiroshima University. From 1989 to 1997, he was an associate professor at Faculty of Engineering, University of Tokushima. He was promoted to Professor in the Department of Information Science and Intelligent Systems in 1997. His current research interests include learning in multi-agent systems, autonomous agents, reinforcement learning and evolutionary algorithms. Masahiro Okamoto, Ph.D.: He is currently Professor of Graduate School of Systems Life Sciences, Kyushu University, Japan. He received his Ph.D. degree in Biochemistry from Kyushu University in 1981. His major research field is nonlinear numerical optimization and systems biology. His current research interests cover system identification of nonlinear complex systems by using evolutional computer algorithm of optimization, development of integrated simulator for analyzing nonlinear dynamics and design of fault-tolerant routing network by mimicking metabolic control system. He has more than 90 peer reviewed publications.     

Efficient minimum spanning tree algorithms on the reconfigurable mesh

1 IntroductionLet G = (V, E) be a connected, undirected graph with a weight function W on the set Eof edges to the set of reals. A spanning tree is a subgraph T = (V, ET), ET G E, of C suchthat T is a tree. The weight W(T) of a spanning tree T is the sum of the weights of its edges.A spanning tree with the smallest possible'weight is called a minimum spanning tree (MST)of G. Computing an MST of a given weighted graph is an important problem that arisesin many applications. For this …     

Multi-structure information retrieval method based on transformation invariance

The needs of efficient and flexible information retrieval on multi-structural data stored in database and network are significantly growing. Especially, its flexibility plays one of the key roles to acquire relevant information desired by users in retrieval process. However, most of the existing approaches are dedicated to a single content and data structure respectively, e.g., relational database and natural text. In this work, we propose “Multi-Structure Information Retrieval” (MSIR) approach applicable to various types of contents and data structures by adapting a small part of the approach to data structures. The power of this approach comes from the use of the invariant feature information obtained from byte patterns in the files through some mathematical transformation. The experimental evaluation of the proposed approach for both artificial and real data indicates its high feasibility. Fuminori Adachi: He received his Master of engineering from Osaka University in ’03. He is enrolled in the doctoral course of Osaka University from ’03. His current research interest includes scientific discovery, data mining and machine learning techniques. Takashi Washio, Ph.D.: He received his Ph.D. from Tohoku University in ’88. In ’88, he became a visiting reseacher in Massachusetts Institute of Technology. In ’90, he joined Mitsubishi Research Institute Inc., and is working for Osaka University from ’96. His current research interest includes scientific discovery, data mining and machine learning techniques. Atsushi Fujimoto: He is enrolled in the master cource of Osaka University from ’03. His Current research interest includes correlation analysis, data mining and machine learning techniques. Hiroshi Motoda, Ph.D.: He received his Ph.D. from University of Tokyo in ’72. In ’67, he joined Hitachi Ltd. and has been working for Osaka University since ’96. His current research interest includes scientific discovery, data mining and machine learning. Hidemitsu Hanafusa: He received Master of Engineering from Keio University in ’83. In ’83, he joined The Kansai Electric Power Co. Ins. (KEPCO). He researched on Maintenance Support System at INSS from ’97 to ’02. Now, he is working in KEPCO.     

Program transformation system based on generalized partial computation

Generalized Partial Computation (GPC) is a program transformation method utilizing partial information about input data, abstract data types of auxiliary functions and the logical structure of a source program. GPC uses both an inference engine such as a theorem prover and a classical partial evaluator to optimize programs. Therefore, GPC is more powerful than classical partial evaluators but harder to implement and control. We have implemented an experimental GPC system called WSDFU (Waseda Simplify-Distribute-Fold-Unfold). This paper demonstrates the power of the program transformation system as well as its theorem prover and discusses some future works. Yoshihiko Futamura, Ph.D.: He is Professor of Department of Information and Computer Science and the director of the Institute for Software Production Technology (ISPT) of Waseda University. He received his BS in mathematics from Hokkaido University in 1965, MS in applied mathematics from Harvard University in 1972 and Ph.D. degree from Hokkaido University in 1985. He joined Hitachi Central Research Laboratory in 1965 and moved to Waseda University in 1991. He was a visiting professor of Uppsala University from 1985 to 1986 and a visiting scholar of Harvard University from 1988 to 1989. Automatic generation of computer programs and programming methodology are his main research fields. He is the inventor of the Futamura Projections in partial evaluation and ISO8631 PAD (Problem Analysis Diagram). Zenjiro Konishi: He is a visiting lecturer of Institute for Software Production Technology, Waseda University. He received his M. Sc. degree in mathematics from Waseda University in 1995. His research interests include automated theorem proving. He received JSSST Takahashi Award in 2001. He is a member of JSSST and IPSJ. Robert Glück, Ph.D., Habil.: He is an Associate Professor of Computer Science at the University of Copenhagen. He received his Ph.D. and Habilitation (venia docendi) from the Vienna University of Technology in 1991 and 1997. He was research assistant at the City University of New York and received twice the Erwin-Schrodinger-Fellowship of the Austrian Science Foundation (FWF). After being an Invited Fellow of the Japan Society for the Promotion of Science (JSPS), he is now funded by the PRESTO21 program for basic research of the Japan Science and Technology Corporation (JST) and located at Waseda University in Tokyo. His main research interests are advanced programming languages, theory and practice of program transformation, and metaprogramming.     

Trends of internet auctions and agent-mediated Web commerce

Electronic Commerce (EC) is a promising field for applying agent and Artificial Intelligence technologies. In this article, we give an overview of the trends of Internet auctions and agent-mediated Web commerce. We describe the theoretical backgrounds of auction protocols and introduce several Internet auction sites. Furthermore, we describe various activities aimed toward utilizing agent technologies in EC and the trends in standardization efforts on agent technologies. Makoto Yokoo, Ph.D.: He received the B.E. and M.E. degrees in electrical engineering, in 1984 and 1986, respectively, from the University of Tokyo, Japan, and the Ph.D. degree in information and communication engineering in 1995 from the University of Tokyo, Japan. He is currently a distinguished technical member in NTT Communication Science Laboratories, Kyoto, Japan. He was a visiting research scientist at the Department of Electrical Engineering and Computer Science, the University of Michigan, Ann Arbor, from 1990 to 1991. His current research interests include multi-agent systems, search, and constraint satisfaction. Satoru Fujita, D.Eng.: He received his B.E. and M.E. degrees in electronic engineering from the University of Tokyo in 1984 and 1986, respectively. He also received his D.Eng. from the University of Tokyo in 1989 for his research on context comprehension in natural language understanding. He joined NEC Corporation in 1989, and is now a principal researcher of Internet Systems Research Laboratories of NEC. He is engaged in research on mobile agents, distributed systems and Web services.     

Calculating accumulations

Theaccumulation strategy consists of generalizing a function over an algebraic data structure by inclusion of an extra parameter, anaccumulating parameter, for reusing and propagating intermediate results. However, there remain two major difficulties in this accumulation strategy. One is to determinewhere andwhen to generalize the original function. The other, surprisingly not yet receiving its worthy consideration, is how to manipulate accumulations. To overcome these difficulties, we propose to formulate accumulations ashigher order catamorphisms, and provide several general transformation rules for calculating accumulations (i.e., finding and manipulating accumulations) bycalculation-based (rather than a search-based) program transformation methods. Some examples are given for illustration. Zhenjiang Hu, Dr.Eng.: He is an Assistant Professor in Information Engineering at the University of Tokyo. He received his BS and MS in Computer Science from Shanghai Jiao Tong University in 1988 and 1990 respectively, and his Dr. Eng. degree in Information Engineering from the University of Tokyo in 1996. His current research concerns programming languages, functional programming, program transformation, and parallel processing. Hideya Iwasaki, Dr.Eng.: He is an Associate Professor in Information Engineering at the University of Tokyo. He received the M.E. degree in 1985, the Dr. Eng. degree in 1988 from the University of Tokyo. His research interests are list processing languages, functional languages, parallel processing, and constructive algorithmics. Masato Takeichi, Dr.Eng.: He is Professor in Mathematical Engineering and Information Engineering at the University of Tokyo since 1993. After graduation from the University of Tokyo, he joined the faculty at the University of Electro-Communications in Tokyo before he went back to work at the University of Tokyo in 1987. His research concerns the design and implementation of functional programming languages, and calculational program transformation systems.     

The influence of investor's behavioral biases on the usefulness of the Dual Moving Average Crossovers

The so called Dual Moving Average Crossovers are said to be useful signals for forecasting trends of stock prices, as one of the technical analysis methods. First, we examined the usefulness of these crossovers by using historical daily closing price data and tick by tick price data of Japanese stocks. The results revealed that these crossovers were useful as confirmatory signals for forecasting market trends. Second, we tried to identify the underlying reasons for the usefulness of the crossovers. A model, which followed the Efficient Market Hypothesis, was found to fail to generate the price fluctuation where the crossovers were useful. We then developed a model that incorporated investor's suspicion about current price validity and two famous behavioral biases: conservativeness and representativeness. We identified the mechanism that those crossovers were closely related to investor's suspicion and the behavioral biases. Kotaro Miwa: He is a Ph.D. candidate at the University of Tokyo. He is also a quantitative financial analyst and fund manager at Tokio Marine Asset Managements. He received his B.A. degree from the Faculty of Engineering at the University of Tokyo in 2001. He also received M.A. degree from the Department of Systems Science at the University of Tokyo in 2003. His current research interests include behavioral finance and financial engineering. Kazuhiro Ueda, Ph.D.: He is an associate professor at the University of Tokyo. He received his B.A. degree from the Faculty of Liberal Arts and Science at the University of Tokyo in 1988. He also received M.A. and Ph.D. degrees in cognitive science from the Department of Systems Science at the University of Tokyo in 1990 and 1993. His current research interests include cognitive analysis on scientific problem solving, adaptive human-machine interface, artificial market and behavioral finance and cognitive robotics.     

The superstructure toward open bioinformatics grid

The grid design strongly depends on not only a network infrastructure but also a superstructure, that is, a social structure of virtual organizations where people trust each other, share resources and work together. Open Bioinformatics Grid (OBIGrid) is a grid aimed at building a cooperative bioinformatics environment for computer sicentists and biologists. In October 2003, OBIGrid consisted of 293 nodes with 492 CPUs provided by 27 sites at universities, laboratories and other enterprises, connected by a virtual private network over the Internet. So many organizations have participated because OBIGrid has been conscious of constructing a superstructure on a grid as well as a grid infrastructure. For the benefit of OBIGrid participants, we have developed a series of life science application services: an open bioinformatics environment (OBIEnv), a scalable genome database (OBISgd), a genome annotation system (OBITco), a biochemical network simulator (OBIYagns), and to name a few. Akihiko Konagaya, Dr.Eng.: He is Project Director of Bioinformatics Group, RIKEN Genomic Sciences Center. He received his B.S. and M.S. from Tokyo Institute of Technology in 1978 and 1980 in Informatics Science, and joined NEC Corporation in 1980, Japan Advanced Institute of Science and Technology in 1997, RIKEN GSC in 2003. His research covers wide area from computer architectures to bioinformatics. He has been much involved into the Open Bioinformatics Grid project since 2002. Fumikazu Konishi, Dr.Eng.: He is researcher at Bioinformatics Group, RIKEN Genomic Sciences Center since 2000. He received his M.S. (1996) and Ph.D. (2001) from Tokyo Metropolitan Institute of Technology. He served as an assistant in Department of Production and Information Systems Engineering, Tokyo Metropolitan Institute of Technology since 2000. He also works in Structurome Research Group, RIKEN Harima Institute from 2001. His research interests include concurrent engineering, bioinformatics and the Grid. He has deeply affected to the design of OBIGrid. Mariko Hatakeyama, Ph.D.: She recieved her Ph.D. degree from Tokyo University of Agriculture and Technology. She is Research Scientist at Bioinformactis Group, RIKEN Genomic Sciences Center. Her research topics are: microbiology, enzymology and signal transduction of mammalian cells. She is now working on computational simulation of signal transduction systems and on thermophilic bacteria project. Kenji Satou, Ph.D.: He is Associate Professor of School of Knowledge Science at Japan Advanced Institute of Science and Technology. He received B.S., M.E. and Ph.D. degrees from Kyushu University, in 1987, 1989 and 1995 respectively. For each degree, he majored in computer engineering. His research interests have progressed from deductive database application through data mining to Grid computing and natural language processing. His current field of research is bioinformatics. He prefers set-oriented manner of thinking, and usually wonders how he can construct an intelligent-looking system based on large amount of heterogeneous data and computer resources.     

Binding-time analysis for both static and dynamic expressions

This paper presents a specializer and a binding-time analyzer for a functional language where expressions are allowed to be used as both static and dynamic. With both static and dynamic expressions, data structures can be statically accessed while they are residualized at the same time. Previously, such data structures were treated as completely dynamic, which prevented their components from being accessed statically. The technique presented in this paper effectively allows data structures to be lifted which was prohibited in the conventional partial evaluators. The binding-time analysis is formalized as a type system and the solution is obtained by solving constraints generated by the type system. We prove the correctness of the constraint solving algorithm and show that the algorithm runs efficiently in almost linear time. Kenichi Asai, Ph.D.: He is a research associate at the Department of Computer Science, Faculty of Science, the University of Tokyo. He obtained his bachelors degree, masters degree, and doctor of Science from the University of Tokyo in 1990, 1992, and 1997, respectively. His research interests are in Programming Languages in general, in Partial Evaluation and Reflection in particular. He is a member of ACM, IPSJ, and JSSST.     

PAN: A portable,parallel Prolog: Its design,realisation and performance

PAN is a general purpose, portable environment for executing logic programs in parallel. It combines a flexible, distributed architecture which is resilient to software and platform evolution with facilities for automatically extracting and exploiting AND and OR parallelism in ordinary Prolog programs. PAN incorporates a range of compile-time and run-time techniques to deliver the performance benefits of parallel execution while rertaining sequential execution semantics. Several examples illustrate the efficiency of the controls that facilitate the execution of logic programs in a distributed manner and identify the class of applications that benefit from distributed platforms like PAN. George Xirogiannis, Ph.D.: He received his B.S. in Mathematics from the University of Ioannina, Greece in 1993, his M.S in Artificial Intelligence from the University of Bristol in 1994 and his Ph.D. in Computer Science from Heriot-Watt University, Edinburgh in 1998. His Ph.D. thesis concerns the automated execution of Prolog on distributed heterogeneous multi-processors. His research interests have progressed from knowledge-based systems to distributed logic programming and data mining. Currently, he is working as a senior IT consultant at Pricewaterhouse Coopers. He is also a Research Associate at the National Technical University of Athens, researching in knowledge and data mining. Hamish Taylor, Ph.D.: He is a lecturer in Computer Science in the Computing and Electrical Engineering Department of Heriot-Watt University in Edinburgh. He received M.A. and MLitt degrees in philosophy from Cambridge University and an M.S. and a Ph.D. degree in computer science from Heriot-Watt University, Scotland. Since 1985 he has worked on research projects concerned with implementing concurrent logic programming languages, developing formal models for automated reasoning, performance modelling parallel relational database systems, and visualisizing resources in shared web caches. His current research interests are in applications of collaborative virtual environments, parallel logic programming and networked computing technologies.     

Self-stabilizing depth-first token circulation on networks

Summary This paper proposes a self-stabilizing protocol which circulates a token on a connected network in nondeterministic depth-first-search order, rooted at a special node. Starting with any initial state in which the network may have no token at all or more than one token, the protocol eventually makes the system stabilize in states having exactly one circulating token. With a slight modification to the protocol —by removing nondeterminism in the search — a depth-first-search tree on the network can be constructed. The proposed protocol runs on systems that allow parallel operations. Shing-Tsaan Huang was born in Taiwan on September 4, 1949. He got his Ph.D. degree in 1985 from Department of Computer Science, University of Maryland at College Park. Before he pursued his Ph.D. degree, he had worked several years in the computer industry in Taiwan. Professor Huang is currently the chairman of the Department of Computer Science, Tsing Hua University, Taiwan, Republic of China. His research interests include interconnection networks, operating systems and distributed computing. He is a senior member of the IEEE Computer Society and a member of the Association for Computing Machinery. Nian-Shing Chen was born in Taiwan on October 21, 1961. He received his Ph.D. degree in computer science from National Tsing Hua University in 1990. Dr. Chen is currently an associate professor with the Department of Information Management at Sun Yat-Sen University of Taiwan. His research interests include distributed systems, computer networks, computer viruses and expert systems. He is a member of IEEE and Phi Tau Phi honorary society.This research is supported by National Science Council of the Republic of China under the contract NSC81-0408-E-007-05 and NSC82-0408-E-007-027     

Preference queries in deductive databases

Traditional database query languages such as datalog and SQL allow the user to specify only mandatory requirements on the data to be retrieved from a database. In many applications, it may be natural to express not only mandatory requirements but also preferences on the data to be retrieved. Lacroix and Lavency¹⁰⁾ extended SQL with a notion of preference and showed how the resulting query language could still be translated into the domain relational calculus. We explore the use of preference in databases in the setting of datalog. We introduce the formalism of preference datalog programs (PDPs) as preference logic programs without uninterpreted function symbols for this purpose. PDPs extend datalog not only with constructs to specify which predicate is to be optimized and the criterion for optimization but also with constructs to specify which predicate to be relaxed and the criterion to be used for relaxation. We can show that all of the soft requirements in Reference¹⁰) can be directly encoded in PDP. We first develop anaively-pruned bottom-up evaluation procedure that is sound and complete for computing answers to normal and relaxation queries when the PDPs are stratified, we then show how the evaluation scheme can be extended to the case when the programs are not necessarily stratified, and finally we develop an extension of themagic templates method for datalog¹⁴) that constructs an equivalent but more efficient program for bottom-up evaluation. Kannan Govindarajan, Ph.D.: He obtained his bachelors degree in Computer Science and Engineering from the Indian Institute of Technology, Madras, and he completed his Ph.D. degree in Computer Science from the State University of New York at Buffalo. His dissertation research was on optimization and relaxation techniques for logic languages. His interests lie in the areas of programming languages, databases, and distributed systems. He currently leads the trading community effort in the E-speak Operation in Hewlett Packard Company. Prior to that, he was a member of the Java Products Group in Oracle Corporation. Bharat Jayaraman, Ph.D.: He is a Professor in the Department of Computer Science at the State University of New York at Buffalo. He obtained his bachelors degree in Electronics from the Indian Institute of Technology, Madras (1975), and his Ph.D. from the University of Utah (1981). His research interests are in programming languages and declarative modeling of complex systems. Dr. Jayaraman has published over 50 papers in refereed conferences and journals. He has served on the program committees of several conferences in the area of programming languages, and he is presently on the Editorial Board of the Journal of Functional and Logic Programming. Surya Mantha, Ph.D.: He is a manager in the Communications and Software Services Group of Pittiglio Rabin Todd & McGrath (PRTM), a management consulting firm serving high technology industries. He obtained a bachelors degree in Computer Science and Engineering from the Indian Institute of Technology, Kanpur, an MBA in Finance and Competitive Strategy from the University of Rochester, and a Ph.D. in Computer Science from the University of Utah (1991). His research interests are in the modeling of complex business processes, inter-enterprise application integration, and business strategy. Dr. Mantha has two US patents, and has published over 10 research papers. Prior to joining PRTM, he was a researcher and manager in the Architecture and Document Services Technology Center at Xerox Corporation in Rochester, New York.     

New Meta-Heuristic for Combinatorial Optimization Problems: Intersection Based Scaling

Combinatorial optimization problems are found in many application fields such as computer science,engineering and economy. In this paper, a new efficient meta-heuristic, Intersection-Based Scaling (IBS for abbreviation), is proposed and it can be applied to the combinatorial optimization problems. The main idea of IBS is to scale the size of the instance based on the intersection of some local optima, and to simplify the search space by extracting the intersection from the instance, which makes the search more efficient. The combination of IBS with some local search heuristics of different combinatorial optimization problems such as Traveling Salesman Problem (TSP) and Graph Partitioning Problem (GPP) is studied, and comparisons are made with some of the best heuristic algorithms and meta-heuristic algorithms. It is found that it has significantly improved the performance of existing local search heuristics and significantly outperforms the known best algorithms.     

ARMiner: A Data Mining Tool Based on Association Rules

In this paper,ARM iner,a data mining tool based on association rules,is introduced.Beginning with the system architecture,the characteristics and functions are discussed in details,including data transfer,concept hierarchy generalization,mining rules with negative items and the re-development of the system.An example of the tool‘s application is also shown.Finally,Some issues for future research are presented.     

A futures market-based model for dynamic network resource allocation

Management of telecommunication network requires quick, continuous and decentralized allocation of network bandwidth to various sorts of demands. So as to achieve the efficient network resource allocation, this paper describes a market-based model combining futures market with the agent-based approach. That is, utilization time is divided into many timeslots, and futures markets in hereafter use of bandwidth are opened. In our model, all market participants (software agents) observe only market prices and decide to buy or sell bandwidth trying to maximize their utilities over time so that they can secure enough network resources. The authors discuss network resource allocation through simulation using the proposed model. Masayuki Ishinishi, Ph.D.: He graduated from National Defense Academy in 1995 and 2000. He received the B.E. (1995) and M.E.(2000) degrees in computer science from National Institution for Academic Degrees (NIAD). He received his Ph.D. degree from Tokyo Institute of Technology in 2003. He has been a communications officer at Air Communications and Systems Wing in Japan Air Self-Defence Force (JASDF) since 2003. His research interests include information assurance, agent-based modeling and simulation, multi-agent system and market-based control. He is a member of IEEJ, IPSJ and JSAI. Yuhsuke Koyama, Ph.D.: He received the B.Econ., M.Econ., and Ph.D. degrees in economics from Kyoto University, in 1996, 1998, 2002, respectively. He has been a research associate of Tokyo Institute of Technology since 2002. His research field is evolutionary economics, mathematical sociology and experimental economics. He is a member of JAFEE, JAMS, JASESS and JASAG. Hiroshi Deguchi, Ph.D.: He received his Ph.D. degree in systems science from Tokyo Institute of Technology, in 1986. He also received the Dr. Econ. degree from Kyoto University in 2001. He has been a Professor of Tokyo Institute of Technology since 2002. His research field is evolutionary economics, computational organization theory, agent-based modeling, social system theory, gaming simulation, and philosophy of science. He is a member of SICE, JAMS, IPSJ, PHSC, JASAG and JAFEE. Hajime Kita, Ph.D.: He received the B.E., M.E., and Ph.D. degrees in electrical engineering from Kyoto University, in 1982, 1984, 1991, respectively. He has been a Professor of Kyoto University since 2003, His research field is systems science/engineering, and his research interests are evolutionary computation, neural networks and socio-economic analysis of energy systems, and agentbased modeling. He is a member of IEEJ, IEICE, ISCIE, JNNS, JSER, ORSJ and SICE.     

S-Club: an overlay-based efficient service discovery mechanism in CROWN Grid

Information service plays a key role in grid system, handles resource discovery and management process. Employing existing information service architectures suffers from poor scalability, long search response time, and large traffic overhead. In this paper, we propose a service club mechanism, called S-Club, for efficient service discovery. In S-Club, an overlay based on existing Grid Information Service (GIS) mesh network of CROWN is built, so that GISs are organized as service clubs. Each club serves for a certain type of service while each GIS may join one or more clubs. S-Club is adopted in our CROWN Grid and the performance of S-Club is evaluated by comprehensive simulations. The results show that S-Club scheme significantly improves search performance and outperforms existing approaches. Chunming Hu is a research staff in the Institute of Advanced Computing Technology at the School of Computer Science and Engineering, Beihang University, Beijing, China. He received his B.E. and M.E. in Department of Computer Science and Engineering in Beihang University. He received the Ph.D. degree in School of Computer Science and Engineering of Beihang University, Beijing, China, 2005. His research interests include peer-to-peer and grid computing; distributed systems and software architectures. Yanmin Zhu is a Ph.D. candidate in the Department of Computer Science, Hong Kong University of Science and Technology. He received his B.S. degree in computer science from Xi’an Jiaotong University, Xi’an, China, in 2002. His research interests include grid computing, peer-to-peer networking, pervasive computing and sensor networks. He is a member of the IEEE and the IEEE Computer Society. Jinpeng Huai is a Professor and Vice President of Beihang University. He serves on the Steering Committee for Advanced Computing Technology Subject, the National High-Tech Program (863) as Chief Scientist. He is a member of the Consulting Committee of the Central Government’s Information Office, and Chairman of the Expert Committee in both the National e-Government Engineering Taskforce and the National e-Government Standard office. Dr. Huai and his colleagues are leading the key projects in e-Science of the National Science Foundation of China (NSFC) and Sino-UK. He has authored over 100 papers. His research interests include middleware, peer-to-peer (P2P), grid computing, trustworthiness and security. Yunhao Liu received his B.S. degree in Automation Department from Tsinghua University, China, in 1995, and an M.A. degree in Beijing Foreign Studies University, China, in 1997, and an M.S. and a Ph.D. degree in computer science and engineering at Michigan State University in 2003 and 2004, respectively. He is now an assistant professor in the Department of Computer Science and Engineering at Hong Kong University of Science and Technology. His research interests include peer-to-peer computing, pervasive computing, distributed systems, network security, grid computing, and high-speed networking. He is a senior member of the IEEE Computer Society. Lionel M. Ni is chair professor and head of the Computer Science and Engineering Department at Hong Kong University of Science and Technology. Lionel M. Ni received the Ph.D. degree in electrical and computer engineering from Purdue University, West Lafayette, Indiana, in 1980. He was a professor of computer science and engineering at Michigan State University from 1981 to 2003, where he received the Distinguished Faculty Award in 1994. His research interests include parallel architectures, distributed systems, high-speed networks, and pervasive computing. A fellow of the IEEE and the IEEE Computer Society, he has chaired many professional conferences and has received a number of awards for authoring outstanding papers.     

A General Probability Formula of the Number of Location Areas＇ Boundaries Crossed by a Mobile Between Two Successive Call Arrivals

Mobility management is a challenging topic in mobile computing environment. Studying the situation of mobiles crossing the boundaries of location areas is significant for evaluating the costs and performances of various location management strategies. Hitherto, several formulae were derived to describe the probability of the number of location areas‘ boundaries crossed by a mobile. Some of them were widely used in analyzing the costs and performances of mobility management strategies. Utilizing the density evolution method of vector Markov processes, we propose a general probability formula of the number of location areas‘ boundaries crossed by a mobile between two successive calls. Fortunately, several widely-used formulae are special cases of the proposed formula.