Generation of templates for low-resolution text recognition using a hypothesis graph

We propose a recognition method of character-string images captured by portable digital cameras. A challenging task in character-string recognition is the segmentation of characters. In the proposed method, a hypothesis graph is used for recognition-based segmentation of the character-string images. The hypothesis graph is constructed by the subspace method, using eigenvectors as conditionally elastic templates. To obtain these templates, a generation-based approach is introduced in the training stage. Various templates are generated to cope with low-resolution. We have experimentally proved that the proposed scheme achieves high recognition performance even for low-resolution character-string images. The text was submitted by the authors in English. Hiroyuki Ishida. Received his B.S. and M.S. degrees from the Department of Information Engineering and from the Graduate School of Information Science, respectively, at Nagoya University. He is currently pursuing a Ph.D. in Information Science at Nagoya University. Ichiro Ide. Received his B.S. degree from the Department of Electronic Engineering, his M.S. degree from the Department of Information Engineering, and his Ph.D. from the Department of Electrical Engineering at the University of Tokyo. He is currently an Associate Professor in the Graduate School of Information Science at Nagoya University. Tomokazu Takahashi. Received his B.S. degree from the Department of Information Engineering at Ibaraki University, and his M.S. and Ph.D. from the Graduate School of Science and Engineering at Ibaraki University. His research interests include computer graphics and image recognition. Hiroshi Murase. Received his B.S., M.S., and Ph.D. degrees from the Graduate School of Electrical Engineering at Nagoya University. He is currently a Professor in the Graduate School of Information Science at Nagoya University. He received the Ministry Award from the Ministry of Education, Culture, Sports, Science and Technology in Japan in 2003. He is a Fellow of the IEEE.     

Efficient algorithms for NMR quantum computers with small qubits

The security of the RSA cryptosystems is based on the difficulty of factoring a large composite integer. In 1994, Shor showed that factoring a large composite is executable in polynomial time if we use a quantum Turing machine. Since this algorithm is complicated, straightforward implementations seem impractical judging from current technologies. In this paper, we propose simple and efficient algorithms for factoring and discrete logarithm problem based on NMR quantum computers. Our algorithms are easier to implement if we consider NMR quantum computers with small qubits. A part of this work was done while both authors were with NTT Communication Science Laboratories. Noboru Kunihiro, Ph.D.: He is Assistant Professor of the University of Electro-Communications. He received his B.E., M.E. and Ph.D. in mathematical engineering and information physics from the University of Tokyo in 1994, 1996 and 2001, respectively. He had been engaged in the research on cryptography and information security at NTT Communication Science Laboratories from 1996 to 2002. Since 2002, he has been working for Department of Information and Communication Engineering of the University of Elector-Communications. His research interest includes cryptography, information security and quantum computations. He was awarded the SCIS’97 paper prize. Shigeru Yamashita, Ph.D.: Associate Professor of Graduate School of Information Science, Nara Institute of Science and Technology, Nara 630-0192, Japan. He received his B.E., M.E. and Ph.D. degrees in information science from Kyoto University, Kyoto, Japan, in 1993, 1995 and 2001, respectively. His research interests include new type of computer architectures and quantum computation. He received the 2000 IEEE Circuits and Systems Society Transactions on Computer-Aided Design of Integrated Circuits and Systems Best Paper Award.     

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.     

Quantum Bit-commitment for small storage based on quantum one-way permutations

We propose a quantum bit-commitment scheme based on quantum one-way permutations with the unconditionally binding and computationally concealing property. Our scheme reduces exponentially the number of bits which the receiver needs to store until, the opening phase compared with the classical counterpart. Keisuke Tanaka, Ph.D.: He is Assistant Professor of Department of Mathematical and Computing Sciences at Tokyo Institute of Technology. He received his B.S. from Yamanashi University in 1992 and his M.S. and Ph.D. from Japan Advanced Institute of Science and Technology in 1994 and 1997, respectively. For each degree, he majored in computer science. Before joining Tokyo Institute of Technology, he was Research Engineer at NTT Information Sharing Platform Laboratories. His research interests are cryptography, quantum computation, circuit complexity, and the design and analysis of algorithms.     

A challenge towards next-generation research infrastructure for advanced life science

Recently, life scientists have expressed a strong need for computational power sufficient to complete their analyses within a realistic time as well as for a computational power capable of seamlessly retrieving biological data of interest from multiple and diverse bio-related databases for their research infrastructure. This need implies that life science strongly requires the benefits of advanced IT. In Japan, the Biogrid project has been promoted since 2002 toward the establishment of a next-generation research infrastructure for advanced life science. In this paper, the Biogrid strategy toward these ends is detailed along with the role and mission imposed on the Biogrid project. In addition, we present the current status of the development of the project as well as the future issues to be tackled. Haruki Nakamura, Ph.D.: He is Professor of Protein Informatics at Institute for Protein Research, Osaka University. He received his B.S., M.A. and Ph.D. from the University of Tokyo in 1975, 1977 and 1980 respectively. His research field is Biophysics and Bioinformatics, and has so far developed several original algorithms in the computational analyses of protein electrostatic features and folding dynamics. He is also a head of PDBj (Protein Data Bank Japan) to manage and develop the protein structure database, collaborating with RCSB (Research Collaboratory for Structural Bioinformatics) in USA and MSD-EBI (Macromolecular Structure Database at the European Bioinformatics Institute) in EU. Susumu Date, Ph.D.: He is Assistant Professor of the Graduate School of Information Science and Technology, Osaka University. He received his B.E., M.E. and Ph.D. degrees from Osaka University in 1997, 2000 and 2002, respectively. His research field is computer science and his current research interests include application of Grid computing and related information technologies to life sciences. He is a member of IEEE CS and IPSJ. Hideo Matsuda, Ph.D.: He is Professor of the Department of Bioinformatic Engineering, the Graduate School of Information Science and Technology, Osaka University. He received his B.S., M.Eng. and Ph.D. degrees from Kobe University in 1982, 1984 and 1987 respectively. For M.Eng. and Ph.D. degrees, he majored in computer science. His research interests include computational analysis of genomic sequences. He has been involved in the FANTOM (Functional Annotation of Mouse) Project for the functional annotation of RIKEN mouse full-length cDNA sequences. He is a member of ISCB, IEEE CS and ACM. Shinji Shimojo, Ph.D.: He received M.E. and Ph.D. degrees from Osaka University in 1983 and 1986 respectively. He was an Assistant Professor with the Department of Information and Computer Sciences, Faculty of Engineering Science at Osaka University from 1986, and an Associate Professor with Computation Center from 1991 to 1998. During the period, he also worked as a visiting researcher at the University of California, Irvine for a year. He has been Professor with Cybermedia Center (then Computation Center) at Osaka University since 1998. His current research work focus on a wide variety of multimedia applications, peer-to-peer communication networks, ubiquitous network systems and Grid technologies. He is a member of ACM, IEEE and IEICE.     

Open Mobile Alliance (OMA) security layer: Architecture, implementation and performance evaluation of the integrity unit

Security has become a very critical issue in the provision of mobile services. The Open Mobile Alliance (OMA) has specified a powerful security layer, the WTLS. In this paper, a VLSI architecture for the implementation of the WTLS integrity unit is proposed. The proposed architecture is reconfigurable in the sense that operates in three different modes: as Keyed-Hash Authentication Code (HMAC), as SHA-1 and MD5 hash functions, according to WTLS specifications. This multi-mode operation is achieved due to the reconfigurable applied design technique in the proposed architecture, which keeps the allocated area resources at a minimized level. The proposed architecture achieves high speed performance, due to the pipeline designed architecture. Especially, SHA-1 operation achieved throughput is equal to 1,7 Gbps, while MD5 operation mode bit rate is equal to 2,1 Gbps. The proposed architecture has been integrated by using VHDL and has been synthesized placed and routed in an FPGA device. Comparisons with related hash functions implementations have been done in terms of throughput, operating frequency, allocated area and Area-Delay product. The achieved performance of the SHA-1 operation mode is better at about 14–42 times compared with the other conventional works. In addition, MD5 performance is superior to the other works at about 6–18 times, in all of the cases. The proposed Integrity Unit is a very trustful and powerful solution for the WTLS layer. In addition, it can be integrated in security systems which are used for the implementation networks for wireless protocols, with special needs of integrity in data transmission. Nicolas Sklavos, Ph.D.: He is a Ph.D. Researcher with the Electrical and Computer Engineering Department, University of Patras, Greece. His interests include computer security, new encryption algorithms design, wireless communications and reconfigurable computing. He received an award for his Ph.D. thesis on “VLSI Designs of Wireless Communications Security Systems” from IFIP VLSI SOC 2003. He is a referee of International Journals and Conferences. He is a member of the IEEE, the Technical Chamber of Greece and the Greek Electrical Engineering Society. He has authored or co-authored up to 50 scientific articles in the areas of his research. Paris Kitsos, Ph.D.: He is currently pursuing his Ph.D. in the Department of Electrical and computer Engineering, University of Patras, Greece. He received the B.S. in Physics from the University of Patras in 1999. His research interests include VLSI design, hardware implementations of cryptography algorithms, security protocols for wireless communication systems and Galois field arithmetic implementations. He has published many technical papers in the areas of his research. Epaminondas Alexopoulos: He is a student of the Department of Electrical and Computer Engineering, University of Patras, Greece. His research includes hardware implementations, mobile computing and security. He has published papers in the areas of his research. Odysseas Koufopavlou, Ph.D.: He received the Diploma of Electrical Engineering in 1983 and the Ph.D. degree in Electrical Engineering in 1990, both from University of Patras, Greece. From 1990 to 1994 he was at the IBM Thomas J. Watson Research Center, Yorktown Heights, NY, USA. He is currently an Associate Professor at the Department of Electrical and Computer Engineering, University of Patras. His research interests include VLSI, low power design, VLSI crypto systems and high performance communication subsystems architecture and implementation. He has published more than 100 technical papers and received patents and inventions in these areas.     

Secure software infrastructure in the internet age

The rapid growth and penetration of the Internet are now leading us to a world where networks are ubiquitous and everything is connected. Breaking the distance barrier by the ubiquitous connection, however, is a two-edged sword. Our network infrastructure today is still fragile and thus “everything is connected” may simply mean “everything can be attacked from whatever place on the earth.” In this paper, we first point out the importance and inherent problems of software systems that underlay open and extensible networks, especially the Internet. We put emphasis on software since software vulnerabilities account for most attacks, incidents, or even disasters on the Internet today. Next we present general ideas of promising techniques in defense of software systems, including theoretical, language-based, and runtime solutions. Finally, we show our experience in developing a secure mail system. Etsuya Shibayama, D.Sc.: He is a professor of the Graduate School of Information Science and Engineering at Tokyo Institute of Technology. He received B.Sc. and M.Sc. in mathematical sciences from Kyoto University in 1981 and 1983, respectively, and D.Sc. in information science from the University of Tokyo in 1991. He is interested in various topics in software including design and implementation of textual and visual programming languages, system software, and user interface software. Recently, he has been doing research on language-based software security and methodologies for building secure software. Akinori Yonezawa, Ph.D.: He is a Professor of computer science at Department of Computer Science, the University of Tokyo. He received his Ph.D. in Computer Science form the Massachusetts Institute of Technology in 1977. His current major research interests are in the areas of concurrent/parallel computation models, programming languages, object-oriented computing and distributed computing. He is the designer of and object-oriented concurrent language ABCL/1 and the editor of several books and served as an associate editor of ACM Transaction of Programming Language and Systems (TOPLAS). Since 1998, he has been an ACM Fellow.     

Discover unknown causes from inferred and visualized Co-occurring events

It is hard to have knowledge including all events which may have caused observed events. This makes it difficult to infer significant causes of observed events. However, unexpected relations detected between known events by a computer suggest unknown events to humans, being combined with the vast human knowledge acquired by rich experience. This paper presents a method to have a computer express “unknown” hidden causes, i.e. not included in the given knowledge. The inference method of the computer, for inferring known causes of observed time-series events, is Cost-based Cooperation of Multi-Abducers (CCMA) here aiming at detecting unexpectedly strong co-occurrences among known events. The detected relations are expressed to user, which makes significant unknown causal events easily understood. The empirical results encourages that the presented method helps in discovering significant unknown events. Yukio Ohsawa, Ph.D.: He is an Associate Professor in the Graduate School of Systems Management, University of Tsukuba. He obtained his bachelors, masters, and Ph.D. degrees in Engineering from the University of Tokyo in 1990, 1992 and 1995 respectively. He was a research associate in Osaka University from 1995 to 1999. His research interests are in discovering signs of future events affecting human life, from data, based on his background of artificial intelligence. He received the Paper Award from the Japanese Society of Artificial Intelligence in 1999 and some awards for conference papers. He has served on program commitees of several conferences and workshops on AI and agents, currently chairing Multi-agent and Cooperative Computing workshops (MACC99). Masahiko Yachida, Ph.D.: He is a professor at the Dept. of Systems Engineering of Osaka University since 1993. He obtained his B. E., M.Sc in electrical engineering and Ph.D. in control engineering from Osaka University in 1969, 1971, and 1976 respectively. He became a professor of the Dept. of Information and Computer Science of the same university in 1990, and moved to the current department as a professor. He was a research fellow at the Fachbereich Informatik, Hamburg University from 1981 to 1982, and a CDC professor at the Dept. of Computer Science, University of Minessota in 1983. He received several prizes including Ohkawa Publishing Prize, and is presently a Chairman of Technical Committee on Pattern Recognition & Media Understanding.     

A quantum algorithm using NMR computers to break secret-key cryptosystems

In this paper, we discuss quantum algorithms that, for a given plaintextm _o and a given ciphertextc _o, will find a secret key,k _o, satisfyingc _o=E(k _o,m _o), where an encryption algorithm,E, is publicly available. We propose a new algorithm suitable for an NMR (Nuclear Magnetic Resonance) computer based on the technique used to solve the counting problem. The complexity of, our algorithm decreases as the measurement accuracy of the NMR computer increases. We discuss the possibility that the proposed algorithm is superior to Grover’s algorithm based on initial experimental results. Kazuo Ohta, Dr.S.: He is Professor of Faculty of Electro-Communications at the University of Electro-Communications, Japan. He received B.S., M.S., and Dr. S. degrees from Waseda University, Japan, in 1977, 1979, and 1990, respectively. He was researcher of NTT (Nippon Telegraph and Telephone Corporation) from 1979 to 2001, and was visiting scientist of Laboratory for Computer Science e of MIT (Massachusetts Institute of Technology) in 1991–1992 and visiting Professor of Applied Mathematics of MIT in 2000. He is presently engaged in research on Information Security, and theoretical computer science. Dr. Ohta is a member of IEEE, the International Association for Cryptologic Research, the Institute of Electronics, Information and Communication Engineers and the Information Processing Society of Japan. Tetsuro Nishino,: He received the B.S., M.S. and, D.Sc. degrees in mathematics from Waseda University, in 1982, 1984, and 1991 respectively. From 1984 to 1987, he joined Tokyo Research Laboratory, IBM Japan. From 1987 to 1992, he was a Research Associate of Tokyo Denki University, and from 1992 to 1994, he was an Associate Professor of Japan Advanced Institute of Science and Technology, Hokuriku. He is presently an Associate Professor in the Department of Communications and Systems Engineering, the University of Electro-Communications. His main interests are circuit complexity theory, computational learning theory and quantum complexity theory. Seiya Okubo,: He received the B.Eng. and M.Eng. degrees from the University of Electro-Communications in 2000 and 2002, respectively. He is a student in Graduate School of Electro-Communications, the University of Electro-Communications. His research interests include quantum complexity theory and cryptography. Noboru Kunihiro, Ph.D.: He is Assistant Professor of the University of Electro-Communications. He received his B. E., M. E. and Ph. D. in mathematical engineering and information physics from the University of Tokyo in 1994, 1996 and 2001, respectively. He had been engaged in the research on cryptography and information security at NTT Communication Science Laboratories from 1996 to 2002. Since 2002, he has been working for Department of Information and Communication Engineering of the University of Elector-Communications. His research interests include cryptography, information security and quantum computations. He was awarded the SCIS’97 paper prize.     

A study on effects of market systems in an artificial market

In an artificial market approach with multi-agent systems, the static equilibrium concept is often used in market systems to approximate continuous market auctions. However, differences between the static equilibrium concept and continuous auctions have not been discussed in the context of an artificial market study. In this paper, we construct an artificial market model with both of them, namely, the Itayose and Zaraba method, and show simple characteristic differences between these methods based on computer simulations. The result indicates the further need to model the market system by studying artificial markets. Hidenori Kawamura, Ph.D.: He received Ph.D. degree from Division of Systems and Information Engineering, Graduate School of Engineering, Hokkaido University, Japan in 2000. He is currently an instructor in Graduate School of Information Science and Technology, Hokkaido University, Japan. His research interests include multiagent systems, mass user support, artificial intelligence, complex systems, and tourism informatics. He is a member of IPSJ, JSAI, IEICE, ORSJ, JSTI and AAAI. Yasushi Okada, Ph.D.: He is a master course student in Graduate School of Engineering, Hokkaido University, Japan. He studies multiagent systems. Azuma Ohuchi, Ph.D.: He received his Ph.D. degree in 1974 from Hokkaido University. He is currently the professor in Graduate School of Information Science and Technology, Hokkaido University Japan. His research interstes include systems information engineering, artificial intelligence, complex systems, tourism informatics and medical systems. He is a member of the IPSJ, JSAI, IEEJ, ORSJ, Soc. Contr. Eng., Jap. OR Soc., Soc. Med. Informatics, Hosp. Manag., JSTI and IEEE-SMC. Koichi Kurumatani, Ph.D.: He received his Ph.D. Degree in 1989 from The University of Tokyo. He is currently a leader of Multiagent Research Team in Cyber Assist Research Center (CARC), National Institute of Advanced Industrial Science and Technology (AIST), Japan. His research interests include multiagent systems and mass user support. He is a member of JSAI, IPSJ, JSTI and AAAI.     

RHiNET-2/SW: a high-throughput, compact network-switch using 8.8-gbit/s optical interconnection

We have developed a high-throughput, compact network switch (the RHiNET-2/SW) for a distributed parallel computing system. Eight pairs of 800-Mbit/s×12-channel optical interconnection modules and a CMOS ASIC switch are integrated on a compact circuit board. To realize high-throughput (64 Gbit/s) and low-latency network, the SW-LSI has a customized high-speed LVDS I/O interface, and a high-speed internal SRAM memory in a 784-pin BGA one-chip package. We have also developed device implementation technologies to overcome the electrical problems (loss and crosstalk) caused by such high integration. The RHiNET-2/SW system enables high-performance parallel processing in a distributed computing environment. Shinji Nishimura: He is a researcher in the Department of Network System at the Central Research Laboratory, Hitachi Ltd., at Tokyo. He obtained his bachelors degree in Electronics Engineering from the University of Tokyo in 1989, and his M.E. from the University of Tokyo in 1991. He joined a member of the Optical Interconnection Hitachi Laboratory from 1992. His research interests are in hardware technology for the optical interconnection technologies in the computer and communication systems. Katsuyoshi Harasawa: He is a Senior Enginner of Hitachi Communication Systems Inc. He obtained his bachelors degree in Electrical Engineering from Tokyo Denki University. He is a chief of development of the devices and systems for the optical telecommunication. He was engaged in Development of Optical Reciever and Transmitter module. He joined RWCP project from 1997. His research interests are in hardward technology for optical interconnection in distributed parallel computing system (RHiNET). Nobuhiro Matsudaira: He is a engineer in the Hitachi Communication Systems, Inc. He obtained his bachelors degree in Mercantile Marine Engineering from the Kobe University of Mercantile Marine in 1986. He was engaged in Development of Optical Reciever and Transmitter module at 2.4 Gbit/s to 10Gbit/s. He joined RWCP project from 1998. His reserch interests are in hardware technology for the optical interconnection technology in the computer and communication systems. Shigeto Akutsu: He is a staff in Hitachi Communication Systems Inc. He obtained his bachelors degree in Electronics from Kanagawa University, Japan in 1998. His research interests are hardware technology for the optical interconnection technology in the computer and communication systems. Tomohiro Kudoh, Ph.D.: He received Ph.D. degree from Keio University, Japan in 1992. He has been chief of the parallel and distributed architecture laboratory, Real World Computing Partnership since 1997. His research interests include the area of parallel processing and network for high performance computing. Hiroaki Nishi: He received B.E., M.E. from Keio University, Japan, in 1994, 1996, respectively. He joined Parallel & Distributed Architecture Laboratory, Real World Computing Partnership in 1999. He is currently working on his Ph.D. His research interests include area of interconnection networks. Hideharu Amano, Ph.D.: He received Ph.D. degree from Keio University, Japan in 1986. He is now an Associate Professor in the Department of Information and Computer Science, Keio University. His research interests include the area of parallel processing and reconfigurable computing.     

Privacy-preserving SVM classification

Traditional Data Mining and Knowledge Discovery algorithms assume free access to data, either at a centralized location or in federated form. Increasingly, privacy and security concerns restrict this access, thus derailing data mining projects. What is required is distributed knowledge discovery that is sensitive to this problem. The key is to obtain valid results, while providing guarantees on the nondisclosure of data. Support vector machine classification is one of the most widely used classification methodologies in data mining and machine learning. It is based on solid theoretical foundations and has wide practical application. This paper proposes a privacy-preserving solution for support vector machine (SVM) classification, PP-SVM for short. Our solution constructs the global SVM classification model from data distributed at multiple parties, without disclosing the data of each party to others. Solutions are sketched out for data that is vertically, horizontally, or even arbitrarily partitioned. We quantify the security and efficiency of the proposed method, and highlight future challenges. Jaideep Vaidya received the Bachelor’s degree in Computer Engineering from the University of Mumbai. He received the Master’s and the Ph.D. degrees in Computer Science from Purdue University. He is an Assistant Professor in the Management Science and Information Systems Department at Rutgers University. His research interests include data mining and analysis, information security, and privacy. He has received best paper awards for papers in ICDE and SIDKDD. He is a Member of the IEEE Computer Society and the ACM. Hwanjo Yu received the Ph.D. degree in Computer Science in 2004 from the University of Illinois at Urbana-Champaign. He is an Assistant Professor in the Department of Computer Science at the University of Iowa. His research interests include data mining, machine learning, database, and information systems. He is an Associate Editor of Neurocomputing and served on the NSF Panel in 2006. He has served on the program committees of 2005 ACM SAC on Data Mining track, 2005 and 2006 IEEE ICDM, 2006 ACM CIKM, and 2006 SIAM Data Mining. Xiaoqian Jiang received the B.S. degree in Computer Science from Shanghai Maritime University, Shanghai, 2003. He received the M.C.S. degree in Computer Science from the University of Iowa, Iowa City, 2005. Currently, he is pursuing a Ph.D. degree from the School of Computer Science, Carnegie Mellon University. His research interests are computer vision, machine learning, data mining, and privacy protection technologies.     

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.     

PAI: Automatic indexing for extracting asserted keywords from a document

This paper proposes an automatic indexing method named PAI (Priming Activation Indexing) that extracts keywords expressing the author’s main point from a document based on the priming effect. The basic idea is that since the author writes a document emphasizing his/her main point, impressive terms born in the mind of the reader could represent the asserted keywords. Our approach employs a spreading activation model without using corpus, thesaurus, syntactic analysis, dependency relations between terms or any other knowledge except for stop-word list. Experimental evaluations are reported by applying PAI to journal/conference papers. Naohiro Matsumura: He received his B.S. and M.S. in Engineering Science from Osaka University in 1998 and 2000. Currently, he is a Ph.D. candidate in Engineering at the University of Tokyo and a research staff of PRESTO of Japan Science and Technology Corporation (2000–). His research interests include chance discovery, computer-mediated communication, and user-oriented data mining/text mining. Yukio Ohsawa, Ph.D.: BS, U. Tokyo, 1990, MS, 1992, DS, 1995. Research associate Osaka U. (1995). Associate prof. Univ. of Tsukuba (1999–) and also researcher of Japan Science and Technology Corp (2000–). He has been working for the program com. of the Workshop on Multiagent and Cooperative Computation, Annual Conf. Japanese Soc. Artificial Intelligence, International Conf. MultiAgent Systems, Discovery Science, Pacific Asia Knowledge Discovery and Data Mining, International Conference on Web Intelligence, etc. He chaired the First International Workshop of Japanese Soc. on Artificial Intelligence, Chance Discovery International Workshop Series and the Fall Symposium on Chance Discovery from AAAI. Guest editor of Special Issues on Chance Discovery for the Journal of Contingencies and Crisis Management, Journal of Japan Society for Fuzzy Theory and intelligent informatics, regular member of editorial board for Japanese Society of Artificial Intelligence. Currently he is authoring book “Chance Discovery” from Springer Verlag, “Knowledge Managament” from Ohmsha etc. Mitsuru Ishizuka, Ph.D.: He is a professor at the Dept. of Infomation and Communication Eng., School of Information Science and Thechnology, the Univ. of Tokyo. Prior to this position, he worked at NTT Yokosuka Lab. and the Institute of Industrial Science, the Univ. of Tokyo. He earned his B.S., M.S. and Ph.D. in electronic engineering from the Univ. of Tokyo. His research interests include artificial intelligence, WWW intelligence, and multimodal lifelike agents. He is a member of IEEE, AAAI, IEICE Japan, IPS Japan, and Japanese Society for AI.     

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.     

A multi-threshold online smoothing technique for variable rate multimedia streams

Variable bit rate (VBR) compression for media streams allocates more bits to complex scenes and fewer bits to simple scenes. This results in a higher and more uniform visual and aural quality. The disadvantage of the VBR technique is that it results in bursty network traffic and uneven resource utilization when streaming media. In this study we propose an online media transmission smoothing technique that requires no a priori knowledge of the actual bit rate. It utilizes multi-level buffer thresholds at the client side that trigger feedback information sent to the server. This technique can be applied to both live captured streams and stored streams without requiring any server side pre-processing. We have implemented this scheme in our continuous media server and verified its operation across real world LAN and WAN connections. The results show smoother transmission schedules than any other previously proposed online technique. This research has been funded in part by NSF grants EEC-9529152 (IMSC ERC), and IIS-0082826, DARPA and USAF under agreement nr. F30602-99-1-0524, and unrestricted cash/equipment gifts from NCR, IBM, Intel and SUN. Roger Zimmermann is currently a Research Assistant Professor with the Computer Science Department and a Research Area Director with the Integrated Media Systems Center (IMSC) at the University of Southern California. His research activities focus on streaming media architectures, peer-to-peer systems, immersive environments, and multimodal databases. He has made significant contributions in the areas of interactive and high quality video streaming, collaborative large-scale group communications, and mobile location-based services. Dr. Zimmermann has co-authored a book, a patent and more than seventy conference publications, journal articles and book chapters in the areas of multimedia and databases. He was the co-chair of the ACM NRBC 2004 workshop, the Open Source Software Competition of the ACM Multimedia 2004 conference, the short paper program systems track of ACM Multimedia 2005 and will be the proceedings chair of ACM Multimedia 2006. He is on the editorial board of SIGMOD DiSC, the ACM Computers in Entertainment magazine and the International Journal of Multimedia Tools and Applications. He has served on many conference program committees such as ACM Multimedia, SPIE MMCN and IEEE ICME. Cyrus Shahabi is currently an Associate Professor and the Director of the Information Laboratory (InfoLAB) at the Computer Science Department and also a Research Area Director at the NSF's Integrated Media Systems Center (IMSC) at the University of Southern California. He received his M.S. and Ph.D. degrees in Computer Science from the University of Southern California in May 1993 and August 1996, respectively. His B.S. degree is in Computer Engineering from Sharif University of Technology, Iran. He has two books and more than hundred articles, book chapters, and conference papers in the areas of databases and multimedia. Dr. Shahabi's current research interests include Peer-to-Peer Systems, Streaming Architectures, Geospatial Data Integration and Multidimensional Data Analysis. He is currently an associate editor of the IEEE Transactions on Parallel and Distributed Systems (TPDS) and on the editorial board of ACM Computers in Entertainment magazine. He is also the program committee chair of ICDE NetDB 2005 and ACM GIS 2005. He serves on many conference program committees such as IEEE ICDE 2006, ACM CIKM 2005, SSTD 2005 and ACM SIGMOD 2004. Dr. Shahabi is the recipient of the 2002 National Science Foundation CAREER Award and 2003 Presidential Early Career Awards for Scientists and Engineers (PECASE). In 2001, he also received an award from the Okawa Foundations. Kun Fu is currently a Ph.D candidate in computer science from the University of Southern California. He did research at the Data Communication Technology Research Institute and National Data Communication Engineering Center in China prior to coming to the United States and is currently working on large scale data stream recording architectures at the NSF's Integrated Media System Center (IMSC) and Data Management Research Laboratory (DMRL) at the Computer Science Department at USC. He received an MS in engineering science from the University of Toledo. He is a member of the IEEE. His research interests are in the area of scalable streaming architectures, distributed real-time systems, and multimedia computing and networking. Mehrdad Jahangiri was born in Tehran, Iran. He received the B.S. degree in Civil Engineering from University of Tehran at Tehran, in 1999. He is currently working towards the Ph.D. degree in Computer Science at the University of Southern California. He is currently a research assistant working on multidimensional data analysis at Integrated Media Systems Center (IMSC)—Information Laboratory (InfoLAB) at the Computer Science Department of the University of Southern California.     

Privacy preservation for data cubes

A range query finds the aggregated values over all selected cells of an online analytical processing (OLAP) data cube where the selection is specified by the ranges of contiguous values for each dimension. An important issue in reality is how to preserve the confidential information in individual data cells while still providing an accurate estimation of the original aggregated values for range queries. In this paper, we propose an effective solution, called the zero-sum method, to this problem. We derive theoretical formulas to analyse the performance of our method. Empirical experiments are also carried out by using analytical processing benchmark (APB) dataset from the OLAP Council. Various parameters, such as the privacy factor and the accuracy factor, have been considered and tested in the experiments. Finally, our experimental results show that there is a trade-off between privacy preservation and range query accuracy, and the zero-sum method has fulfilled three design goals: security, accuracy, and accessibility. Sam Y. Sung is an Associate Professor in the Department of Computer Science, School of Computing, National University of Singapore. He received a B.Sc. from the National Taiwan University in 1973, the M.Sc. and Ph.D. in computer science from the University of Minnesota in 1977 and 1983, respectively. He was with the University of Oklahoma and University of Memphis in the United States before joining the National University of Singapore. His research interests include information retrieval, data mining, pictorial databases and mobile computing. He has published more than 80 papers in various conferences and journals, including IEEE Transaction on Software Engineering, IEEE Transaction on Knowledge & Data Engineering, etc. Yao Liu received the B.E. degree in computer science and technology from Peking University in 1996 and the MS. degree from the Software Institute of the Chinese Science Academy in 1999. Currently, she is a Ph.D. candidate in the Department of Computer Science at the National University of Singapore. Her research interests include data warehousing, database security, data mining and high-speed networking. Hui Xiong received the B.E. degree in Automation from the University of Science and Technology of China, Hefei, China, in 1995, the M.S. degree in Computer Science from the National University of Singapore, Singapore, in 2000, and the Ph.D. degree in Computer Science from the University of Minnesota, Minneapolis, MN, USA, in 2005. He is currently an Assistant Professor of Computer Information Systems in the Management Science & Information Systems Department at Rutgers University, NJ, USA. His research interests include data mining, databases, and statistical computing with applications in bioinformatics, database security, and self-managing systems. He is a member of the IEEE Computer Society and the ACM. Peter A. Ng is currently the Chairperson and Professor of Computer Science at the University of Texas—Pan American. He received his Ph.D. from the University of Texas–Austin in 1974. Previously, he had served as the Vice President at the Fudan International Institute for Information Science and Technology, Shanghai, China, from 1999 to 2002, and the Executive Director for the Global e-Learning Project at the University of Nebraska at Omaha, 2000–2003. He was appointed as an Advisory Professor of Computer Science at Fudan University, Shanghai, China in 1999. His recent research focuses on document and information-based processing, retrieval and management. He has published many journal and conference articles in this area. He had served as the Editor-in-Chief for the Journal on Systems Integration (1991–2001) and as Advisory Editor for the Data and Knowledge Engineering Journal since 1989.     

Toward a real-world knowledge medium: Building a guidance system for exhibition tours

We propose a notion of a real-world knowledge medium by presenting our ongoing project to build a guidance system for exhibition tours. In order to realize a knowledge medium usable in the real world, we focus on the context-awareness of users and their environments. Our system is a personal mobile assistant that provides visitors touring exhibitions with information based on their spatial/temporal locations and individual interests. We also describe an application of knowledge sharing used in the actual exhibition spaces. Yasuyuki Sumi, Ph.D.: He has been a researcher at ATR Media Integration & Communications Research Laboratories since 1995. His research interests include knowledge-based systems, creativity supporting systems, and their applications for facilitating human collaboration. He received his B. Eng. degree from Waseda University in 1990, and M. Eng. and D. Eng. degrees in information engineering from the University of Tokyo in 1992 and 1995, respectively. He is a member of Institutes of Electronics, Information and Communication Engineers (IEICE) of Japan, the Information Processing Society of Japan (IPSJ), the Japanese Society for Artificial Intelligence (JSAI), and American Association for Artificial Intelligence (AAAI). Kenji Mase, Ph.D.: He received the B.S. degree in Electrical Engineering and the M.S. and Ph.D. degrees in Information Engineering from Nagoya University in 1979, 1981 and 1992 respectively. He has been with ATR (Advanced Telecommunications Research Institute) Media Integration & Communications Research Laboratories since 1995 and is currently the head of Department 2. He joined the Nippon Telegraph and Telephone Corporation (NTT) in 1981 and had been with the NTT Human Interface Laboratories. He was a visiting researcher at the Media Laboratory, MIT in 1988–1989. His research interests include image sequence processing of human actions, computer graphics, computer vision, artificial intelligence and their applications for computer-aided communications and human-machine interfaces. He is a member of the Information Processing Society of Japan (IPSJ), Institutes of Electronics, Information and Communication Engineers (IEICE) of Japan and IEEE Computer Society.     

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