Dept of Computer Science

DEPT OF COMPUTER SCIENCE

Researcher : Bo P

List of Research Outputs

Bo P. and Wang W.P., Geodesic-controlled developable surfaces for modeling paper bending, Computer Graphics Forum, (Eurographics 2007). 2007, vol. 26, no. 3.

Researcher : Chan B

List of Research Outputs

Wang L., Tu C., Wang W.P., Meng X., Chan B. and Yan D., Silhouette smoothing for real-time rendering of mesh surfaces, IEEE Transactions on Visualization and Computer Graphics. USA, IEEE Computer Society, 2008, 14: 640-652.

Researcher : Chan HL

List of Research Outputs

Chan H.L., Lam T.W. and Liu K.S., Extra Unit-Speed Machines Are Almost as Powerful as Speedy Machines for Flow Time Scheduling, SIAM Journal on Computing. USA, SIAM, 2008, 37:5: 1595-1612.

Chan H.L., Lam T.W., Sung W.K., Wong P.W.H. and Yiu S.M., Non-overlapping Common Substrings Allowing Mutations , Mathematics in Computer Science. Springer, 2008, 543-555.

Researcher : Chan HW

Project Title:	Anonymity in Web transactions
Investigator(s):	Chan HW
Department:	Computer Science
Source(s) of Funding:	Small Project Funding
Start Date:	01/2006

Abstract:

Privacy issue is always a concern for certain individuals with the proliferation of emails and transactions on the Web. In most of the current communication systems, information such as our identity (IP address) is exposed and kept by another party. Web server log files contain information about the users who visit them and the content they access. The server can record the user's IP address and often the user's Internet domain name, workplace, and/or approximate location, the type of computing platform used. The Web page that referred the user to this site and the server that is going to be visited next are all possibly contained within the request header. Even when the user's IP address changes between browsing sessions (e.g., the IP address is assigned dynamically using DHCP), a Web server can link multiple sessions by the same user by planting a unique cookie in the user' s browser during the first browsing session, and retrieving that cookie in subsequent sessions. Thus, various sites on the Internet collect a great amount of personal information about the individuals who visit them. This information can be used to generate consumer and communication profiles. The same monitoring capabilities are available to the user's ISP or local gateway administrator who can observe all communication in which the user participates. The user's profile made possible by such monitoring capabilities is viewed as a useful tool because a Web server can use such information to personalize its content for its users. However, user's privacy is compromised. In spite of a lack of privacy has always characterized Internet communication, a general acceptance that Internet communication has been logged universally and revealed so much about the personal tastes of its users is to be scrutinized. Web users should have the ability to limit what information is revealed about them and to whom it is revealed. While encrypting communication to and from web servers (e.g., using SSL) can hide the content of the transaction from an Internet service provider, or a local system administrator, they can still learn a lot about the client and server computers, the length of the data being exchanged, and the time and frequency of exchanges. Encryption indeed does little to protect the privacy of the client from the server. A web server can record the Internet addresses at which its clients reside, the servers that referred the clients to it, and the times and frequencies of accesses by its clients. Although some approaches enable users to negotiate the conditions under which they will share potentially private information with a Web server, these negotiations apply only to the server, only for certain kinds of information (for example, not the user's IP address), cannot be enforced, and are not presently widely practised. Other methods are definitely needed as well. Anonymity is a way not to release the identity and personal information of the individual. With the use of a proxy server, some degree of anonymity can be provided. However, it may still be possible to reveal our approximate location by examining the address of proxy server. Advertising company can use the information collected to decide which banner to show according to user location. With the use of cookies, the behavior of a visitor can be tracked when he/she visits another site embedded with web bugs. Therefore, individual privacy on the Internet is endangered and is of utmost concern for some. Since privacy cannot be protected solely by legislation, technologies that can be used to enforce privacy are needed. Anonymity for privacy protection is one possible solution, because if users are anonymous on a network, they need not worry about the loss of their privacy. The aim of the research is to design an efficient scheme for anonymous communication in web transactions. With such scheme, involved party should not be able to have an idea of whom and where the information requester is.

List of Research Outputs

Chow K.P., Cheng K.Y., Man L.Y., Lai K.Y., Hui C.K., Chong C.F., Pun K.H., Tsang W.W., Chan H.W. and Yiu S.M., BTM—An Automated Rule-Based BT Monitoring System for Piracy Detection, The Second International Conference on Internet Monitoring and Protection, ICIMP 2007. Silicon Valley, USA, IEEE Computer Society Press, 6 pages.

Li Z., Chong C.F., Hui C.K., Yiu S.M., Chow K.P., Tsang W.W., Chan H.W. and Pun K.H., An Attack on Libert et al.’s ID-Based Undeniable Signature Scheme, International Journal of Network Security. Seoul, Korea, 2007, Vol. 5, No. 2: 220-223.

Researcher : Chan KP

List of Research Outputs

Chan K.P., Chen T.Y. and Towey D.P., Controlling Restricted Random Testing: An Examination of the Exclusion Ratio Parameter, The Nineteenth International Conference on Software Engineering and Knowledge Engineering. Boston, U.S.A., 2007.

Researcher : Chan WK

List of Research Outputs

Chan W.K., Ho J.C.F., Tse T.H. and Yu Y.T., Piping classification to metamorphic testing: an empirical study towards better effectiveness for the identification of failures in mesh simplification programs, Proceedings of the 31st Annual International Computer Software and Applications Conference (COMPSAC 2007), IEEE Computer Society Press, Los Alamitos, CA (acceptance rate: 18%). Los Alamitos, California, IEEE Computer Society Press, 2007, 397−404.

Lu H., Chan W.K. and Tse T.H., Testing pervasive software in the presence of context inconsistency resolution services, Proceedings of the 30th International Conference on Software Engineering (ICSE 2008), ACM Press, New York, NY (acceptance rate: 15.1%). 2008, 61−70.

Mei L., Chan W.K. and Tse T.H., Data flow testing of service-oriented workflow applications, Proceedings of the 30th International Conference on Software Engineering (ICSE 2008), ACM Press, New York, NY (acceptance rate: 15.1%). 2008, 371−380.

Tse T.H., Lau F.C.M., Chan W.K., Liu P.C.K. and Luk C.K.F., Testing of object-oriented industrial software without precise oracles or results, Communications of the ACM (acceptance rate: < 15%). New York, ACM Press, 2007, 50 (8): 78−85.

Zhang Z., Chan W.K. and Tse T.H., Synthesizing component-based WSN applications via automatic combination of code optimization techniques, Proceedings of the 7th International Conference on Quality Software (QSIC 2007), IEEE Computer Society Press, Los Alamitos, CA. 2007, 181−190.

Researcher : Chan WT

Project Title:	Algorithm issues on on-request data dissemination: scheduling algorithms and performance guarantee
Investigator(s):	Chan WT, Lam TW, Ting HF
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	12/2003

Abstract:

To solve the problem on deciding when to disseminate which page so as to optimize a pre-defined performance measure, such as the response time of a request, by giving online scheduling algorithms with performance guarantee; to introduce a formal performance comparison analysis between two (unicast or multicast) DDS with different resource settings; to study and solve the scheduling problems for some practical considerations.

List of Research Outputs

Chan W.T., Chin F.Y.L., Ye D., Zhang G. and Zhang Y., On-line scheduling of parallel jobs on two machines, Journal of Discrete Algorithms . Amsterdam, The Netherlands, Elsevier Science Publishers B. V., 2008, 6(1): 3-10.

Researcher : Chen L

List of Research Outputs

Chen L., Wang C.L. and Lau F.C.M., Process Reassignment with Reduced Migration Cost in Grid Load Rebalancing, 17th International Heterogeneity in Computing Workshop (HCW 2008) . IEEE, 2008.

Researcher : Chen TY

List of Research Outputs

Wong W.E., Tse T.H., Glass R.L., Basili V.R. and Chen T.Y., An assessment of systems and software engineering scholars and institutions (2001−2005), Journal of Systems and Software. 2008, 81 (6): 1059−1062.

Researcher : Cheng CK

List of Research Outputs

Cheng C.K., Managing Spatial Uncertainty in a Database System, the POLYNET IT Security Symposium 2008, Hong Kong Polytechnic University (HKPU). 2008.

Cheng C.K., Chen J.C., Mokbel M. and Chow C.Y., Probabilistic Verifiers: Evaluating Constrained Probabilistic Nearest-Neighbor Queries over Uncertain Data, IEEE Intl. Conf. on Data Engineering (IEEE ICDE 2008). 2008, 973-982.

Singh S., Mayfield C., Shah R., Prabhakar S., Hambrusch S., Neville J. and Cheng C.K., Database Support for Probabilistic Attributes and Tuples, IEEE Intl. Conf. on Data Engineering (IEEE ICDE 2008). 2008, 1053-1061.

Researcher : Cheng KH

List of Research Outputs

Cheng K.H., The Chi-square Test when the Expected Frequencies are Less than 5. Hong Kong, 2008.

Researcher : Cheng KSD

List of Research Outputs

Cheng K.S.D., Wang W.P., Qin H., Wong K.K.Y., Yang H.P. and Liu Y., Design and Analysis of Optimization Methods for Subdivision Surface Fitting, IEEE Transactions on Visualization and Computer Graphics. 2007, 13(5): 878-890.

Researcher : Cheng KY

List of Research Outputs

Chow K.P., Cheng K.Y., Man L.Y., Lai K.Y., Hui C.K., Chong C.F., Pun K.H., Tsang W.W., Chan H.W. and Yiu S.M., BTM—An Automated Rule-Based BT Monitoring System for Piracy Detection, The Second International Conference on Internet Monitoring and Protection, ICIMP 2007. Silicon Valley, USA, IEEE Computer Society Press, 6 pages.

Researcher : Cheung DWL

Project Title:	Mining association rules on high performance parallel systems
Investigator(s):	Cheung DWL
Department:	Computer Science
Source(s) of Funding:	Outstanding RGC Projects
Start Date:	09/1998

Abstract:

To study and develop algorithms and techniques for mining association rules on high performance parallel systems including the following two system paradigms: share-nothing distributed memory parallel system and share-memory parallel system.

Project Title:	Semi-supervised Subspace Clustering for High-Dimensional Data
Investigator(s):	Cheung DWL, Ng KP
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2005

Abstract:

The objectives of this project are: 1.Design and analysis of semi-supervised subspace clustering algorithms in different models. 2.Performance studies of the algorithms in both synthetic and real data. 3.Explore the applications of these algorithms in different environments.

Project Title:	Service oriented e-transaction platform
Investigator(s):	Cheung DWL
Department:	Computer Science
Source(s) of Funding:	Innovation and Technology Fund Internship Programme
Start Date:	06/2006

Abstract:

To extend SOA to support processing of electronic transactions between enterprises; to develop Web Service components to support reliable and secure B2B applications based on open standards; and to develop service modeling methodology and software to facilitate design of electronic transaction services.

Project Title:	Service oriented e-transaction platform
Investigator(s):	Cheung DWL
Department:	Computer Science
Source(s) of Funding:	Innovation and Technology Fund Internship Programme
Start Date:	06/2006

Abstract:

Project Title:	Extending web 2.0 to deliver e-commerce services
Investigator(s):	Cheung DWL, Lee TYT
Department:	Computer Science
Source(s) of Funding:	Innovation and Technology Support Programme
Start Date:	09/2006

Abstract:

This proposal aims to extend various Web 2.0 technologies with electronic transaction capabilities and demonstrate the application of Web 2.0 for e-commerce. The objectives of this project are as follows: 1. Study the potential of implementing e-commerce services using Web 2.0 and the areas to extend Web 2.0 to support B2B and B2G requirements. 2. Extend existing Web 2.0 technologies, e.g. RSS (Really Simple Syndication) and AJAX (Asynchronous JavaScript And XML), with security and reliability mechanisms. 3. prototype a Web 2.0 e-commerce engine to demonstrate the use of Web 2.0 to conduct electronic transactions in proof-of-concept projects.

List of Research Outputs

Cheung D.W.L., Yee K.C. and Kwok R.P.M., B2B Exchange Technology Training, Thammasat University. Thailand, 2007.

Cheung D.W.L., Invited Talk, Security in Outsourcing of Data Mining, University of Illinois at Urbana Champaign. 2008.

Cheung D.W.L., Invited talk, Security and Integrity in Outsourcing of Data Mining, Croucher Advanced Study Institute, Mathematical & Algorithmic Challenges for Modeling & Analyzing Modern Data Sets. 2008.

Cheung D.W.L., Keynote, Information Interoperability, E-Government Interoperability Framework Forum, Thammasat University, Thailand. 2008.

Cheung D.W.L., Keynote: Security in Outsourcing of Data Mining , International Forum on Frontier of Data Management (FDM2007), Beijing, China . 2007.

Cheung D.W.L., Open Source Software License, ebXML Hermes H2O, Active Media Group, Italy. Italy, 2007.

Cheung D.W.L., Open Source Software License, ebXML Hermes, DBKK Health Insurance, Germany. Germany, 2007.

Cheung D.W.L., Security in Outsourcing of Data Mining, Queen's University, Canada. 2008.

Cheung D.W.L., Security in Outsourcing of Data Mining, Tsinghua University, China. 2007.

Cheung D.W.L., Security in Outsourcing of Data Mining, York University, Canada. 2008.

Cheung D.W.L. and Kwok R.P.M., Software License, Hermes 2.0, iASPEC. 2007.

Cheung D.W.L., Yee K.C. and Lee T.Y.T., Webformer: A Rapid Application Development Toolkit for Writing Ajax Web Form Applications, International Conference on Distributed Computing and Internet Technology (ICDCIT 2007). Springer Berlin / Heidelberg, 2007, 4882/2007: 248-253.

Cheung D.W.L. and Lee T.Y.T., XML Schema Design Methodology Training, Macau University of Science & Technology. Macau, 2007.

Lee S.D., Yee K.C., Cheung D.W.L. and Yuan W., Descriptive Schema: Semantics-based Query Answering, 3rd Semantic Wiki Workshop (SemWiki 2008). 2008.

Leung W.S., Lin M.C., Cheung D.W.L. and Yiu S.M., A Clustering-Based Approach for Filtering False Positive MicroRNA Candidates, 4-th International Symposium on Bioinformatics Research and Applications; May 6-9, 2008; Department of Computer Science, Georgia State University; Atlanta, Georgia (Lecture Notes in Bioinformatics (LNBI)). 2008.

Leung W.S., Yiu S.M., Cheung D.W.L., Lai L., Lin M.C. and Kung H.F., Computational Prediction on Mammalian and Viral MicroRNAs - a Review, International Journal of Integrative Biology. 2007, 1(2): 118-126.

Lo E., Kao C.M., Ho W.S., Lee S.D., Chui C.K. and Cheung D.W.L., OLAP on Sequence Data, ACM SIGMOD International Conference on Management of Data (SIGMOD 2008). 2008.

Mamoulis N., Yiu M.L., Cheng K.H. and Cheung D.W.L., Efficient Top-k Aggregation of Ranked Inputs, ACM Transactions on Database Systems . Association of Computing Machinery, 2007, 32(3).

Wong W.K., Cheung D.W.L., Hung E. and Liu H., Protecting Privacy in Incremental Maintenance for Distributed Association Rule Mining, The 12th Pacific-Asia Conference on Knowledge Discovery and Data Mining. 2008.

Wong W.K., Cheung D.W.L., Hung E., Kao C.M. and Mamoulis N., Security in Outsourcing of Association Rule Mining, The 33rd International Conference on Very Large Data Bases. 2007.

Zhang M., Kao C.M., Cheung D.W.L. and Yip K., Mining Periodic Patterns with Gap Requirement from Sequences, ACM Transaction on Knowledge Discovery from Data. Association of Computing Machinery, 2007, 1.

Zhang M., Kao C.M., Cheung D.W.L. and Yip C.L., Mining Sequence Patterns in Evolving Databases, In: Hsu, Lee, Temporal and Spatio-Temporal Data Mining. Idea Group Inc., 2007.

Researcher : Chin FYL

Project Title:	MultiVision Fund
Investigator(s):	Chin FYL
Department:	Computer Science
Source(s) of Funding:	MultiVision Intelligent Surveillance (Hong Kong) Ltd. - General Award
Start Date:	07/2003

Abstract:

MultiVision Fund.

Project Title:	Computationally Haplotyping Pedigree Data
Investigator(s):	Chin FYL, Smith DK, Song Y
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	01/2006

Abstract:

Minimum Recombination Haplotyping Problem (MRHP): finding a haplotype solution for a given pedigree that is consistent with given genotype data and derived from fewest recombinations (minimizing SUM). (1) The k-MRHP is an MRHP with the additional constraint that the number of recombinations on each haplotype is at most k where k = 0, 1, 2 (minimizing SUM with MAX=k) (2) An efficient algorithm for the k-MRHP when k=0 (3) Software implementation of the efficient algorithm

Project Title:	A new motif representation based on position specific patterns
Investigator(s):	Chin FYL
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2006

Abstract:

1 We want to introduce a good model to represent motifs and describe them in a precise and complete fashion. 2 Based on our new motif representation model, we will redefine the motif discovering problem and design efficient algorithms or heuristics to solve the problem. 3 The goal of the new model is to enable the discovery of a higher percentage of known motifs and some unknown motifs.

List of Research Outputs

Chan W.T., Chin F.Y.L., Ye D., Zhang G. and Zhang Y., On-line scheduling of parallel jobs on two machines, Journal of Discrete Algorithms . Amsterdam, The Netherlands, Elsevier Science Publishers B. V., 2008, 6(1): 3-10.

Chin F.Y.L., Zhang Y. and Zhu H., A 1-local 13/9-competitive Algorithm for Multicoloring Hexagonal Graphs, The 13th Annual International Computing and Combinatorics Conference (COCOON 2007). Banff, Alberta, Canada, 2007, 526-536.

Chin F.Y.L., A Clustering-Based Approach for Finding Motif Pairs from Protein Interaction Data (Keynote), 2008 International Conference on BioMedical Engineering and Informatics (BMEI 2008). Sanya, Hainan, China, 2008.

Chin F.Y.L., Ting H.F. and Zhang Y., A Constant-competitive Algorithm for Online OVSF Code Assignment, The 18th International Symposium on Algorithms and Computation (ISAAC 2007). Sendai, Japan, Springer Berlin / Heidelberg, 2007, 4835/2007: 452-463.

Chin F.Y.L., Chinese Journal of Advanced Software Research. 2008.

Chin F.Y.L., Chinese Journal of Advanced Software Research. 2007.

Chin F.Y.L., Current Bioinformatics. 2008.

Chin F.Y.L. and Leung C.M., DNA Motif Representation with Nucleotide Dependency, In: Dan Gusfield, IEEE/ACM Transactions on Computational Biology and Bioinformatics. USA, IEEE Computer Society, 2008, 5: 110-119.

Chin F.Y.L., Finding Motifs Computationally (Distinguished Lecture in Theoretical Computer Science) , Institute for Theoretical Computer Science, Tsinghua University. Beijing, China, 2007.

Chin F.Y.L., Finding Motifs Computationally, Computational Biology Seminar, Dept of Computer Science, University of Toronto. Toronto, Canada, 2007.

Chin F.Y.L., Finding Motifs Computationally, Department of Computer Science, University of Alberta. Alberta, Canada, 2007.

Chin F.Y.L., Finding Motifs Computationally, National Tsing-Hua Univeristy. Hsinchu, Taiwan, 2007.

Chin F.Y.L., International Journal of Computer Processing of Oriental Languages. 2007.

Chin F.Y.L., International Journal of Computer Processing of Oriental Languages. 2008.

Chin F.Y.L., Journal of Information Processing Letters. 2007.

Chin F.Y.L., Journal of Information Processing Letters. 2008.

Chin F.Y.L., Managing Editor, International Journal of Foundations of Computer Science. 2008.

Chin F.Y.L., Managing Editor, International Journal of Foundations of Computer Science. 2007.

Chin F.Y.L., Online Frequency Assignment Problem in Cellular Network Communication (Keynote), The 25th Workshop on Combinatorial Mathematics and Computation Theory. Taipei, Taiwan, 2008.

Chin F.Y.L., Online Frequency Assignment Problem in Cellular Network Communication, Dept. of Information Management of Shih Hsin University . 世新大學, Taipei, Taiwan, 2008.

Chin F.Y.L., Online Frequency Assignment in Wireless Communication Networks (Distinguished Lecture in Theoretical Computer Science), Institute for Theoretical Computer Science, Tsinghua University. Beijing, China, 2007.

Chin F.Y.L., Online Frequency Assignment in Wireless Communication Networks (Keynote), The 13th Annual International Computing and Combinatorics Conference (COCOON 2007) . Banff, Alberta, Canada, Springer Berlin / Heidelberg, 2007, 4598/2007: 2.

Chin F.Y.L., Online Frequency Assignment in Wireless Communication Networks, York University. Canada, 2008.

Chin F.Y.L., Leung C.M., Siu M.H. and Yiu S.M., Optimal Algorithm for Finding DNA Motifs with Nucleotide Adjacent Dependency, The Sixth Asia-Pacific Bioinformatics Conference (APBC 2008). Kyoto, Japan, 2008, 343-352.

Chin F.Y.L., Leung C.M. and Sung W.K., The Point Placement Problem on a Line - Improved Bounds for Pairwise Distance Queries, The 7th Workshop on Algorithms in Bioinformatics (WABI 2007). Philadelphia, Pennsylvania, USA, Springer, 2007, LNCS 4645: 372-382.

He X., Yung N.H.C., Chow K.P., Chin F.Y.L., Chung H.Y., Wong K.K.Y. and Tsang K.S.H., Watershed Segmentation with Boundary Curvature Ratio Based Merging Criterion, 9th IASTED International Conference on Signal and Image Processing. Honolulu, Hawaii, USA, 2007, 7-12.

Leung C.M., Siu M.H., Yiu S.M., Chin F.Y.L. and Sung K.W.K., Finding Linear Motif Pair from Protein Interaction Networks: A Probabilistic Approach, The 6th Annual International Conference on Computational Systems Bioinformatics Conference (CSB 2007). San Diego, California, USA, 2007, 111-120.

Yuk S.C., Wong K.K.Y., Chung H.Y., Chow K.P., Chin F.Y.L. and Tsang K.S.H., Object-Based Surveillance Video Retrieval System With Real-Time Indexing Methodology, International Conference on Image Analysis and Recognition. Montreal, Canada, 2007, 626-637.

Researcher : Choi YK

List of Research Outputs

Choi Y.K., Li X.Q., Rong F.G., Wang W.P. and Cameron S., Determining directional contact range of two convex polyhedra,, Proceedings of Geometric Modeling and Processing 2008, Hangzhou, China. 2008.

Lu L., Choi Y.K., Wang W.P. and Kim M.S., Variational 3D shape segmentation for bounding volume computation, Computer Graphics Forum, (Eurographics 2007). 2007, vol. 26, no. 3.

Researcher : Chong CF

List of Research Outputs

Chow K.P., Cheng K.Y., Man L.Y., Lai K.Y., Hui C.K., Chong C.F., Pun K.H., Tsang W.W., Chan H.W. and Yiu S.M., BTM—An Automated Rule-Based BT Monitoring System for Piracy Detection, The Second International Conference on Internet Monitoring and Protection, ICIMP 2007. Silicon Valley, USA, IEEE Computer Society Press, 6 pages.

Law Y.W., Lai K.Y., Jiang L., Ieong S.C.R., Kwan Y.K., Chow K.P., Hui C.K., Yiu S.M. and Chong C.F., Protecting Digital Legal Professional Privilege (LPP) Data, The third International Workshop on Systematic Approaches to Digital Forensic Engineering. Los Alamitos, IEEE Computer Society, 2008, 1: 11.

Li Z., Chong C.F., Hui C.K., Yiu S.M., Chow K.P., Tsang W.W., Chan H.W. and Pun K.H., An Attack on Libert et al.’s ID-Based Undeniable Signature Scheme, International Journal of Network Security. Seoul, Korea, 2007, Vol. 5, No. 2: 220-223.

Researcher : Chow KP

Project Title:	Advanced semantic video analysis for content-based video retrieval
Investigator(s):	Chow KP, Chin FYL, Wong KKY
Department:	Computer Science
Source(s) of Funding:	Innovation and Technology Support Programme
Start Date:	09/2006

Abstract:

The objective of this proposal is to develop new and enabling semanitc video analysis techniques for video retrieval applications. We believe these new techniques can help to remedy the video retrieval problems found in video surveillance systems and the video search engine.

List of Research Outputs

Chow K.P., Cheng K.Y., Man L.Y., Lai K.Y., Hui C.K., Chong C.F., Pun K.H., Tsang W.W., Chan H.W. and Yiu S.M., BTM—An Automated Rule-Based BT Monitoring System for Piracy Detection, The Second International Conference on Internet Monitoring and Protection, ICIMP 2007. Silicon Valley, USA, IEEE Computer Society Press, 6 pages.

He X., Yung N.H.C., Chow K.P., Chin F.Y.L., Chung H.Y., Wong K.K.Y. and Tsang K.S.H., Watershed Segmentation with Boundary Curvature Ratio Based Merging Criterion, 9th IASTED International Conference on Signal and Image Processing. Honolulu, Hawaii, USA, 2007, 7-12.

Jiang L., Hui C.K., Chow K.P., Yiu S.M. and Lai K.Y., Improving Disk Sector Integrity Using 3-dimension Hashing Scheme, The 2007 International Workshop on Forensics for Future Generation Communication Environments. IEEE Computer Society, 2007, 2: 5.

Kwan Y.K., Chow K.P., Law Y.W. and Lai K.Y., Reasoning About Evidence using Bayesian Networks, In: Indrajit Ray, Sujeet Shenoi, Fourth Annual IFIP WG 11.9 International Conference on Digital Forensics. New York, Springer, 2008, 1: 15.

Law Y.W., Chow K.P., Kwan Y.K. and Lai K.Y., Consistency Issue on Live Systems Forensics, The 2007 International Workshop on Forensics for Future Generation Communication Environments. IEEE Computer Society, 2007, 2: 5.

Law Y.W., Lai K.Y., Jiang L., Ieong S.C.R., Kwan Y.K., Chow K.P., Hui C.K., Yiu S.M. and Chong C.F., Protecting Digital Legal Professional Privilege (LPP) Data, The third International Workshop on Systematic Approaches to Digital Forensic Engineering. Los Alamitos, IEEE Computer Society, 2008, 1: 11.

Li Z., Chong C.F., Hui C.K., Yiu S.M., Chow K.P., Tsang W.W., Chan H.W. and Pun K.H., An Attack on Libert et al.’s ID-Based Undeniable Signature Scheme, International Journal of Network Security. Seoul, Korea, 2007, Vol. 5, No. 2: 220-223.

Yuk S.C., Wong K.K.Y., Chung H.Y., Chow K.P., Chin F.Y.L. and Tsang K.S.H., Object-Based Surveillance Video Retrieval System With Real-Time Indexing Methodology, International Conference on Image Analysis and Recognition. Montreal, Canada, 2007, 626-637.

Researcher : Chui CK

List of Research Outputs

Chui C.K. and Kao C.M., A Decremental Approach for Mining Frequent Itemsets from Uncertain Data, The 12th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2008). 2008.

Chui C.K., Mining Frequent Intemsets and Order Preserving Sub-matrix from Uncertain Data. 2007.

Lo E., Kao C.M., Ho W.S., Lee S.D., Chui C.K. and Cheung D.W.L., OLAP on Sequence Data, ACM SIGMOD International Conference on Management of Data (SIGMOD 2008). 2008.

Researcher : Chung HY

List of Research Outputs

He X., Yung N.H.C., Chow K.P., Chin F.Y.L., Chung H.Y., Wong K.K.Y. and Tsang K.S.H., Watershed Segmentation with Boundary Curvature Ratio Based Merging Criterion, 9th IASTED International Conference on Signal and Image Processing. Honolulu, Hawaii, USA, 2007, 7-12.

Yuk S.C., Wong K.K.Y., Chung H.Y., Chow K.P., Chin F.Y.L. and Tsang K.S.H., Object-Based Surveillance Video Retrieval System With Real-Time Indexing Methodology, International Conference on Image Analysis and Recognition. Montreal, Canada, 2007, 626-637.

Researcher : Feng X

Project Title:	A New Approach for Intelligent Processing Based on Generalized Particle Model
Investigator(s):	Feng X, Lau FCM
Department:	Computer Science
Source(s) of Funding:	Small Project Funding
Start Date:	03/2007

Abstract:

Many real-world problems can be solved using artificial intelligence (AI) techniques. The goal of this project is to investigate and develop an intelligent processing approach based on the generalized particle model (GPM). In GPM, entities are modeled as particles in one or more force-fields. We will study the evolution of “swarms”, the particles’ microcosmic actions, and macroscopic swarm intelligence, and present efficient algorithms for applying GPM to communication networks and multi-agent systems (MASs). GPM is an important extension of Elastic Net (EN), but it is fundamentally different from many other popular intelligent approaches including those based on symbolic or fuzzy logic, genetic algorithms, artificial neural network, game theory and ant colony optimization. The features of the GPM-based models and their corresponding algorithms include a powerful processing ability to deal with priorities, personality, autonomy and interaction of different entities in networks or MASs. Furthermore, these models can be applied to the optimization of multiple objectives, including aggregate utility, personal utility, minimal personal utility, etc. The proposed approach also has the advantages of the high parallelism, low computational complexity, and ease for hardware implementation. The major objectives in this project are as follows: 1. To present a new generalized particle model (GPM), which is different in many respects from cellular automaton, generalized cellular automaton, neural network, cellular neural network, particle model in physics, ant colony optimization, reaction and growth model, genetic algorithm, etc. 2. Based on GPM, to propose a new distributed parallel swarm intelligent model and theory, and to explore the essence and rules of swarm intelligence in terms of growth, evolution, phase transformation, etc. Based on the proposed model and theory, to deal with and explain a variety of complicated phenomena that might occur in dynamic environments which are difficult for traditional models and approaches. 3. To extend and develop the spring net approach originally proposed by applicant to a generic parallel and distributed method based on various generalized particle models (of different granularities) for swarm intelligence. 4. To present some parallel and distributed intelligent approaches and algorithms based on GPM. By simulations and experiments, to test that these approaches on their ability to adapt to the real-time dynamic environment that involves various interactions, metabolism, phase transformation, etc. To show that the new approaches can overcome some deficiencies of traditional approaches.

List of Research Outputs

Feng X. and Lau F.C.M., A Parallel Evolutionary Approach to Multi-objective Optimization, The IEEE Congress on Evolutionary Computation (CEC 2007). Singapore, 2007.

Feng X., Lau F.C.M. and Shuai D.X., The Coordination Generalized Particle Model--An Evolutionary Approach to Multi-sensor Fusion , Information Fusion. Elsevier, 2008, 9: 450-464.

Researcher : He T

List of Research Outputs

Huo Q. and He T., A Minimax Classification Approach to HMM-Based Online Handwritten Chinese Character Recognition Robust Against Affine Distortions, ICDAR-2007. 1: IEEE.

Researcher : He X

List of Research Outputs

He X. and Yung N.H.C., A corner detector based on global and local curvature properties, Optical Engineering - a journal of SPIE. USA, SPIE, 2008, 47 (5): 12.

He X., Yung N.H.C., Chow K.P., Chin F.Y.L., Chung H.Y., Wong K.K.Y. and Tsang K.S.H., Watershed Segmentation with Boundary Curvature Ratio Based Merging Criterion, 9th IASTED International Conference on Signal and Image Processing. Honolulu, Hawaii, USA, 2007, 7-12.

Researcher : Ho CY

List of Research Outputs

Ho C.Y., Group-based Checkpoint/Rollback Recovery for Large Scale Message-passing Systems . Hong Kong, 2008.

Ho C.Y., Wang C.L. and Lau F.C.M., Scalable Group-based Checkpoint/restart For Large-scale Message-passing Systems, Proceedings Of The 2008 Ieee International Parallel & Distributed Processing Symposium (ipdps 2008). IEEE, 2008.

Researcher : Ho JCF

List of Research Outputs

Chan W.K., Ho J.C.F., Tse T.H. and Yu Y.T., Piping classification to metamorphic testing: an empirical study towards better effectiveness for the identification of failures in mesh simplification programs, Proceedings of the 31st Annual International Computer Software and Applications Conference (COMPSAC 2007), IEEE Computer Society Press, Los Alamitos, CA (acceptance rate: 18%). Los Alamitos, California, IEEE Computer Society Press, 2007, 397−404.

Researcher : Ho SC

List of Research Outputs

Ho S.C., Wang C.L. and Lau F.C.M., Lightweight Process Migration and Memory Prefetching in openMosix, Proceedings of 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2008). Miami, USA, IEEE, 2008.

Ho S.C., Process Roaming. 2007.

Researcher : Ho SC

List of Research Outputs

Ho S.C., Process Roaming. 2007.

Researcher : Ho WS

List of Research Outputs

Lo E., Kao C.M., Ho W.S., Lee S.D., Chui C.K. and Cheung D.W.L., OLAP on Sequence Data, ACM SIGMOD International Conference on Management of Data (SIGMOD 2008). 2008.

Researcher : Hu H

List of Research Outputs

Hu H. and Wang C.L., GPS-Based Location Extraction and Presence Management for Mobile Instant Messenger, 2007 IFIP International Conference on Embedded and Ubiquitous Computing (EUC'2007), December 17-20, 2007, Taipei Taiwan.. Berlin, Springer, 2007, 309-320.

Researcher : Hu P

List of Research Outputs

Hu P., Automated Fault Localization: a Statistical Predicate Analysis Approach, 2007.

Researcher : Hui CK

Project Title:	Study of multi-signer signature scheme and identity authentication
Investigator(s):	Hui CK, Chow KP, Tsang WW
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	12/2003

Abstract:

to investigate the security of multi-signer signature schemes, and to design some new schemes with secure and high efficient features.

Project Title:	Forward secure crytographic schemes for Ad Hoc Network
Investigator(s):	Hui CK, Chow KP, Yiu SM, Li VOK
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	01/2005

Abstract:

To carry out: (1) a forward secure signature scheme to be used in the clients of an ad hoc network. (2) a forward secure threshold signature scheme to be used in the CAs of an ad hoc network.

Project Title:	Design of cryptographic schemes for delegation network
Investigator(s):	Hui CK, Yiu SM
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	01/2007

Abstract:

(1) Delegation is a process where a user (the delegator) grants some of his rights (power), e.g. the signing right, to another user (the delegate), to work on his/her behalf.In a paper-based environment, delegation can be easily achieved. However, in a digital environment, how delegation can be handled properly becomes an issue to be addressed. The key management is also complicated, especially in a general delegation network.In this project, we propose to design a number of efficient and provably secure cryptographic schemes to support different variations of delegation networks. The developed schemes would help to enhance the security of an enterprise information system as delegation would be a common operation in most of the office environment. Also, the knowledge gained will be useful to build up a security model about delegation network. (2) In a paper-based environment, delegation can be easily achieved. However, in a digital environment, how delegation can be handled properly becomes an issue to be addressed. For examples, it is not trivial how a delegate can digitally sign or decrypt a document on behalf of the delegator and also how the receiver of the document verifies the signature and be convinced that the signer has the right (power) from the delegator to sign the document. Obviously, some straight-forward approaches do not work. Using signing as an example, the delegator passes the signing key (e.g. the private key if using an asymmetric cryptographic system) to the delegate, then the delegator has to change the key frequently and it also violates the non-repudiation property of the scheme as it is difficult to prove whether the delegator or the delegate is the person who actually signed the document. The key management is also complicated, especially in a general delegation network. (3)In other words, from the perspective of computer security, a set of specially designed cryptographic primitives that support delegation network is necessary. To tackle this problem, [MU96] proposed the proxy signature to deal with the delegation of signing. In a proxy signature, the original signer creates a key pair (the proxy key pair, denoted as (, K)) using his own signing key. The delegate (called the proxy signer) signs a document using . The verifier has to use K as well as the public key of the original signer to check the validity of the signature. Since the public key of the original signer is involved in the checking, so the delegation relationship is confirmed. After this work, a number of proxy signature schemes were proposed. However, most of these schemes are either too restrictive and cannot be extended easily for delegation networks, or are shown to be insecure.(4) In this project, we propose to design a number of efficient and provably secure cryptographic schemes to support different variations of delegation networks. The developed schemes would help to enhance the security of an enterprise information system as delegation would be a common operation in most of the office environment.

List of Research Outputs

Chow K.P., Cheng K.Y., Man L.Y., Lai K.Y., Hui C.K., Chong C.F., Pun K.H., Tsang W.W., Chan H.W. and Yiu S.M., BTM—An Automated Rule-Based BT Monitoring System for Piracy Detection, The Second International Conference on Internet Monitoring and Protection, ICIMP 2007. Silicon Valley, USA, IEEE Computer Society Press, 6 pages.

Dong Y., Sui A.F., Yiu S.M., Li V.O.K. and Hui C.K., Providing distributed certificate authority service in cluster-based mobile and hoc networks, Computer Communications. 2007, 30: 2442-2452.

Jiang L., Hui C.K., Chow K.P., Yiu S.M. and Lai K.Y., Improving Disk Sector Integrity Using 3-dimension Hashing Scheme, The 2007 International Workshop on Forensics for Future Generation Communication Environments. IEEE Computer Society, 2007, 2: 5.

Jiang L., Hui C.K. and Yiu S.M., Improving Disk Sector Integrity Using k-dimension Hashing, IFIP International Federation for Information Processing. Japan, Springer Boston, 2008, 285: 87-98.

Law Y.W., Lai K.Y., Jiang L., Ieong S.C.R., Kwan Y.K., Chow K.P., Hui C.K., Yiu S.M. and Chong C.F., Protecting Digital Legal Professional Privilege (LPP) Data, The third International Workshop on Systematic Approaches to Digital Forensic Engineering. Los Alamitos, IEEE Computer Society, 2008, 1: 11.

Li Z., Chong C.F., Hui C.K., Yiu S.M., Chow K.P., Tsang W.W., Chan H.W. and Pun K.H., An Attack on Libert et al.’s ID-Based Undeniable Signature Scheme, International Journal of Network Security. Seoul, Korea, 2007, Vol. 5, No. 2: 220-223.

Researcher : Hung RYS

List of Research Outputs

Hung R.Y.S. and Ting H.F., Competitive analysis of most-request-first for scheduling broadcasts with start-up delay, In: G. Ausiello, and D. Sannella , Theoretical Computer Science. Amsterdam, The Netherlands., ELSEVIER, 2008, 361(1-3): 200--211.

Hung R.Y.S., Lai K.F. and Ting H.F., Finding Frequent Items in a Turnstile Data Stream, In: Xiaodong Hu, and Jie Wang, Proceedings of the 14th Annual International Symposium on Theoretical Informatics. Springer, 2008, 498--509.

Hung R.Y.S. and Ting H.F., Finding Heavy Hitters Over The Sliding Window Of A Weighted Data Stream, In: Eduardo Laber, Proceedings of the 8th Latin America Symposium on Theoretical Informatics. New York, Springer, 2008, 699--710.

Researcher : Huo Q

Project Title:	Towards on-line recognition of continuous Chinese handwriting text on tablet PCs
Investigator(s):	Huo Q
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2003

Abstract:

To construct a large scale corpus of Chinese handwriting samples naturally written on Tablet PCs; to investigate new techniques for feature extraction, character modeling, contextual processing and integrated search to cope with the on-line recognition problem of continuously handwritten Chinese sentences; to implement a prototype system on the Tablet PC using the most promising solution identified by investigating the effectiveness of integrating the available techniques in different ways.

Project Title:	Chinese spoken language processing
Investigator(s):	Huo Q
Department:	Computer Science
Source(s) of Funding:	Anhui USTC iFLYTEK Co. Ltd. - General Award
Start Date:	09/2005

Abstract:

To research and develop the state-of-the-art Chinese spoken language processing technology.

Project Title:	A Detection and Verification Based Approach for On-line Recognition of Handwritten Chinese Words
Investigator(s):	Huo Q
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2005

Abstract:

The objectives of this project are: (1) to investigate a new "detection and verification based approach" for on-line recognition of handwritten Chinese words; (2) to investigate new techniques for feature extraction and character modeling to improve the character classification accuracy as well as the reliability of character verification; (3) to develop a prototype system on Tablet PC, as a test-bed of new ideas, by using the most promising solution identified through the study in this project. The character vocabulary of our recognizer will include 6763 simplified Chinese characters in GB2312-80 standard, 12 frequently used GBK Chinese characters, 62 alphanumeric characters, 140 punctuation marks and symbols. We are aiming at a writer-independent character recognition accuracy of above 90% for naturally written Chinese words derived from our handwriting corpus.

Project Title:	A Study of Similarity Measures For Hidden Markov Models and Their Applications in Speech Recognition
Investigator(s):	Huo Q
Department:	Computer Science
Source(s) of Funding:	Seed Funding Programme for Basic Research
Start Date:	03/2006

Abstract:

After many years research, Gaussian mixture continuous density hidden Markov model (CDHMM) remains predominant as a speech modeling technique in automatic speech recognition (ASR) area. How to measure the similarity of two given CDHMMs has been an important research topic for several decades. In a pioneering work, Juang and Rabiner proposed to use Kullback-Leibler (KL) divergence as a similarity measure of two HMMs with discrete observation distributions. In order to calculate the KL divergence, a Monte Carlo simulation procedure has to be used. It is not practical to use such a procedure in ASR applications that require a quick response. So, the main objectives of this project are as follows: - To develop efficient approximation methods for calculating the KL divergence of two given CDHMMs; - To study the possibility of using approximate KL divergence for the prediction of word confusabilities in a given vocabulary of an ASR system; - To develop effective and intelligent speaker adaptation strategies guided by an automatic analysis of vocabulary word confusability.

List of Research Outputs

Huo Q. and He T., A Minimax Classification Approach to HMM-Based Online Handwritten Chinese Character Recognition Robust Against Affine Distortions, ICDAR-2007. 1: IEEE.

Researcher : Ieong SCR

List of Research Outputs

Law Y.W., Lai K.Y., Jiang L., Ieong S.C.R., Kwan Y.K., Chow K.P., Hui C.K., Yiu S.M. and Chong C.F., Protecting Digital Legal Professional Privilege (LPP) Data, The third International Workshop on Systematic Approaches to Digital Forensic Engineering. Los Alamitos, IEEE Computer Society, 2008, 1: 11.

Researcher : Jiang L

List of Research Outputs

Jiang L., Hui C.K., Chow K.P., Yiu S.M. and Lai K.Y., Improving Disk Sector Integrity Using 3-dimension Hashing Scheme, The 2007 International Workshop on Forensics for Future Generation Communication Environments. IEEE Computer Society, 2007, 2: 5.

Jiang L., Hui C.K. and Yiu S.M., Improving Disk Sector Integrity Using k-dimension Hashing, IFIP International Federation for Information Processing. Japan, Springer Boston, 2008, 285: 87-98.

Law Y.W., Lai K.Y., Jiang L., Ieong S.C.R., Kwan Y.K., Chow K.P., Hui C.K., Yiu S.M. and Chong C.F., Protecting Digital Legal Professional Privilege (LPP) Data, The third International Workshop on Systematic Approaches to Digital Forensic Engineering. Los Alamitos, IEEE Computer Society, 2008, 1: 11.

Researcher : Kao CM

Project Title:	Association rule mining on continuous stream data
Investigator(s):	Kao CM, Cheung DWL
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2004

Abstract:

To derive efficient online time-based sampling algorithms; to derive efficient approximation algorithms for mining association rules from a single data stream; to derive efficiency algorithms for mining inter-stream associations; to perform time-delayed association analysis.

Project Title:	Computational issues in mining uncertain data
Investigator(s):	Kao CM, Cheung DWL
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2006

Abstract:

1 Data Uncertainty Models. One of the key steps in knowledge discovery is data collection. In practice, statistical approximation is used in the data collection process. This may be due to measurement error or data values that are based on subjective judgement. Our first objective is to investigate the various forms of uncertainty that may exist in data, and how these various forms of uncertainty affect the design of data-mining algorithms under different mining models (such as association-rule mining, clustering, and classification). For starters, we consider "value uncertainty" and "existential uncertainty." A database system models the physical world by recording facts (attribute values) of real-life entities (data items or tuples). By value uncertainty, we refer to data that contains a known set of tuples but their attribute values are uncertain. For example, a moving-object database tracks the location of a set of known moving objects. Due to the time lag between the current time and the time an object's location was last recorded, the current location of an object (an attribute value) can only be approximated by a statistical model. Example models include "uniform line uncertainty" (consider the moving object being a car moving on a straight road) and "Gaussian circular uncertainty" (consider the moving object performs a random walk starting from its last recorded location). By existential uncertainty, we refer to data whose tuple membership is uncertain or fuzzy. For example, a patient with a body temperature of 100F may be assessed as having a fever with a confidence of 70%. Here, the physical entity (patient) exists, but its attribute value (fever) is associated with an estimated probability. 2 Mining Association Rules from Uncertain Data. Traditional algorithms for mining association rules apply to market basket type of data. A market basket dataset consists of a number of "transactions" each being a set of "items." For example, a transaction may read "milk, bread, egg" specifying what a particular customer has purchased. Association rule mining aims at finding rules of the form X => Y, where X and Y are non-overlapping non-empty itemsets. The semantics of the rule is that if all the items in X occur in a transaction, then it is very likely that items in Y also occur in the same transaction. In many applications, however, the occurrence of an item/event in a transaction/tuple may not be certain. As we will elaborate further in Section 2, Part II, a transcriptomic microarray dataset, for example, might register probabilistic values. Here, an experiment derives a tuple of the dataset and an entry in the tuple corresponds to whether a particular gene is "over-expressed" in that experiment. As we will explain later, "over-expression" is best associated with a probability to lighten the effect of measurement error. Hence, the dataset can be considered as one whose tuples contain items that are associated with existential probabilities. Our objective here is to re-visit the definition of association rules in the presence of items' existential probabilities. Also, our preliminary study shows that traditional algorithms like Apriori are not efficient when applied to this kind of uncertain datasets. New algorithms that handle data uncertainty efficiently need to be designed. 3 Uncertain Data Clustering. Given a set of data objects, clusterization is about grouping the objects into clusters such that objects belonging to the same cluster are "close" to each other while objects belonging to different clusters are "far" from each other, with respect to some distance metric defined for "closeness." As an example, if landmarks/buildings etc. are considered objects, then clusterization would group them according to their physical proximity. Traditional clustering algorithms assume that data is certain, in terms of both objects' existence and their feature values (e.g., a landmark's co-ordinates). Our third objective is to investigate how clustering should be done if data uncertainty exists. For example, with "value uncertainty", the objects are no longer considered as "points" in the feature space. Instead, they are described by probability density functions according to the uncertainty model assumed. The implication is that traditional distance metrics, such as Euclidean distance, are no longer applicable. Traditional clustering algorithms assign an object to a cluster based on the "distance" the object is from the cluster (using the cluster's centroid as a reference point, for example). With value uncertainty, other more complicated distance metrics, such as "expected Euclidean distance" has to be used. In these cases, the computation of "distance" becomes very computationally expensive, which often requires numerical integration methods. We will derive algorithms that are designed to reduce such expensive computation. 4 Building Classifiers from Uncertain Data. Classification is another very important data-mining model. A number of methods for building classifiers have been proposed in the past, including decision tree classifiers, neural networks, Bayesian classifiers, and emerging-pattern-based classifiers. Our fourth objective is to study how data uncertainty affects the construction of those classifiers. In classification, a set of training data is used to construct a classifier. A training tuple typically consists of some attribute values together with a class label. Building a classifier requires plowing through the training set and figuring out which attribute value combination lead to a strong implication of a particular class label. Again, traditional algorithms assume certain data. We consider both value uncertainty (i.e., attribute values are represented by pdf's) and label uncertainty (i.e., the class label of a training data tuple is associated with a probability. 5 Applying Uncertain Data Mining Algorithms to Real-Life Applications. Our final objective is to evaluate the effectiveness of our mining algorithms when applied to real-life applications. There are two goals: (1) to study whether the quality of the mined results (be they association rules, clusters, or classifiers) are better when data uncertainty is taken into account in the mining process; (2) to study the efficiency of such mining algorithms.

List of Research Outputs

Chau M.C.L., Cheng R. and Kao C.M., Uncertain Data Mining: An Example in Self-Organizing Maps, The 1st Workshop on Data Mining of Uncertain Data (DUNE 2007). 2007.

Chui C.K. and Kao C.M., A Decremental Approach for Mining Frequent Itemsets from Uncertain Data, The 12th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2008). 2008.

Lee S.D., Kao C.M. and Cheng R., Reducing UK-means to K-means, The 1st Workshop on Data Mining of Uncertain Data (DUNE 2007) . 2007.

Lo E., Kao C.M., Ho W.S., Lee S.D., Chui C.K. and Cheung D.W.L., OLAP on Sequence Data, ACM SIGMOD International Conference on Management of Data (SIGMOD 2008). 2008.

Wong W.K., Cheung D.W.L., Hung E., Kao C.M. and Mamoulis N., Security in Outsourcing of Association Rule Mining, The 33rd International Conference on Very Large Data Bases. 2007.

Zhang M., Kao C.M., Cheung D.W.L. and Yip K., Mining Periodic Patterns with Gap Requirement from Sequences, ACM Transaction on Knowledge Discovery from Data. Association of Computing Machinery, 2007, 1.

Zhang M., Kao C.M., Cheung D.W.L. and Yip C.L., Mining Sequence Patterns in Evolving Databases, In: Hsu, Lee, Temporal and Spatio-Temporal Data Mining. Idea Group Inc., 2007.

Researcher : Karras P

List of Research Outputs

Karras P., Data Structures and Algorithms for Data Representation in Constrained Environments, 2007.

Researcher : Kwan KL

List of Research Outputs

Kwan K.L., Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance, 2007.

Researcher : Kwan YK

List of Research Outputs

Kwan Y.K., Chow K.P., Law Y.W. and Lai K.Y., Reasoning About Evidence using Bayesian Networks, In: Indrajit Ray, Sujeet Shenoi, Fourth Annual IFIP WG 11.9 International Conference on Digital Forensics. New York, Springer, 2008, 1: 15.

Law Y.W., Chow K.P., Kwan Y.K. and Lai K.Y., Consistency Issue on Live Systems Forensics, The 2007 International Workshop on Forensics for Future Generation Communication Environments. IEEE Computer Society, 2007, 2: 5.

Law Y.W., Lai K.Y., Jiang L., Ieong S.C.R., Kwan Y.K., Chow K.P., Hui C.K., Yiu S.M. and Chong C.F., Protecting Digital Legal Professional Privilege (LPP) Data, The third International Workshop on Systematic Approaches to Digital Forensic Engineering. Los Alamitos, IEEE Computer Society, 2008, 1: 11.

Researcher : Kwok RPM

List of Research Outputs

Cheung D.W.L., Yee K.C. and Kwok R.P.M., B2B Exchange Technology Training, Thammasat University. Thailand, 2007.

Cheung D.W.L. and Kwok R.P.M., Software License, Hermes 2.0, iASPEC. 2007.

Researcher : Lai KY

List of Research Outputs

Chow K.P., Cheng K.Y., Man L.Y., Lai K.Y., Hui C.K., Chong C.F., Pun K.H., Tsang W.W., Chan H.W. and Yiu S.M., BTM—An Automated Rule-Based BT Monitoring System for Piracy Detection, The Second International Conference on Internet Monitoring and Protection, ICIMP 2007. Silicon Valley, USA, IEEE Computer Society Press, 6 pages.

Jiang L., Hui C.K., Chow K.P., Yiu S.M. and Lai K.Y., Improving Disk Sector Integrity Using 3-dimension Hashing Scheme, The 2007 International Workshop on Forensics for Future Generation Communication Environments. IEEE Computer Society, 2007, 2: 5.

Kwan Y.K., Chow K.P., Law Y.W. and Lai K.Y., Reasoning About Evidence using Bayesian Networks, In: Indrajit Ray, Sujeet Shenoi, Fourth Annual IFIP WG 11.9 International Conference on Digital Forensics. New York, Springer, 2008, 1: 15.

Law Y.W., Chow K.P., Kwan Y.K. and Lai K.Y., Consistency Issue on Live Systems Forensics, The 2007 International Workshop on Forensics for Future Generation Communication Environments. IEEE Computer Society, 2007, 2: 5.

Law Y.W., Lai K.Y., Jiang L., Ieong S.C.R., Kwan Y.K., Chow K.P., Hui C.K., Yiu S.M. and Chong C.F., Protecting Digital Legal Professional Privilege (LPP) Data, The third International Workshop on Systematic Approaches to Digital Forensic Engineering. Los Alamitos, IEEE Computer Society, 2008, 1: 11.

Researcher : Lam TW

Project Title:	Algorithms for uncovering conserved genes on whole genomes
Investigator(s):	Lam TW
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2004

Abstract:

To investigate the complexity of a maximum common subsequence problem that models mutations between genomes; to design and implement better algorithms and software for uncovering conserved genes.

Project Title:	Compressed indexes for approximate string matching, with applications to biological sequences
Investigator(s):	Lam TW
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	08/2006

Abstract:

1 The objectives of my proposal contains special fonts, and they are included into the section of backgrounds of research as a combined pdf file.

List of Research Outputs

Chan H.L., Lam T.W. and Liu K.S., Extra Unit-Speed Machines Are Almost as Powerful as Speedy Machines for Flow Time Scheduling, SIAM Journal on Computing. USA, SIAM, 2008, 37:5: 1595-1612.

Chan H.L., Lam T.W., Sung W.K., Wong P.W.H. and Yiu S.M., Non-overlapping Common Substrings Allowing Mutations , Mathematics in Computer Science. Springer, 2008, 543-555.

Hon W.K., Lam T.W., Shah R., Tam S.L. and Vitter J., Cache-Oblivious Index for Approximate String Matching, The 18th Annual Symposium on Combinatorial Pattern Matching (CPM). 2007.

Hon W.K., Lam T.W., Shah R.A.H.U.L., Tam S.L. and Vitter J.S., Compressed Index for Dictionary Matching, IEEE Data Compression Conference. IEEE Computer Society, 2008, 23-32.

Lam T.W., Sung W.K., Tam S.L., Wong C.K. and Yiu S.M., An Experimental Study of Compressed Indexing and Local Alignments of DNA, First International Conference on Combinatorial Optimization and Applications. Springer, 2007, 242-254.

Lam T.W., Lee L.K., Wong P.W.H. and To I.K.K., Competitive Non-migratory Scheduling For Flow Time And Energy, The 20th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). ACM, 2008, 256-264.

Lam T.W., Sung W.K., Tam S.L., Wong C.K. and Yiu S.M., Compressed indexing and local alignment of DNA, Bioinformatics. Oxford University Press, 2008, 24 (6): 791-797.

Lam T.W., Lee L.K., To I.K.K. and Wong P.W.H., Energy Efficient Deadline Scheduling in Two Processor Systems, The 18th International Symposium on Algorithms and Computation. Springer, 2007, 476-487.

Lam T.W., Energy Efficient online scheduling, Foundations of Computational Mathematics. 2008.

Lam T.W., Energy efficient online scheduling, New Challenges on Scheduling Theory. 2008.

Lam T.W., Sung W.K., Tam S.L. and Yiu S.M., Space Efficient Indexes for String Matching with Don't Cares, The 18th International Symposium on Algorithms and Computation . Springer, 2007, 846-857.

Wong K.F., Chiu Y.S., Lam T.W. and Yiu S.M., A Memory Efficient Algorithm for Structural Alignment of RNAs with Embedded Simple Pseudoknots, The 5th Asia-Pacific Bioinformatics Conference . World Scientific, 2008, 89-100.

Researcher : Lau FCM

Project Title:	The Hong Kong University grid point
Investigator(s):	Lau FCM
Department:	Computer Science
Source(s) of Funding:	Matching Fund for Hi-Tech Research and Development Program of China (863 Projects)
Start Date:	12/2002

Abstract:

To study grid point of The University of Hong Kong.

Project Title:	Content adaptation for mobile computing
Investigator(s):	Lau FCM
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2003

Abstract:

To design and implement a content adaptation system with context-awareness and which is sensitive to user's preferences; to design and implement an automatic content augmentation tool for content creation.

Project Title:	A holistic approach to structured web document viewing in small devices
Investigator(s):	Lau FCM
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2004

Abstract:

To produce a system design covering the content creation, content adaptation, and content rendering aspects of Web content viewing on a mobile handheld device, whereby any viewing activity will be seen as complete, fast, and easy.

Project Title:	HP mobile technology for teaching initiative
Investigator(s):	Lau FCM
Department:	Computer Science
Source(s) of Funding:	Hewlett-Packard HK SAR Ltd.
Start Date:	10/2004

Abstract:

To develop HP mobile technology for teaching initiative.

Project Title:	Intelligent Systems for Painting and Calligraphy
Investigator(s):	Lau FCM
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2005

Abstract:

The objectives of this proposed project are: (1)To apply point-based techniques to achieve fast rendering of the brush geometry, and to consider image-based rendering algorithms for high quality rendering of the animated brush. (2) To incorporate the smooth particles hydrodynamics method borrowed from astrophysics in the dynamics simulation of the brush. (3) To apply particle diffusion (from chemistry/physics) to simulate the complex pigment behavior. (4) To devise an intelligent system component for training the brush to adapt to “personal habitual bias” of the user. (5) To extend the present calligraphy generation system with a feedback reinforcement learning component to strengthen the constraint satisfaction process. (6) To explore possible new recognition algorithms for calligraphic writings of which the characters are severely distorted.

Project Title:	UGC-Matching Grant Scheme (2nd Phase)-Process Migration and Runtime Scheduling for Parallel Tasks in Computational Grids
Investigator(s):	Lau FCM
Department:	Computer Science
Source(s) of Funding:	Other Funding Scheme
Start Date:	05/2006

Abstract:

To study process migration and runtime scheduling for parallel tasks in computational grids.

Project Title:	Memory management strategies to improve garbage collectors
Investigator(s):	Lau FCM, Wang CL
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2006

Abstract:

1. To devise a low-overhead dynamic object pretenuring mechanism for identifying long-lived objects and allocating them to the mature space directly. 2. To design a nursery sizing policy which can select, against a given total heap size, a best nursery size leading to the best performance of an application. 3. To design an automatic heap sizing policy for controlling the heap growth.

List of Research Outputs

Chen L., Wang C.L. and Lau F.C.M., Process Reassignment with Reduced Migration Cost in Grid Load Rebalancing, 17th International Heterogeneity in Computing Workshop (HCW 2008) . IEEE, 2008.

Feng X. and Lau F.C.M., A Parallel Evolutionary Approach to Multi-objective Optimization, The IEEE Congress on Evolutionary Computation (CEC 2007). Singapore, 2007.

Feng X., Lau F.C.M. and Shuai D.X., The Coordination Generalized Particle Model--An Evolutionary Approach to Multi-sensor Fusion , Information Fusion. Elsevier, 2008, 9: 450-464.

Ho C.Y., Wang C.L. and Lau F.C.M., Scalable Group-based Checkpoint/restart For Large-scale Message-passing Systems, Proceedings Of The 2008 Ieee International Parallel & Distributed Processing Symposium (ipdps 2008). IEEE, 2008.

Ho S.C., Wang C.L. and Lau F.C.M., Lightweight Process Migration and Memory Prefetching in openMosix, Proceedings of 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2008). Miami, USA, IEEE, 2008.

Tsang C.K.K., Wang C.L. and Lau F.C.M., Handoff Performance Comparison of Mobile IP, Fast Handoff and mSCTP in Mobile Wireless Networks (Best Paper Award), The 2008 International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN 2008). IEEE, 2008, 45 - 52.

Tsang C.K.K., Wang C.L. and Lau F.C.M., Handoff Performance Comparison of Mobile IP, Fast Handoff and mSCTP in Mobile Wireless Networks, The 2008 International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN). IEEE Computer Society Press, 2008.

Tse T.H., Lau F.C.M., Chan W.K., Liu P.C.K. and Luk C.K.F., Testing of object-oriented industrial software without precise oracles or results, Communications of the ACM (acceptance rate: < 15%). New York, ACM Press, 2007, 50 (8): 78−85.

Wang R., Lau F.C.M. and Zhao Y.C., Hamiltonicity of Regular Graphs and Blocks of Consecutive Ones in Symmetric Matrices, Discrete Applied Mathematics. 2007, 155: 2312-2320.

Wang R., Lau F.C.M. and Liu Y.Y., On The Hardness Of Minimizing Space For All-shortest-path Interval Routing Schemes, Theoretical Computer Science. 2007, 389: 250-264.

Wang R. and Lau F.C.M., Optimal gossiping in square 2D meshes, Theoretical Computer Science. 2007, 384: 263-286.

Xu S.H., Tan H., Jiao X., Lau F.C.M. and Pan Y., A Generic Pigment Model for Digital Painting, Computer Graphics Forum. 2007, 26.

Xu S.H., Tan H., Jiao X., Lau F.C.M. and Pan Y., A Generic Pigment Model for Digital Painting, Eurographics 2007.

Xu S.H., Jiang H., Lau F.C.M. and Pan Y., An Intelligent System for Chinese Calligraphy, 22nd Conference on Artificial Intelligence (AAAI-07). 2007.

Yu C.H., Lau F.C.M. and Wang C.L., Recycling Memory Blocks for Improving Execution of Java Programs, ACM Transactions on Architecture and Code Optimization. ACM, 2008, 4.

Researcher : Law YW

List of Research Outputs

Kwan Y.K., Chow K.P., Law Y.W. and Lai K.Y., Reasoning About Evidence using Bayesian Networks, In: Indrajit Ray, Sujeet Shenoi, Fourth Annual IFIP WG 11.9 International Conference on Digital Forensics. New York, Springer, 2008, 1: 15.

Law Y.W., Chow K.P., Kwan Y.K. and Lai K.Y., Consistency Issue on Live Systems Forensics, The 2007 International Workshop on Forensics for Future Generation Communication Environments. IEEE Computer Society, 2007, 2: 5.

Law Y.W., Lai K.Y., Jiang L., Ieong S.C.R., Kwan Y.K., Chow K.P., Hui C.K., Yiu S.M. and Chong C.F., Protecting Digital Legal Professional Privilege (LPP) Data, The third International Workshop on Systematic Approaches to Digital Forensic Engineering. Los Alamitos, IEEE Computer Society, 2008, 1: 11.

Researcher : Lee LK

List of Research Outputs

Lam T.W., Lee L.K., Wong P.W.H. and To I.K.K., Competitive Non-migratory Scheduling For Flow Time And Energy, The 20th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). ACM, 2008, 256-264.

Lam T.W., Lee L.K., To I.K.K. and Wong P.W.H., Energy Efficient Deadline Scheduling in Two Processor Systems, The 18th International Symposium on Algorithms and Computation. Springer, 2007, 476-487.

Researcher : Lee SD

List of Research Outputs

Lee S.D., Yee K.C., Cheung D.W.L. and Yuan W., Descriptive Schema: Semantics-based Query Answering, 3rd Semantic Wiki Workshop (SemWiki 2008). 2008.

Lee S.D., Kao C.M. and Cheng R., Reducing UK-means to K-means, The 1st Workshop on Data Mining of Uncertain Data (DUNE 2007) . 2007.

Lo E., Kao C.M., Ho W.S., Lee S.D., Chui C.K. and Cheung D.W.L., OLAP on Sequence Data, ACM SIGMOD International Conference on Management of Data (SIGMOD 2008). 2008.

Researcher : Lee TYT

List of Research Outputs

Cheung D.W.L., Yee K.C. and Lee T.Y.T., Webformer: A Rapid Application Development Toolkit for Writing Ajax Web Form Applications, International Conference on Distributed Computing and Internet Technology (ICDCIT 2007). Springer Berlin / Heidelberg, 2007, 4882/2007: 248-253.

Cheung D.W.L. and Lee T.Y.T., XML Schema Design Methodology Training, Macau University of Science & Technology. Macau, 2007.

Researcher : Leung CM

List of Research Outputs

Chin F.Y.L. and Leung C.M., DNA Motif Representation with Nucleotide Dependency, In: Dan Gusfield, IEEE/ACM Transactions on Computational Biology and Bioinformatics. USA, IEEE Computer Society, 2008, 5: 110-119.

Chin F.Y.L., Leung C.M., Siu M.H. and Yiu S.M., Optimal Algorithm for Finding DNA Motifs with Nucleotide Adjacent Dependency, The Sixth Asia-Pacific Bioinformatics Conference (APBC 2008). Kyoto, Japan, 2008, 343-352.

Chin F.Y.L., Leung C.M. and Sung W.K., The Point Placement Problem on a Line - Improved Bounds for Pairwise Distance Queries, The 7th Workshop on Algorithms in Bioinformatics (WABI 2007). Philadelphia, Pennsylvania, USA, Springer, 2007, LNCS 4645: 372-382.

Leung C.M., Siu M.H., Yiu S.M., Chin F.Y.L. and Sung K.W.K., Finding Linear Motif Pair from Protein Interaction Networks: A Probabilistic Approach, The 6th Annual International Conference on Computational Systems Bioinformatics Conference (CSB 2007). San Diego, California, USA, 2007, 111-120.

Researcher : Leung WS

List of Research Outputs

Leung W.S., Lin M.C., Cheung D.W.L. and Yiu S.M., A Clustering-Based Approach for Filtering False Positive MicroRNA Candidates, 4-th International Symposium on Bioinformatics Research and Applications; May 6-9, 2008; Department of Computer Science, Georgia State University; Atlanta, Georgia (Lecture Notes in Bioinformatics (LNBI)). 2008.

Leung W.S., Shen Z., Yiu S.M., Kung H.F. and Lin M.C., Characterization of HGFK1 Signaling Networks in Microvessel Endothelial and Hepatoma Cell Lines, International Conference on Bioinformatics 2007; 27-30 August 2007; Hong Kong. 2007.

Leung W.S., Yiu S.M., Cheung D.W.L., Lai L., Lin M.C. and Kung H.F., Computational Prediction on Mammalian and Viral MicroRNAs - a Review, International Journal of Integrative Biology. 2007, 1(2): 118-126.

Shen Z., Leung W.S., Yiu S.M., Kung H.F. and Lin M.C., The Molecular Mechanisms of the Dual Anti-angiogenic and Anti-tumor Effects of rAAV-HGFK1, 11th Annual Meeting of the American Society of Gene Therapy May 28-June 1, 2008; Boston, Massachusetts, USA.. 2008.

Researcher : Li S

List of Research Outputs

Li S., Combining Silhouettes and Shading Cues for Model Reconstruction. Hong Kong, 2008.

Researcher : Li W

List of Research Outputs

Li W., A Study of an Active Approach to Speaker and Task Adaptation based on Automatic Analysis of Vocabulary Confusability. Hong Kong, 2008.

Researcher : Liang C

List of Research Outputs

Liang C., 3D Model Reconstruction from Silhouettes. 2008.

Liang C. and Wong K.K.Y., Exact Visual Hull from Marching Cubes, International Conference on Computer Vision Theory and Applications. Funchal, Madeira, Portugal, 2008, 2: 597-604.

Liang C. and Wong K.K.Y., Robust Recovery of Shapes with Unknown Topology from the Dual Space, IEEE Transactions on Pattern Analysis and Machine Intelligence . IEEE Computer Society, 2007, 29(12): 2205-2216.

Researcher : Liu KS

List of Research Outputs

Chan H.L., Lam T.W. and Liu K.S., Extra Unit-Speed Machines Are Almost as Powerful as Speedy Machines for Flow Time Scheduling, SIAM Journal on Computing. USA, SIAM, 2008, 37:5: 1595-1612.

Researcher : Liu Y

List of Research Outputs

Chen F.L., Wang W.P. and Liu Y., Computing singular points of plane rational curves, Journal of Symbolic Computation. 2008, 43, no. 2: 92-117.

Cheng K.S.D., Wang W.P., Qin H., Wong K.K.Y., Yang H.P. and Liu Y., Design and Analysis of Optimization Methods for Subdivision Surface Fitting, IEEE Transactions on Visualization and Computer Graphics. 2007, 13(5): 878-890.

Liu Y. and Wang W.P., A revisit to least squares orthogonal distance
tting of para- metric curves and surfaces, Geometric Modeling and Pro- cessing 2008, Hangzhou, China, April, 2008.. 2008.

Pottmann H., Liu Y., Wallner J., Bobenko A. and Wang W.P., Geometry of multi-layer freeform structures for architecture, ACM Transactions on Graphics, (SIGGRAPH 2007). 2007, vol. 26, no. 2.

Wang W.P., Juttler B., Zheng D. and Liu Y., Computation of rotation minimizing frames, ACM Transactions on Graphics. 2008, 27, Issue 1.

Researcher : Lu H

List of Research Outputs

Lu H., Chan W.K. and Tse T.H., Testing pervasive software in the presence of context inconsistency resolution services, Proceedings of the 30th International Conference on Software Engineering (ICSE 2008), ACM Press, New York, NY (acceptance rate: 15.1%). 2008, 61−70.

Researcher : Lu L

List of Research Outputs

Lu L., Choi Y.K., Wang W.P. and Kim M.S., Variational 3D shape segmentation for bounding volume computation, Computer Graphics Forum, (Eurographics 2007). 2007, vol. 26, no. 3.

Researcher : Mak KS

List of Research Outputs

Mak K.S., Energy Efficient Online Deadline Scheduling. 2008.

Researcher : Mamoulis N

Project Title:	Continuous Constraint Query Evaluation for Spatio-temporal Data Sequences
Investigator(s):	Mamoulis N, Cheung DWL
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2005

Abstract:

The main objectives of this project are: (1) The development of effective techniques that manage and index incoming events in memory. These techniques will take adantage of the special nature of the queries to minimize the required memory. (2) The development of appropriate algorithms for evaluation of CCQ. The algorithms should consider the online, dynamic nature of the queries. Each time a new event arrives, we need to validate whether it forms a query result with past events. (3) The development of approximate management and query evaluation solutions for problem settings, when the required memory is smaller than the available. For such cases, we should consider data structures like spatiotemporal histograms, which could allow query evaluation with some uncertainty. (4) The integration of the developed system with a spatiotemporal pattern mining module that will automatically define the CCQs.

Project Title:	Evaluation of advanced spatial queries in sensor networks
Investigator(s):	Mamoulis N
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	01/2007

Abstract:

(1) We aim at providing methods that continuously evaluate advanced spatial queries in a sensor network locally, avoiding as much as possible unnecessary transmission of information to (potentially remote) centralized servers (i.e., information collectors). We are especially interested in queries that combine information from neighbor nodes, instead of monitoring simple aggregate results in a spatial region. An interesting class of such queries is spatial-pattern queries (a.k.a. structural spatial queries [PMD98]), which are generalizations of spatial joins. An example of a query in this class is “a high-temperature reading (>50 degrees) close to and surrounded by at least four low-humidity readings (

List of Research Outputs

Hadjieleftheriou M., Mamoulis N. and Tao Y., Continuous Constraint Query Evaluation for Spatiotemporal Streams, 10th International Symposium on Spatial and Temporal Databases (SSTD). 2007.

Mamoulis N., Yiu M.L., Cheng K.H. and Cheung D.W.L., Efficient Top-k Aggregation of Ranked Inputs, ACM Transactions on Database Systems . Association of Computing Machinery, 2007, 32(3).

U L.H., Mamoulis N. and Yiu M.L., Continuous Monitoring of Exclusive Closest Pairs, Proceedings of the 10th International Symposium on Spatial and Temporal Databases (SSTD) . Boston, MA, US, Springer, 2007, 4605: 1-19.

Wong W.K., Cheung D.W.L., Hung E., Kao C.M. and Mamoulis N., Security in Outsourcing of Association Rule Mining, The 33rd International Conference on Very Large Data Bases. 2007.

Yiu M.L., Mamoulis N. and Bakiras S., Retrieval of Spatial Join Pattern Instances from Sensor Networks, 19th International Conference on Scientific and Statistical Database Management (SSDBM). 2007.

Yiu M.L., Tao Y. and Mamoulis N., The Bdual-Tree: Indexing Moving Objects by Space-Filling Curves in the Dual Space, the VLDB Journal. Springer, 2008, 17(3): 379-400.

Researcher : Man LY

List of Research Outputs

Chow K.P., Cheng K.Y., Man L.Y., Lai K.Y., Hui C.K., Chong C.F., Pun K.H., Tsang W.W., Chan H.W. and Yiu S.M., BTM—An Automated Rule-Based BT Monitoring System for Piracy Detection, The Second International Conference on Internet Monitoring and Protection, ICIMP 2007. Silicon Valley, USA, IEEE Computer Society Press, 6 pages.

Researcher : Mei L

List of Research Outputs

Mei L., Chan W.K. and Tse T.H., Data flow testing of service-oriented workflow applications, Proceedings of the 30th International Conference on Software Engineering (ICSE 2008), ACM Press, New York, NY (acceptance rate: 15.1%). 2008, 371−380.

Researcher : Peng Z

List of Research Outputs

Peng Z., Ting H.F. and Berry V., From Constrained To Unconstrained Maximum Agreement Subtree In Linear Time, In: M.Y. Kao, Algorithmica. New York, Springer, 2008, 50(3): 369--385.

Ting H.F. and Peng Z., Guided forest edited distance: Better structure comparisons by using domain knowledge, In: Bin Ma, Kaizhong Zhang, Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching. Springer, 2007, 195-204.

Researcher : Peng Z

List of Research Outputs

Peng Z., Ting H.F. and Berry V., From Constrained To Unconstrained Maximum Agreement Subtree In Linear Time, In: M.Y. Kao, Algorithmica. New York, Springer, 2008, 50(3): 369--385.

Researcher : Pun KH

Project Title:	Community Legal Information Project
Investigator(s):	Pun KH
Department:	Computer Science
Source(s) of Funding:	Department of Justice, HKSAR Government - General Award
Start Date:	04/2004

Abstract:

To study community legal information.

List of Research Outputs

Chow K.P., Cheng K.Y., Man L.Y., Lai K.Y., Hui C.K., Chong C.F., Pun K.H., Tsang W.W., Chan H.W. and Yiu S.M., BTM—An Automated Rule-Based BT Monitoring System for Piracy Detection, The Second International Conference on Internet Monitoring and Protection, ICIMP 2007. Silicon Valley, USA, IEEE Computer Society Press, 6 pages.

Li Z., Chong C.F., Hui C.K., Yiu S.M., Chow K.P., Tsang W.W., Chan H.W. and Pun K.H., An Attack on Libert et al.’s ID-Based Undeniable Signature Scheme, International Journal of Network Security. Seoul, Korea, 2007, Vol. 5, No. 2: 220-223.

Researcher : Siu MH

List of Research Outputs

Chin F.Y.L., Leung C.M., Siu M.H. and Yiu S.M., Optimal Algorithm for Finding DNA Motifs with Nucleotide Adjacent Dependency, The Sixth Asia-Pacific Bioinformatics Conference (APBC 2008). Kyoto, Japan, 2008, 343-352.

Leung C.M., Siu M.H., Yiu S.M., Chin F.Y.L. and Sung K.W.K., Finding Linear Motif Pair from Protein Interaction Networks: A Probabilistic Approach, The 6th Annual International Conference on Computational Systems Bioinformatics Conference (CSB 2007). San Diego, California, USA, 2007, 111-120.

Researcher : Su Q

List of Research Outputs

Su Q., Wong K.K.Y. and Fung S.K., A Semi-Automatic Clustering-Based Level Set Method for Segmentation of Endocardium from MSCT Images, 29th Annual International Conference of the IEEE Engineering in Medicine and Biology Society. Lyon, France, 2007, 6023-6026.

Researcher : Tam SL

List of Research Outputs

Hon W.K., Lam T.W., Shah R., Tam S.L. and Vitter J., Cache-Oblivious Index for Approximate String Matching, The 18th Annual Symposium on Combinatorial Pattern Matching (CPM). 2007.

Hon W.K., Lam T.W., Shah R.A.H.U.L., Tam S.L. and Vitter J.S., Compressed Index for Dictionary Matching, IEEE Data Compression Conference. IEEE Computer Society, 2008, 23-32.

Lam T.W., Sung W.K., Tam S.L., Wong C.K. and Yiu S.M., An Experimental Study of Compressed Indexing and Local Alignments of DNA, First International Conference on Combinatorial Optimization and Applications. Springer, 2007, 242-254.

Lam T.W., Sung W.K., Tam S.L., Wong C.K. and Yiu S.M., Compressed indexing and local alignment of DNA, Bioinformatics. Oxford University Press, 2008, 24 (6): 791-797.

Lam T.W., Sung W.K., Tam S.L. and Yiu S.M., Space Efficient Indexes for String Matching with Don't Cares, The 18th International Symposium on Algorithms and Computation . Springer, 2007, 846-857.

Researcher : Tan H

List of Research Outputs

Xu S.H., Tan H., Jiao X., Lau F.C.M. and Pan Y., A Generic Pigment Model for Digital Painting, Computer Graphics Forum. 2007, 26.

Xu S.H., Tan H., Jiao X., Lau F.C.M. and Pan Y., A Generic Pigment Model for Digital Painting, Eurographics 2007.

Researcher : Ting HF

Project Title:	Algorithmic issues on designing media-on-demand systems
Investigator(s):	Ting HF, Lam TW
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	08/2002

Abstract:

With the use of relative-competitive analysis for online systems, the project attempts to provide a theoretical foundation for comparing different media-on-demand (MOD) systems and thus helps to decide scientifically the right configurations. It is anticipated that results of the analysis can be used to design schedulers with performance guarantee and implement computational tools for building cost-effective MOD systems.

Project Title:	Design and analysis of algorithms for constrained structure comparisons
Investigator(s):	Ting HF
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	08/2006

Abstract:

1 (The motivation and background for the objectives are given in the next sections.) We design efficient algorithms for the Constrained Maximum agreement subtree (CMAST) problem and the Constrained Forest Edit-Distance (CFED) problem, which find important applications in bioinformatics, especially in comparative and evolutionary genomics. 2 We implement our algorithms and develop a Web-based tool that allows other biologists use our algorithms to solve their problems. 3 We gain, from our study, insights into the underlying intricacy of a new class of problems, namely the constrained combinatorial optimization problems, and develop general algorithmic techniques for them. 4 We explore a new problem solving methodolgy, namely knwoledge-based problem solving, and study how domain knowledge help us solve difficult problems.

List of Research Outputs

Chin F.Y.L., Ting H.F. and Zhang Y., A Constant-competitive Algorithm for Online OVSF Code Assignment, The 18th International Symposium on Algorithms and Computation (ISAAC 2007). Sendai, Japan, Springer Berlin / Heidelberg, 2007, 4835/2007: 452-463.

Hung R.Y.S. and Ting H.F., Competitive analysis of most-request-first for scheduling broadcasts with start-up delay, In: G. Ausiello, and D. Sannella , Theoretical Computer Science. Amsterdam, The Netherlands., ELSEVIER, 2008, 361(1-3): 200--211.

Hung R.Y.S., Lai K.F. and Ting H.F., Finding Frequent Items in a Turnstile Data Stream, In: Xiaodong Hu, and Jie Wang, Proceedings of the 14th Annual International Symposium on Theoretical Informatics. Springer, 2008, 498--509.

Hung R.Y.S. and Ting H.F., Finding Heavy Hitters Over The Sliding Window Of A Weighted Data Stream, In: Eduardo Laber, Proceedings of the 8th Latin America Symposium on Theoretical Informatics. New York, Springer, 2008, 699--710.

Peng Z., Ting H.F. and Berry V., From Constrained To Unconstrained Maximum Agreement Subtree In Linear Time, In: M.Y. Kao, Algorithmica. New York, Springer, 2008, 50(3): 369--385.

Ting H.F., A Near Optimal Scheduler For On-demand Data Broadcasts, In: G. Ausiello and D. Sannella , Theoretical Computer Science. Amsterdam, The Netherlands, ELSEVIER, 2008, 401(1--3): 77--84.

Ting H.F. and Peng Z., Guided forest edited distance: Better structure comparisons by using domain knowledge, In: Bin Ma, Kaizhong Zhang, Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching. Springer, 2007, 195-204.

Researcher : Towey DP

List of Research Outputs

Chan K.P., Chen T.Y. and Towey D.P., Controlling Restricted Random Testing: An Examination of the Exclusion Ratio Parameter, The Nineteenth International Conference on Software Engineering and Knowledge Engineering. Boston, U.S.A., 2007.

Researcher : Tsang CKK

List of Research Outputs

Tsang C.K.K., Wang C.L. and Lau F.C.M., Handoff Performance Comparison of Mobile IP, Fast Handoff and mSCTP in Mobile Wireless Networks (Best Paper Award), The 2008 International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN 2008). IEEE, 2008, 45 - 52.

Tsang C.K.K., Wang C.L. and Lau F.C.M., Handoff Performance Comparison of Mobile IP, Fast Handoff and mSCTP in Mobile Wireless Networks, The 2008 International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN). IEEE Computer Society Press, 2008.

Researcher : Tsang WW

Project Title:	Tests for uniformity
Investigator(s):	Tsang WW, Chow KP, Hui CK, Chan HW, Chong CF, Pun KH
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	01/2005

Abstract:

To develop accurate and easy-to-compute C programs for the cumulative distribution functions of the KS statistic and the Anderson-Darling statistic; to conduct a fair and thorough comparison on the power of various tests for uniformity; to develop new tests for uniformity.

Project Title:	Evaluating the CDF of the Kolmogorov Statistic for unknown parameter case
Investigator(s):	Tsang WW, Chong CF
Department:	Computer Science
Source(s) of Funding:	Small Project Funding
Start Date:	09/2005

Abstract:

A goodness-of-fit test checks whether a set of samples follows a hypothetical distribution. The most common test for checking discrete samples is the chi-square test. The counterpart for real samples is the Kolmogorov-Smirnov (KS) test [3,5]. Consider an ordered set of samples, x1≤x2≤…≤xn, and the hypothetical distribution, F(x), where all parameters of F(x) are known. The empirical distribution function (EDF) is defined as / | 0, x < x1, Fn(x) = < k/n , xk ≤ x < xk+1, k = 1,2,…,n-1, | 1, xn ≤ x. \The Kolmogorov statistic, Dn, measures the maximum absolute distance between F(x) and Fn(x). The test result is conventionally determined by looking up tables of the critical values of Dn obtained from simulation [6]. In 2003, we developed a program that evaluates the cumulative distribution function (CDF) of Dn with 13-digit accuracy for 2 ≤ n ≤ 16000 [4]. The test result can thus be determined from the CDF of Dn. However, the KS test is still not quit readily applicable because the parameters of F(x) are often unspecified in real world applications. For example, in the testing of exponentiality, usually we have no idea on the mean of the exponential distribution. Therefore, we need to first estimate the mean from the samples. Then we check whether the samples follow the exponential distribution of this mean. The Dn so computed is noticeably smaller than that of the case where the mean is known beforehand. Durbin is the first scholar who advocates the study of the difference between the two cases [1,2]. Stephens has worked out a couple approximation formulas for the CDFs of two unknown parameter cases [7]. However, these formulas deviate from the true values by as much as 2%. Such extent of errors is not cmmensurate with the modern computing capability. The objective of this project is to develop accurate computer programs that evaluate the CDFs of Dn for the tests of normality and exponentiality, the two most common goodness-of-fit tests in unknown parameter case.Reference[1] J. Durbin, Distribution theory for tests based on the sample distribution function, Regional Conference Series in Applied Mathematics (9), SIAM, Philadelphia, 1973.[2] J. Durbin, Kolmogorov-smirnov tests when parameters are estimated, with applications to tests of exponentiality and tests on spacings, Biometrika, 62(1): 5-22, 1975.[3] A. Kolmogorov, Sulla determinazione empirical ei una legge di distributione, Giornale Dell' Istituto Italiano Degli Attuari, 4:83-91, 1933.[4] G. Marsaglia, W. W. Tsang and J. Wang, Evaluating Kolmogorov's distribution, Journal of Statistical Software, 8(18): 1-4, 2003.[5] N. V. Smirnov, On the deviation of the empirical distribution function, Recreational Mathematics (Mat. Sbornik), 6:3-26, 1939.[6] M. A. Stephens, EDF statistics for goodness of fit and some comparisons, Journal of the American Statistical Association, 69 (347): 730-737, 1974.[7] M. A. Stephens, Asymptotic results for goodness-of-fit statistics with unknown parameters, Annuals of Statistics, 4:357-369, 1976.

Project Title:	Evaluating the CDFs of the Anderson-Darling Statistics for normality and exponentiality testing
Investigator(s):	Tsang WW
Department:	Computer Science
Source(s) of Funding:	Small Project Funding
Start Date:	12/2006

Abstract:

A goodness-of-fit test checks whether a set of samples follows a hypothetical distribution. The most common test for checking discrete samples is the Pearson’s chi-square test. The most common one for checking real samples is the Kolmogorov-Smirnov (KS) test [6,8]. The Anderson-Darling (AD) test is another test for checking real samples [1,2]. Consider an ordered set of samples, x1≤x2≤…≤xn, and the hypothetical distribution, F(x), whose parameters are completely specified. The empirical distribution function (EDF) is denoted as Fn(x). Fn(x) equals 0 when x < x1, equals k/n when xk ≤ x ≤ xk+1 for k = 1,2,.,n-1, and equals 1 when xn ≤ x. The KS statistic, Dn, measures the maximum absolute distance between F(x) and Fn(x). The AD statistic, An, measures the weighted sum of the squares of the differences between F(x) and Fn(x). The AD test is a special case of the Cramer-von Mises approach. It is more powerful than the KS test [9]. Both Dn and An are distribution-free. The cumulative distribution function (CDF) of An is difficult to evaluate. T. W. Anderson and D. A. Darling have given an integration formula for the limiting CDF [1]. In 1954, they computed critical values of three significant levels of the limiting CDF using numerical integration [2]. P. A. W. Lewis tabulated the CDF of An for n = 1 to 8 and n = ∞ in 1961 [11]. He only evaluated the first two terms of a series expansion of the CDF. In 1974, Stevens gave tables of critical values for the limiting CDF [9]. In 1988, C. D. Sinclair and B. D. Spurr gave two approximation formulas for the limiting CDF [7]. In 2000, D. E. A. Giles derived a saddlepoint approximation for the limiting CDF [5]. His formula has accuracy similar to the Sinclair’s in the right tail of the distribution but superior in the left tail. The accuracy of the formulas or critical values mentioned above is at best 4 to 5 digits. In real life applications, the parameters of a hypothetical distribution are often not known. For example, in the testing of normality, usually we first estimate the mean and variance from the samples. Then we check whether the samples follow the normal distribution with such mean and variance. A test statistic, Dn or An, so computed is noticeably smaller than that of the case where the mean and variance are known beforehand. J. Durbin is the first scholar who advocates the study of the difference between the known (completely specified) and unknown parameter cases [3,4]. The statistics in the latter are not distribution free, i.e., the distribution of Dn or An depends on F(x). Durbin has derived a formula for the limiting CDF of An for exponentiality testing. However, his approach is computationally unstable in the crucial right tail region. M. A. Stephens has tabulated a table of critical values of An for normality and exponentiality testing from simulation results [10]. These values have about 2-digit accuracy in general but deviate from the true ones by as much as 2% in some cases. The objective of this project is to develop computer programs that evaluate the CDFs of the AD statistics in two most common applications 1. To develop a computer program that evaluates the CDF of the AD statistic for normality testing when the mean and variance are estimated from the samples being tested. No such program is currently available. A few critical values of the CDF found in literature deviate from the true values by as much as 2%. We aim at achieving an accuracy of 3 digits. 2. To develop a computer program that evaluates the CDF of the AD statistic for exponentiality testing when the mean is estimated from the samples being tested. No such program is currently available. A few critical values found in literature deviate from the true values by as much as 2%. We aim at achieving an accuracy of 3 digits. References [1] T. W. Anderson and D. A. Darling, Asymptotic theory of certain ‘goodness-of-fit’ criteria based on stochastic processes, Ann. Math. Stat., 23 193-212, 1952. [2] T. W. Anderson and D. A. Darling, A test of goodness of fit, J. Amer. Stat., Assn., 49 765-769, 1954. [3] J. Durbin, Distribution theory for tests based on the sample distribution function, Regional Conference Series in Applied Mathematics (9), SIAM, Philadelphia, 1973. [4] J. Durbin, Kolmogorov-smirnov tests when parameters are estimated, with applications to tests of exponentiality and tests on spacings, Biometrika, 62(1): 5-22, 1975. [5] D. E. A. Giles, A saddlepoint approximation to the distribution function of the Anderson-Darling test statistic, Communications in Statistics: Simulation and Computation, Volume 30, Issue 4, 2001. [6] A. Kolmogorov, Sulla determinazione empirical ei una legge di distributione, Giornale Dell’ Istituto Italiano Degli Attuari, 4:83-91, 1933. [7] Sinclair and B. D. Spurr, Approximations to the Distribution Function of the Anderson-Darling Test Statistic, Journal of the American Statistical Association, Vol. 83, No. 404, December, 1988. [8] N. V. Smirnov, On the deviation of the empirical distribution function, Recreational Mathematics (Mat. Sbornik), 6:3-26, 1939. [9] M. A. Stephens, EDF statistics for goodness of fit and some comparisons, Journal of the American Statistical Association, 69 (347): 730-737, 1974. [10] M. A. Stephens, Asymptotic results for goodness-of-fit statistics with unknown parameters, Annuals of Statistics, 4:357-369, 1976. [11] P. A. W. Lewis, Distribution of the Anderson-Darling statistic, Ann. Math. Stat., 32, 1118-1124, 1961.

List of Research Outputs

Chow K.P., Cheng K.Y., Man L.Y., Lai K.Y., Hui C.K., Chong C.F., Pun K.H., Tsang W.W., Chan H.W. and Yiu S.M., BTM—An Automated Rule-Based BT Monitoring System for Piracy Detection, The Second International Conference on Internet Monitoring and Protection, ICIMP 2007. Silicon Valley, USA, IEEE Computer Society Press, 6 pages.

Li Z., Chong C.F., Hui C.K., Yiu S.M., Chow K.P., Tsang W.W., Chan H.W. and Pun K.H., An Attack on Libert et al.’s ID-Based Undeniable Signature Scheme, International Journal of Network Security. Seoul, Korea, 2007, Vol. 5, No. 2: 220-223.

Researcher : Tse TH

Project Title:	Towards an integrated method for program verification, testing and debugging
Investigator(s):	Tse TH
Department:	Computer Science
Source(s) of Funding:	Incentive Award for RGC CERG Fundable But Not Funded Projects
Start Date:	07/2003

Abstract:

N/A

Project Title:	Towards an integrated method for program testing, proving debugging
Investigator(s):	Tse TH
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2004

Abstract:

To provide an integrated method for testing, proving and debugging; to reduce the cost of software quality assurance by improving on individual techniques for testing, proving and debugging; to improve on the quality and relaibility of the software thus produced; to provide software engineers with effective testing, proving and debugging tools.

Project Title:	27th Annual international computer software and applications conference
Investigator(s):	Tse TH
Department:	Computer Science
Source(s) of Funding:	Croucher Foundation - Conference / Seminars
Start Date:	09/2004

Abstract:

27th Annual international computer software and applications conference

Project Title:	TIRAMISU: testing conText-sensItive, concurRent And MIddleware-baSed Ubiquitous software
Investigator(s):	Tse TH
Department:	Computer Science
Source(s) of Funding:	Seed Funding Programme for Basic Research
Start Date:	02/2006

Abstract:

Ubiquitous computing means computing anywhere and at any time. Context-sensitive ubiquitous software dynamically adapts its operations according to the changing environment. One of the strategic directions of Hong Kong is to become a world-class base for supply chain management. Ubiquitous middleware-based sensor network systems are envisaged to be an essential enabling technology. Nevertheless, many researchers have emphasized the difficulties in assuring the quality of such software, because context-sensitive applications operate in a highly volatile and unpredictable environment. We were the first research group to embark on their testing techniques. We propose a major project to comprehensively address both the integration and unit testing of these systems. Context detections and function activations are the duties of the middleware. In unit testing, test oracles may not be immediately available for a component under test. We propose the application of metamorphic testing to solve the problem, focusing on isotropic context properties. They can reveal failures not identifiable by conventional testing methods. In integration testing, we propose a model in Communicating Sequential Processes to generate test cases that conform to the components in a ubiquitous environment. We make use of a notion of anti-extension, which can help to alleviate the state-explosion problem in test case generation. This project has important theoretical and practical implications. It will solve the major difficulties in testing complex context-sensitive middleware-based ubiquitous software. It will also illustrate the usefulness of formal approaches to software testing in practical situations.

Project Title:	TIRAMISU: testing context-sensitive, concurrent and middleware-based ubiquitous software
Investigator(s):	Tse TH
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2006

Abstract:

1 The objectives of the project are as follows: (a) To provide integration testing techniques for context-sensitive concurrent middleware-based ubiquitous systems, (b) To provide unit testing techniques for context-sensitive concurrent middleware-based ubiquitous systems, (c) To provide software engineers with effective testing procedures and tools for context-sensitive software, and (d) To improve on the quality and reliability of ubiquitous software. 2 The proposed project has important theoretical and practical implications: (i) State explosion is an open problem in software testing and verification. It becomes significantly worse in context-sensitive and concurrent ubiquitous software. This project will address the problem using an enhanced form of extension particularly suitable for conformance testing. (ii) Results of context-sensitive ubiquitous applications may be hidden behind a hardware-software architecture so that they cannot easily be observed or recorded. This project will address the problem of testing context-sensitive software without precise oracles. (iii) Formal methods such as model checking and static analysis are gaining acceptance by practicing software engineers in recent years. This project will help accelerate this trend by demonstrating the usefulness of the CSP model for software engineering and software testing. (iv) The project will provide practical procedures and tools for software engineers to enhance the efficacy of software quality assurance, thus improving the cost-effectiveness of software development. (v) The usefulness of the testing techniques will be evaluated by experimental studies based on simulated and empirical data. (vi) The results of the project are important to the quality assurance of context-sensitive ubiquitous applications in Hong Kong as a logistics centre for Pearl River Delta.

Project Title:	An extensible fault-based predicate testing toolset for wireless sensor network software applications
Investigator(s):	Tse TH, Chan WK
Department:	Computer Science
Source(s) of Funding:	Innovation and Technology Support Programme
Start Date:	09/2006

Abstract:

The primary objective is to design and implement a predicate testing toolset for the development of wireless sensor network (WSN) applications running on TinyOS using nesC as the implementation language. TinyOS is the de facto state-of-the-art operating system for WSN applications. nesC is the de facto development language for TinyOS. Other objective include: (i) to formulate product-one architecture for the testing of embedded software; (ii) to enhance experience in the area of embedded software engineering; (ii) to improve on the quality of WSN applications; (iv) to improve on the quality of WSN applications; (v) to test and enrich the capability of the fault class hieracrhy and gain further insights on predicate testing; and (vi) to provide the industry with a user-friendly toolset for the development of WSN applications.

List of Research Outputs

Chan W.K., Ho J.C.F., Tse T.H. and Yu Y.T., Piping classification to metamorphic testing: an empirical study towards better effectiveness for the identification of failures in mesh simplification programs, Proceedings of the 31st Annual International Computer Software and Applications Conference (COMPSAC 2007), IEEE Computer Society Press, Los Alamitos, CA (acceptance rate: 18%). Los Alamitos, California, IEEE Computer Society Press, 2007, 397−404.

Chen H.Y., Li C. and Tse T.H., Transformation of UML interaction diagrams into contract specifications for object-oriented testing, Proceedings of the 2007 IEEE International Conference on Systems, Man, and Cybernetics (SMC 2007), IEEE Computer Society Press, Los Alamitos, CA. 2007, 1298−1303.

Feng X., Parnas D.L. and Tse T.H., Tabular expression-based testing strategies: a comparison, Proceedings of the Testing: Academic and Industrial Conference: Practice And Research Techniques (TAIC PART 2007), IEEE Computer Society Press, Los Alamitos, CA. IEEE Computer Society Press, Los Alamitos, California, 2007, 134.

Lu H., Chan W.K. and Tse T.H., Testing pervasive software in the presence of context inconsistency resolution services, Proceedings of the 30th International Conference on Software Engineering (ICSE 2008), ACM Press, New York, NY (acceptance rate: 15.1%). 2008, 61−70.

Mathur A.P., Wong W.E. and Tse T.H., Guest Editor, Special Issue for the Seventh International Conference on Quality Software , Journal of Systems and Software. Elsevier, Amsterdam, 2008, 81.

Mei H. and Tse T.H., Guest editors' introduction, Special Issue on Quality Software, International Journal of Software Engineering and Knowledge Engineering. 2007, 17 (6): 687−688.

Mei L., Chan W.K. and Tse T.H., Data flow testing of service-oriented workflow applications, Proceedings of the 30th International Conference on Software Engineering (ICSE 2008), ACM Press, New York, NY (acceptance rate: 15.1%). 2008, 371−380.

Tse T.H., "Come, come, my lords; These oracles are hardly attain'd, And hardly understood": confessions of a software tester, Pro Vice Chancellor (Research) Visiting Professor Lecture, Swinburne University of Technology, Melbourne, Australia. 2007.

Tse T.H., Cover Design, Proceedings of the 7th International Conference on Quality Software (QSIC 2007), IEEE Computer Society Press, Los Alamitos, CA. 2007.

Tse T.H. and Wong W.E., Editorial, Special Issue on Model-Based Software Testing, Journal of Systems and Software. Amsterdam, The Netherlands, Elsevier, 2008, 81 (2): 159−160.

Tse T.H., Foundation Editor, Journal for Universal Computer Science. Springer, Berlin, 2008.

Tse T.H. and Wong W.E., Guest Editor, Special Issue on Model-Based Software Testing, Journal of Systems and Software. Amsterdam, The Netherlands, Elsevier, Amsterdam, 2008, 81 (2).

Tse T.H., Guest Editor, Special Issue on Quality Software, International Journal of Software Engineering and Knowledge Engineering. World Scientific, Singapore, 2008, 11 (2).

Tse T.H., Long Service Award, The University of Hong Kong. 2008.

Tse T.H., Member of Editorial Board, Journal of Systems and Software. Elsevier, Amsterdam, 2008.

Tse T.H., Member of Editorial Board, Software Testing, Verification and Reliability. Wiley, New York, NY, 2008.

Tse T.H., Lau F.C.M., Chan W.K., Liu P.C.K. and Luk C.K.F., Testing of object-oriented industrial software without precise oracles or results, Communications of the ACM (acceptance rate: < 15%). New York, ACM Press, 2007, 50 (8): 78−85.

Tse T.H., Testing of real-life object-oriented software: challenges and solutions, Information and Communication Technologies Research Seminar, Swinburne University of Technology, Melbourne, Australia. 2007.

Tse T.H., Tie and Scarf Design, Hong Kong Joint Council for People with Disabilities. 2007.

Tse T.H., Visiting Professor, Swinburne University of Technology, Australia. 2007.

Wong W.E., Tse T.H., Glass R.L., Basili V.R. and Chen T.Y., An assessment of systems and software engineering scholars and institutions (2001−2005), Journal of Systems and Software. 2008, 81 (6): 1059−1062.

Zhang Z., Chan W.K. and Tse T.H., Synthesizing component-based WSN applications via automatic combination of code optimization techniques, Proceedings of the 7th International Conference on Quality Software (QSIC 2007), IEEE Computer Society Press, Los Alamitos, CA. 2007, 181−190.

Researcher : U LH

List of Research Outputs

U L.H., Mamoulis N. and Yiu M.L., Continuous Monitoring of Exclusive Closest Pairs, Proceedings of the 10th International Symposium on Spatial and Temporal Databases (SSTD) . Boston, MA, US, Springer, 2007, 4605: 1-19.

Researcher : Wang CL

Project Title:	The HKU Grid Computing Research Center
Investigator(s):	Wang CL, Lau FCM
Department:	Computer Science
Source(s) of Funding:	The University of Hong Kong Foundation Seed Grant
Start Date:	07/2003

Abstract:

To share resources and knowledge under the theme of grid computing; to collaborate on a joint effort to develop the Hong Kong grid which will then contribute to the China National Grid and the Asia-Pacific Grid.

Project Title:	A component-based software architecture for context-aware pervasive computing
Investigator(s):	Wang CL, Lau FCM
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2004

Abstract:

To carry out: (1) proactive and context-aware adaptation: to realize the functionality adaptation. The proposed adaptation mechanism should be able to proactively discover contextual information and make applications constantly adapt to the changing environment. (2) mobility Support: to explore the possibilities of using the facet model to achieve better mobility in the pervasive world. In particular, the proposed system will support user mobility, which allows nomadic users to continue their job while switching from device to device. (3) software Extensibility: to build a real-life pervasive application using facets, to demonstrate that the functionalities and the scale of the application could be very extensibe and no longer be restricted by the resource-constrained devices.

Project Title:	Session continuity for mobile computing
Investigator(s):	Wang CL
Department:	Computer Science
Source(s) of Funding:	Small Project Funding
Start Date:	11/2004

Abstract:

To construct the missing session layer support on top of the TCP, which masks network changes caused by terminal mobility from the applications, thereby maintaining virtually uninterrupted dialogs between endpoints; to design a name service which supports flexible mappings between logical entities and their network addresses, and to tackle the inherent performance issues.

Project Title:	Enhanced Distributed JVM for Large-scale Scientific Applications
Investigator(s):	Wang CL
Department:	Computer Science
Source(s) of Funding:	Small Project Funding
Start Date:	04/2006

Abstract:

Many large-scale scientific and commercial data-mining applications are written in Java. These applications are in great need of a huge virtual memory to keep the created Java objects in memory for computation. In this research, we will introduce a cluster middleware, a Distributed JVM (DJVM) that can group the memory in all computing nodes (PCs or servers) to support parallel execution of large-scale memory-demanding Java applications. The DJVM will be built at the virtual machine level and it can make a cluster appear as a single, multi-processor machine to Java applications. Existing JVM or DJVM prototypes don't provide solutions for the problem of supporting huge virtula memory. A sinlge machine JVM can support up to 2GB memory space, which is insufficient for running an application with large data set. Previous approaches in DJVM have limitation in the JVM heap management in supporting an address space larger than 2GB in a 32-bit platform. The difficulties come from two aspects. (1) The JVM specification defines the size of the object refence as a word in a physical machine. On 32-bit machines, it is therefore 32-bit. Extending the address space will need to revise the JVM specification substantially. (2) All previous DJVMs are based on some open-source JVM implementations, which tends to follow the orginal specification. For new implementation, new and careful design in JVM heap and JIT compilers is needed in the DJVM kernel for manipulating of Java references, which is a non-trivious task. It needs to involve complex transformations of new reference type on the 32-bit platforms.To make the existing applications able to be transparently migrated to the new platform, we also need to make sure the Java libraries and latest APIs used by the Java applications can be executed on DJVM. To incorporate different Java libraries in a DJVM is a challenge because a JVM is often shipped with its own class libraries. Simply setting class search path or copying class libraries in the DJVM directories will not work. There are many compatibility problems to solve for a JVM to use another JVM's libraries. A DJVM needs to find a portable and flexible method to solve the transplant of Java libraries for the applications to use.

Project Title:	An advanced distributed java virtual machine on commodity clusters for high-performance memory-intensive computing
Investigator(s):	Wang CL, Lau FCM
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2006

Abstract:

(1) n a distributed Java Virtual Machine (DJVM), threads in a Java program are mapped to different computing nodes for execution and a shared global heap created from the memory of all the participating nodes allows data sharing among physically distributed threads. The state-of-the-art DJVMs can perform thread-to-processor remapping via thread migration to achieve load balancing. Multithreaded programming on a DJVM has the potential to become a preferred approach to high-performance computing. The hurdle, however, lies in the situation where many scientific problems in real life today have huge memory consumptions which are beyond what existing DJVM systems can offer. To our best knowledge, none of the existing DJVMs developed for commodity 32-bit PC clusters can offer cluster-wide sharable memory space exceeding 4 gigabytes (the size limit of virtual memory that a single 32-bit machine can address) no matter how many cluster nodes are used. (2) In this research, we propose to elevate DJVM technologies to a new level so that the new DJVM could support any memory-intensive scientific computing application using commodity 32-bit PC clusters. In the new DJVM, we will build a huge global object space (HGOS), a shared global heap that spans all the cluster nodes and can be larger than 4GB for storing a huge number of objects or very big objects. When large-size objects are in the HGOS, locality of reference becomes an important issue. We consider thread migration a good mechanism to achieve better locality, which can avoid unnecessary data migration. Nevertheless, distributed Java thread execution on a DJVM with thread migration will exhibit different behaviors over time that are not easily captured. The workload of a thread will change after migration because the object access cost will change with the change of execution location. The cache coherence overhead depends on the actual thread location and the sharing status that are only known at execution time. All these will make the workload of the system very unpredictable as compared with those using traditional message-passing solutions. The benefit of thread migration is therefore difficult to be estimated, and such simple heuristics as considering only the workloads of cluster nodes (based on the assumption that workload remains unchanged after migration) will not work. In this research, we propose to build a new DJVM having the following distinctive features. (A) Huge global object space support: To support a huge Java heap with size that can scale with the cluster size, and we will support cluster-wide 64-bit object reference for identifying and locating objects in a 32-bit commodity cluster. New addressing scheme will be developed for accessing segmented objects that are distributed among cluster nodes. (B) Fast wide address translation: As the hardware only supports a 32-bit addressing space, we need a fast software solution to translate the wide references to 32-bit references. An extended pointer swizzling method using a page faulting mechanism will be studied for achieving fast wide address translation and to avoid unnecessary object checking overheads.(C) HGOS-aware cache coherence protocol. As we support large objects that could be allocated across cluster nodes, new cache coherence protocol catered for the HGOS will be developed. Efficient whole object and segmented object caching mechanisms in line with the Java memory model will be explored for efficient object accesses in a cluster environment. (D) HGOS-directed workload model. We will investigate and propose a thread-centric load model to capture the migration benefits under the HGOS. The load model should reflect the explicit communication cost in accessing remote objects and the implicit cost embodied in the cache coherence protocol. A runtime profiling method using JIT-compilation techniques will be used to analyze thread stack contexts for approximating the workload of a thread and its migration benefits.(E) New thread migration policies: Migration policies will be devised based on the proposed workload model for choosing threads for migration to achieve maximum profits. We allow thread migration to take place when (1) thread migration can reduce the object access cost; (2) the workload among the cluster nodes is imbalanced, or (3) new nodes are added to participate in the computation.The proposed solutions make it possible to realize high-performance memory-intensive computations using commodity PC clusters based on the Java multithreading programming paradigm. The implementations of the new DJVM will follow the Java language specification without introducing new APIs or language modifications, which allows any existing Java program that runs on a single-node JVM to run on a cluster without any modification. Therefore, ordinary programmers do not need to learn new complicated parallel languages or runtime systems, such as MPI or software distributed shared memory (DSM). The latter approaches tend to impose a steep learning curve because they use explicit messaging passing or programmer-directed data partitioning to achieve efficient parallel execution.

List of Research Outputs

Chen L., Wang C.L. and Lau F.C.M., Process Reassignment with Reduced Migration Cost in Grid Load Rebalancing, 17th International Heterogeneity in Computing Workshop (HCW 2008) . IEEE, 2008.

Ho C.Y., Wang C.L. and Lau F.C.M., Scalable Group-based Checkpoint/restart For Large-scale Message-passing Systems, Proceedings Of The 2008 Ieee International Parallel & Distributed Processing Symposium (ipdps 2008). IEEE, 2008.

Ho S.C., Wang C.L. and Lau F.C.M., Lightweight Process Migration and Memory Prefetching in openMosix, Proceedings of 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2008). Miami, USA, IEEE, 2008.

Hu H. and Wang C.L., GPS-Based Location Extraction and Presence Management for Mobile Instant Messenger, 2007 IFIP International Conference on Embedded and Ubiquitous Computing (EUC'2007), December 17-20, 2007, Taipei Taiwan.. Berlin, Springer, 2007, 309-320.

Tang F.L., Guo M.Y., Li M.L., Wang C.L. and Dong M., Secure Routing for Wireless Mesh Sensor Networks in Pervasive Environment, International Journal on Intelligent Control and Systems . World Scientific Publishing, 2007, 12: 293-306.

Tsang C.K.K., Wang C.L. and Lau F.C.M., Handoff Performance Comparison of Mobile IP, Fast Handoff and mSCTP in Mobile Wireless Networks (Best Paper Award), The 2008 International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN 2008). IEEE, 2008, 45 - 52.

Tsang C.K.K., Wang C.L. and Lau F.C.M., Handoff Performance Comparison of Mobile IP, Fast Handoff and mSCTP in Mobile Wireless Networks, The 2008 International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN). IEEE Computer Society Press, 2008.

Wang C.L., Computation Migration Techniques for Grid Computing (Invited Talk), The 4th Workshop on Grid Technologies and Applications (WoGTA’07). 2007.

Yu C.H., Lau F.C.M. and Wang C.L., Recycling Memory Blocks for Improving Execution of Java Programs, ACM Transactions on Architecture and Code Optimization. ACM, 2008, 4.

Researcher : Wang R

List of Research Outputs

Wang R., Lau F.C.M. and Zhao Y.C., Hamiltonicity of Regular Graphs and Blocks of Consecutive Ones in Symmetric Matrices, Discrete Applied Mathematics. 2007, 155: 2312-2320.

Wang R., Lau F.C.M. and Liu Y.Y., On The Hardness Of Minimizing Space For All-shortest-path Interval Routing Schemes, Theoretical Computer Science. 2007, 389: 250-264.

Wang R. and Lau F.C.M., Optimal gossiping in square 2D meshes, Theoretical Computer Science. 2007, 384: 263-286.

Researcher : Wang WP

Project Title:	Collision detection of moving ellipses and ellipsoids
Investigator(s):	Wang WP
Department:	Computer Science
Source(s) of Funding:	Seed Funding Programme for Basic Research
Start Date:	10/2002

Abstract:

To study the collision detection problem between moving ellipses in 2D plane and ellipsoids in 3D space. Specially, based on the PI's recent study on the algebraic properties of the arrangement of two ellipsoids.

Project Title:	New methods for collision detection of ellipsoids
Investigator(s):	Wang WP
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	09/2003

Abstract:

To develop methods of collision detection of moving ellipsoids in the following three different cases: i) motions expressible as rational functions of time; ii) motions expressible by analytical functions of time; continuous motions, which include the important class of continuous but "non-smooth' motions due to interactive user control or constant interaction with surrounding objects in a VR or computer game application.

Project Title:	Continuous collision detection for composite quadric models in computer graphics
Investigator(s):	Wang WP
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	07/2006

Abstract:

Establish algebraic conditions to characterize contact configurations of commonly used quadrics, such as ellipsoids, cones and cylinders, in 3D. Based on the above results, develop efficient algorithms for continuous collision detection of composite quadric models in the case where the intersection curves are conics.

Project Title:	New technology for real time and accurate collision detection in computer games and simulation
Investigator(s):	Wang WP, Choi YK, Liu Y, Lu L, Zheng D
Department:	Computer Science
Source(s) of Funding:	Innovation and Technology Support Programme
Start Date:	09/2006

Abstract:

In this project we aim to develop this collision detection technology from basic research results into an easy-to-use software tool kit that emcompasses an array of functions for collision detection of ellipsoids in various application scenarios in computer games and 3D interactive virtual environments. For compatibility with using boxes as bounding volumes, collision detection between boxes and ellipsoids will also be implemented. We will develop a prototype to demonstrate the utility and advantage of new collision detection technology. Our software tool kit will be cross-platofrm and open source in order to maximize its benefit to the computer game community in Hong Kong.

Project Title:	Computational algebraic geometry for industrial applications
Investigator(s):	Wang WP, Choi YK
Department:	Computer Science
Source(s) of Funding:	France/Hong Kong Joint Research Scheme - Travel Grants
Start Date:	01/2007

Abstract:

1. Shape segmentation and representation using quadrics 2. Shape processing using quadrics 3. Collision detection for objects defined by quadric surfaces 4. Software for algebraic modeling

Project Title:	Conmputation of Bounding Ellipsoids
Investigator(s):	Wang WP
Department:	Computer Science
Source(s) of Funding:	Seed Funding Programme for Basic Research
Start Date:	01/2007

Abstract:

Bounding volumes of complex 3D shapes are widely used for computation simulation in computer graphic, robotic, biomedical engineering, and CAD/CAM. We propose a novel, efficient optimization method for computing the ellipsoid bounding volumes of 3D objects. The bounding ellipsoids provide a highly compact representation of 3D shapes, which originally are often represented in the verbose format of point samples, mesh surfaces or planar faces. Thus our resarch will be useful to applications in geometric reasoning and processing, collision detection, compression and transmission of geometric data. The objectives of the projects are:1) We shall investigate the novel use of elliptic metric for 3D shape decomposition in the ellipsoid boundingproblem. Preliminary tests have shown advantages of the elliptic metric over the conventional Euclidean metric. 2) A robust and efficient optimization algorithm will be developed for solving the ellipsoid bounding problem, capable of automatic volume-driven component splitting and merging. Information about features or skeletons, when available, will be exploited for good initialization and stable convergence.

List of Research Outputs

Bo P. and Wang W.P., Geodesic-controlled developable surfaces for modeling paper bending, Computer Graphics Forum, (Eurographics 2007). 2007, vol. 26, no. 3.

Chang J.W., Wang W.P. and Kim M.S., E
cient collision detection using a dual bounding volume hierarchy, to appear, Proceedings of Geometric Modeling and Pro- cessing 2008, Hangzhou, China, April, 2008.. 2008.

Chen F.L., Wang W.P. and Liu Y., Computing singular points of plane rational curves, Journal of Symbolic Computation. 2008, 43, no. 2: 92-117.

Cheng K.S.D., Wang W.P., Qin H., Wong K.K.Y., Yang H.P. and Liu Y., Design and Analysis of Optimization Methods for Subdivision Surface Fitting, IEEE Transactions on Visualization and Computer Graphics. 2007, 13(5): 878-890.

Choi Y.K., Li X.Q., Rong F.G., Wang W.P. and Cameron S., Determining directional contact range of two convex polyhedra,, Proceedings of Geometric Modeling and Processing 2008, Hangzhou, China. 2008.

Kobbelt L. and Wang W.P., (special issue eds), Computer-aided Design, (for the best papers presented at SPM’06), to appear., In: L. Kobbelt and W.P. Wang, Computer-aided Design. 2007.

Liu Y. and Wang W.P., A revisit to least squares orthogonal distance
tting of para- metric curves and surfaces, Geometric Modeling and Pro- cessing 2008, Hangzhou, China, April, 2008.. 2008.

Lu L., Choi Y.K., Wang W.P. and Kim M.S., Variational 3D shape segmentation for bounding volume computation, Computer Graphics Forum, (Eurographics 2007). 2007, vol. 26, no. 3.

Pottmann H., Liu Y., Wallner J., Bobenko A. and Wang W.P., Geometry of multi-layer freeform structures for architecture, ACM Transactions on Graphics, (SIGGRAPH 2007). 2007, vol. 26, no. 2.

Wang L., Tu C.H., Wang W.P. and Meng X.X., Silhouette smoothing for real-time rendering of mesh surfaces, IEEE Transactions on Visualization and Computer Graphics. 2008, 14, no. 3: 640-652.

Wang L., Tu C., Wang W.P., Meng X., Chan B. and Yan D., Silhouette smoothing for real-time rendering of mesh surfaces, IEEE Transactions on Visualization and Computer Graphics. USA, IEEE Computer Society, 2008, 14: 640-652.

Wang W.P., Juttler B., Zheng D. and Liu Y., Computation of rotation minimizing frames, ACM Transactions on Graphics. 2008, 27, Issue 1.

Wang W.P., Geometric modeling of mesh surfaces with planar faces., The First Computer Mathematic Conference, November 12-15, 2007, Nanchang, China.. 2007.

Wang W.P., Geometry and computation of planar hexagonal meshes., COMPASS Workshop (Workshop on Computational Methods for Algebraic Spline Surfaces, September, 2007. Strobl, Austria.. 2007.

Wang W.P., Invited talk at SMI 2008, SMI 2008 (Internal Conference on Shape Moldelling and Applications), June 4-6, 2008, New York, USA.. 2008.

Wang W.P., Invited talk at SRATC 2008, SRATC 2008 (International Seminar on Symbolic Real Algebra and Trustworthy Computing), April 3-5, 2008, Shanghai.. 2008.

Wang W.P., Invited to give talk, Dagstuhl Workshop on CAGD, May 2008, Germany.. 2008.

Wang W.P., Invited to talk at Special Session on Approximation Theory at the FoCM (Foundations of Computational Mathematics) Conference 2008, June, 2008, Hong Kong.. 2008.

Wang W.P., Meshes with planar faces for shape design in architecture., Chinese Conference on Geometric Design and Computing 2007, July, 2007, Lanzhou, China.. 2007.

Researcher : Wong CK

List of Research Outputs

Lam T.W., Sung W.K., Tam S.L., Wong C.K. and Yiu S.M., An Experimental Study of Compressed Indexing and Local Alignments of DNA, First International Conference on Combinatorial Optimization and Applications. Springer, 2007, 242-254.

Lam T.W., Sung W.K., Tam S.L., Wong C.K. and Yiu S.M., Compressed indexing and local alignment of DNA, Bioinformatics. Oxford University Press, 2008, 24 (6): 791-797.

Researcher : Wong KF

List of Research Outputs

Wong K.F., Chiu Y.S., Lam T.W. and Yiu S.M., A Memory Efficient Algorithm for Structural Alignment of RNAs with Embedded Simple Pseudoknots, The 5th Asia-Pacific Bioinformatics Conference . World Scientific, 2008, 89-100.

Researcher : Wong KKY

Project Title:	3D shape recovery of complex objects using a dual-space approach
Investigator(s):	Wong KKY
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	01/2006

Abstract:

The main objective of this project is to develop a novel method for reconstructing complex 3D objects with unknown topology using their silhouettes extracted from the image sequences. The proposed method exploits the duality principle governing surface points and their corresponding tangent planes, and enables direct estimation of points on the contour generators.

Project Title:	Robust recovery of differential information and object shape from silhouettes of unordered viewpoints
Investigator(s):	Wong KKY
Department:	Computer Science
Source(s) of Funding:	Competitive Earmarked Research Grants (CERG)
Start Date:	01/2007

Abstract:

The main objective of this project is to provide a robust computer vision based method for acquiring photorealistic 3D models of real world objects. Traditionally, high quality models are obtained through 3D laser scanners which are often expensive and not portable. The use of computer vision techniques provides a much cheaper alternative, and requires no more than a commercial grade imaging device. This is a vast advantage over laser scanners because no active sensor is required by these techniques, and there are fewer physical restrictions placed upon the object to be acquired. In this project, the silhouettes of the object are exploited to recover the differential properities of the object surface. Silhouettes are the profiles of the objects in the images, and they offer rich information about the shape of the objects. Compared with point features used in traditional photogrammetry algorithms, silhouettes can often be reliably extracted and provide relatively complete shape description about the observed objects. However, silhouettes in multiple views generally do not come with correspondent features, and hence the depth of the points on the silhouettes cannot be directly estimated using traditional stereovision techniques. Existing methods for reconstruction from silhouettes can be classified into two categories, namely volumetric approaches and differential approaches. While the volumetric approaches are more robust to objects with complicated shapes than existing differential approaches, they produce much less accurate surface points than differential approaches. Both the volumetric and differential approaches, however, can only reconstruct the visual hull of the object, and cannot reproduce concavities on the object surface. This project aims at bringing several important improvements over the existing differential approaches proposed by others and by the applicant: I) it can handle a more general configuration consisting of discrete viewpoints (cameras) with arbitrary spatial order, while existing differential approaches generally require the camera to travel a continuous path; II) it can extract a relatively complete and topologically correct surface like the volumetric approaches, while retain the accuracy of the differential approaches; III) it allows the integration of textural or shading information for further refinement of the reconstructed models and introduces concavities on the surface which cannot be inferred from silhouettes alone. To address the first issue, a novel distance measure between cameras is proposed. For each camera, we can dynamically discover the nearby cameras that allow differential structure on the surface to be estimated accurately. The second issue is addressed by introducing a novel generic surface extraction algorithm robust to a variety of topology of the observed object. The algorithm is motivated by the literature of medical image processing, particularly, surface extraction from cross-sections. The solution to the last issue is made possible by the nature of the methods we used to address the first two issues. By directly recovering the differential properties on the surface, we can easily locate the flat areas on the surface, which are de facto the candidate regions for concavities. The surface extraction algorithm we adopted conveniently allows us to insert vertices in the regions of interests, and refinement can then be done more efficiently. The proposed approach does not depend on the spatial order of the viewpoints of the input images, and can robustly reconstruct a complete complex object surface with high accuracy, and with the possibility of further refinement for introducing concavities to the model.

List of Research Outputs

Cheng K.S.D., Wang W.P., Qin H., Wong K.K.Y., Yang H.P. and Liu Y., Design and Analysis of Optimization Methods for Subdivision Surface Fitting, IEEE Transactions on Visualization and Computer Graphics. 2007, 13(5): 878-890.

He X., Yung N.H.C., Chow K.P., Chin F.Y.L., Chung H.Y., Wong K.K.Y. and Tsang K.S.H., Watershed Segmentation with Boundary Curvature Ratio Based Merging Criterion, 9th IASTED International Conference on Signal and Image Processing. Honolulu, Hawaii, USA, 2007, 7-12.

Liang C. and Wong K.K.Y., Exact Visual Hull from Marching Cubes, International Conference on Computer Vision Theory and Applications. Funchal, Madeira, Portugal, 2008, 2: 597-604.

Liang C. and Wong K.K.Y., Robust Recovery of Shapes with Unknown Topology from the Dual Space, IEEE Transactions on Pattern Analysis and Machine Intelligence . IEEE Computer Society, 2007, 29(12): 2205-2216.

Su Q., Wong K.K.Y. and Fung S.K., A Semi-Automatic Clustering-Based Level Set Method for Segmentation of Endocardium from MSCT Images, 29th Annual International Conference of the IEEE Engineering in Medicine and Biology Society. Lyon, France, 2007, 6023-6026.

Yuk S.C., Wong K.K.Y., Chung H.Y., Chow K.P., Chin F.Y.L. and Tsang K.S.H., Object-Based Surveillance Video Retrieval System With Real-Time Indexing Methodology, International Conference on Image Analysis and Recognition. Montreal, Canada, 2007, 626-637.

Researcher : Wong KY

List of Research Outputs

Wong K.Y. and Yip C.L., A Fast and Noise-tolerant Method for Positioning Centers of Spiraling and Circulating Vector Fields, Proceedings of the 8th Asian Conference on Computer Vision (ACCV-2007). 2007.

Wong K.Y., Yip C.L. and Li P.W., Automatic tropical cyclone eye fix using genetic algorithm, Expert Systems With Applications. Elsevier, 2008, 34: 643-656.

Wong K.Y., Positioning patterns from multidimensional data and its applications in meteorology. 2008.

Researcher : Wong WK

List of Research Outputs

Wong W.K., Cheung D.W.L., Hung E. and Liu H., Protecting Privacy in Incremental Maintenance for Distributed Association Rule Mining, The 12th Pacific-Asia Conference on Knowledge Discovery and Data Mining. 2008.

Wong W.K., Security in Associate Rule Mining. Hong Kong, 2008.

Wong W.K., Cheung D.W.L., Hung E., Kao C.M. and Mamoulis N., Security in Outsourcing of Association Rule Mining, The 33rd International Conference on Very Large Data Bases. 2007.

Researcher : Yan D

List of Research Outputs

Wang L., Tu C., Wang W.P., Meng X., Chan B. and Yan D., Silhouette smoothing for real-time rendering of mesh surfaces, IEEE Transactions on Visualization and Computer Graphics. USA, IEEE Computer Society, 2008, 14: 640-652.

Researcher : Yan L

List of Research Outputs

Yan L., On The Traffic Flow Control System. 2007.

Yan L., On Traffic Network Flow Monitoring System . 2007.

Researcher : Ye D

List of Research Outputs

Chan W.T., Chin F.Y.L., Ye D., Zhang G. and Zhang Y., On-line scheduling of parallel jobs on two machines, Journal of Discrete Algorithms . Amsterdam, The Netherlands, Elsevier Science Publishers B. V., 2008, 6(1): 3-10.

Researcher : Yee KC

List of Research Outputs

Cheung D.W.L., Yee K.C. and Kwok R.P.M., B2B Exchange Technology Training, Thammasat University. Thailand, 2007.

Cheung D.W.L., Yee K.C. and Lee T.Y.T., Webformer: A Rapid Application Development Toolkit for Writing Ajax Web Form Applications, International Conference on Distributed Computing and Internet Technology (ICDCIT 2007). Springer Berlin / Heidelberg, 2007, 4882/2007: 248-253.

Lee S.D., Yee K.C., Cheung D.W.L. and Yuan W., Descriptive Schema: Semantics-based Query Answering, 3rd Semantic Wiki Workshop (SemWiki 2008). 2008.

Researcher : Yip CL

List of Research Outputs

Wong K.Y. and Yip C.L., A Fast and Noise-tolerant Method for Positioning Centers of Spiraling and Circulating Vector Fields, Proceedings of the 8th Asian Conference on Computer Vision (ACCV-2007). 2007.

Wong K.Y., Yip C.L. and Li P.W., Automatic tropical cyclone eye fix using genetic algorithm, Expert Systems With Applications. Elsevier, 2008, 34: 643-656.

Zhang M., Kao C.M., Cheung D.W.L. and Yip C.L., Mining Sequence Patterns in Evolving Databases, In: Hsu, Lee, Temporal and Spatio-Temporal Data Mining. Idea Group Inc., 2007.

Researcher : Yiu ML

List of Research Outputs

U L.H., Mamoulis N. and Yiu M.L., Continuous Monitoring of Exclusive Closest Pairs, Proceedings of the 10th International Symposium on Spatial and Temporal Databases (SSTD) . Boston, MA, US, Springer, 2007, 4605: 1-19.

Yiu M.L., Tao Y. and Mamoulis N., The Bdual-Tree: Indexing Moving Objects by Space-Filling Curves in the Dual Space, the VLDB Journal. Springer, 2008, 17(3): 379-400.

Researcher : Yiu ML

List of Research Outputs

Yiu M.L., Tao Y. and Mamoulis N., The Bdual-Tree: Indexing Moving Objects by Space-Filling Curves in the Dual Space, the VLDB Journal. Springer, 2008, 17(3): 379-400.

Researcher : Yiu SM

Project Title:	RNA Secondary Structure Prediction with Pseudoknots in Unaligned Sequences
Investigator(s):	Yiu SM, Chin FYL
Department:	Computer Science
Source(s) of Funding:	Seed Funding Programme for Basic Research
Start Date:	09/2006

Abstract:

Ribonucleic acids (RNAs) are molecules that are responsible for regulating many genetic and metabolic activities in cells. RNA is single-stranded and can be considered as a sequence of nucleotides (also known as bases). There are four basic nucleotides, namely, Adenine (A), Cytosine (C), Guanine (G), and Uracil (U). An RNA folds into a 3-dimensional structure by forming pairs of bases using hydrogen bonds and the set of base pairs formed is referred as the secondary structure of the RNA. Each base can at most form a pair with another base. In particular, A-U and C-G form stable pairs and are known as the Watson-Crick base pairs. Other pairings (e.g. A-C) are less stable and seldom exist in RNA molecules, so are usually ignored. The 3-dimensional structure is related to the function of the RNA. Thus, knowing the pairing of the bases can help to predict the 3-dimensional structure as well as the function of the RNA. In this project, we focus on the problem of predicting RNA secondary structure. Given an RNA sequence, there are many different possible secondary structures. To compute the most probable structure, a commonly used measurement is based on the concept of minimzing the total free energy of the substructures (e.g. loops, stacking pairs) formed by the pairings. From a computatioal point of view, the challenge of the RNA secondary structure prediction problem arises from some special structures called "pseudoknots" (see more details in Section VII). Many existing prediction algorithms do not consider pseudoknots, however, pseudoknots are already known to exist in some RNAs. The dynamic programming algorithm [LZP99, ZS84] for computing the optimal secondary structure without pseudoknots based on the free energy minimization model runs in O(n^3) time where n is the length of the RNA sequence. On the other hand, based on some special energy functions, Lyngso and Pederson [LP00] have proven that determining the optimal secondary structure possibly with pseudoknots is NP-hard. When restricting the problem to some special types of pseudoknots, there exist polynomial time algorithms (e.g. [A00, RE99, UHK+99]. However, the time complexity is still high and thus may not be very practical. On the other hand, from some recent studies [e.g. MT02], it was found that to predict the secondary structure of a given RNA sequence, it is more accurate if we also make use of some other RNA sequences which are known to have similar functions as the given RNA sequecne. Roughly speaking, we are given a set of unaligned RNA sequences, the problem is to predict the common secondary structure of these sequences while aligning them at the same time. The intuition behind is that functionally similar RNA sequences usually have similar secondary structures. The alignment of the sequences can guide to locate the important substructures of the secondary structure. Thus, there is a higher chance to get a correct structure. Mathews and Turner [MT02] provided an O(n^6) time algorithm for two sequences without considering pseudoknots and it was shown to be NP-hard for multiple sequences [DB04]. Other works along this direction include [S85, AKS+06, BTZ06, GHS97]. Most of these works do not consider pseudoknots or are heuristics-based.The objective of the project is to study of the problem of predicting the common secondary structure with pseudoknots of a given set of unaligned RNA sequences from both the theoertical and the practical aspects. In particular, we aim at deriving efficient solutions (exact algorithms, approximation algorithms, and/or heuristics-based algorithms) for the following problems. P1) Given two unaligned RNA sequences, the problem is to predict their common secondary structure with "simple pseudoknots (see Section VII for definitions)" based on different optimization criteria (e.g. minimizing the total free energy of the structure, maximizing the number of base pairs).P2) Extend the problem in 1) to other common types of pseudoknots.P3) Extend the problem in 1) and 2) to consider more than two sequences.

List of Research Outputs

Chan H.L., Lam T.W., Sung W.K., Wong P.W.H. and Yiu S.M., Non-overlapping Common Substrings Allowing Mutations , Mathematics in Computer Science. Springer, 2008, 543-555.

Chin F.Y.L., Leung C.M., Siu M.H. and Yiu S.M., Optimal Algorithm for Finding DNA Motifs with Nucleotide Adjacent Dependency, The Sixth Asia-Pacific Bioinformatics Conference (APBC 2008). Kyoto, Japan, 2008, 343-352.

Chow K.P., Cheng K.Y., Man L.Y., Lai K.Y., Hui C.K., Chong C.F., Pun K.H., Tsang W.W., Chan H.W. and Yiu S.M., BTM—An Automated Rule-Based BT Monitoring System for Piracy Detection, The Second International Conference on Internet Monitoring and Protection, ICIMP 2007. Silicon Valley, USA, IEEE Computer Society Press, 6 pages.

Jiang L., Hui C.K., Chow K.P., Yiu S.M. and Lai K.Y., Improving Disk Sector Integrity Using 3-dimension Hashing Scheme, The 2007 International Workshop on Forensics for Future Generation Communication Environments. IEEE Computer Society, 2007, 2: 5.

Jiang L., Hui C.K. and Yiu S.M., Improving Disk Sector Integrity Using k-dimension Hashing, IFIP International Federation for Information Processing. Japan, Springer Boston, 2008, 285: 87-98.

Lam T.W., Sung W.K., Tam S.L., Wong C.K. and Yiu S.M., An Experimental Study of Compressed Indexing and Local Alignments of DNA, First International Conference on Combinatorial Optimization and Applications. Springer, 2007, 242-254.

Lam T.W., Sung W.K., Tam S.L., Wong C.K. and Yiu S.M., Compressed indexing and local alignment of DNA, Bioinformatics. Oxford University Press, 2008, 24 (6): 791-797.

Lam T.W., Sung W.K., Tam S.L. and Yiu S.M., Space Efficient Indexes for String Matching with Don't Cares, The 18th International Symposium on Algorithms and Computation . Springer, 2007, 846-857.

Law Y.W., Lai K.Y., Jiang L., Ieong S.C.R., Kwan Y.K., Chow K.P., Hui C.K., Yiu S.M. and Chong C.F., Protecting Digital Legal Professional Privilege (LPP) Data, The third International Workshop on Systematic Approaches to Digital Forensic Engineering. Los Alamitos, IEEE Computer Society, 2008, 1: 11.

Leung C.M., Siu M.H., Yiu S.M., Chin F.Y.L. and Sung K.W.K., Finding Linear Motif Pair from Protein Interaction Networks: A Probabilistic Approach, The 6th Annual International Conference on Computational Systems Bioinformatics Conference (CSB 2007). San Diego, California, USA, 2007, 111-120.

Leung W.S., Lin M.C., Cheung D.W.L. and Yiu S.M., A Clustering-Based Approach for Filtering False Positive MicroRNA Candidates, 4-th International Symposium on Bioinformatics Research and Applications; May 6-9, 2008; Department of Computer Science, Georgia State University; Atlanta, Georgia (Lecture Notes in Bioinformatics (LNBI)). 2008.

Leung W.S., Shen Z., Yiu S.M., Kung H.F. and Lin M.C., Characterization of HGFK1 Signaling Networks in Microvessel Endothelial and Hepatoma Cell Lines, International Conference on Bioinformatics 2007; 27-30 August 2007; Hong Kong. 2007.

Leung W.S., Yiu S.M., Cheung D.W.L., Lai L., Lin M.C. and Kung H.F., Computational Prediction on Mammalian and Viral MicroRNAs - a Review, International Journal of Integrative Biology. 2007, 1(2): 118-126.

Li Z., Chong C.F., Hui C.K., Yiu S.M., Chow K.P., Tsang W.W., Chan H.W. and Pun K.H., An Attack on Libert et al.’s ID-Based Undeniable Signature Scheme, International Journal of Network Security. Seoul, Korea, 2007, Vol. 5, No. 2: 220-223.

Shen Z., Leung W.S., Yiu S.M., Kung H.F. and Lin M.C., The Molecular Mechanisms of the Dual Anti-angiogenic and Anti-tumor Effects of rAAV-HGFK1, 11th Annual Meeting of the American Society of Gene Therapy May 28-June 1, 2008; Boston, Massachusetts, USA.. 2008.

Wong K.F., Chiu Y.S., Lam T.W. and Yiu S.M., A Memory Efficient Algorithm for Structural Alignment of RNAs with Embedded Simple Pseudoknots, The 5th Asia-Pacific Bioinformatics Conference . World Scientific, 2008, 89-100.

Researcher : Yu CH

List of Research Outputs

Yu C.H., Lau F.C.M. and Wang C.L., Recycling Memory Blocks for Improving Execution of Java Programs, ACM Transactions on Architecture and Code Optimization. ACM, 2008, 4.

Researcher : Yuan W

List of Research Outputs

Lee S.D., Yee K.C., Cheung D.W.L. and Yuan W., Descriptive Schema: Semantics-based Query Answering, 3rd Semantic Wiki Workshop (SemWiki 2008). 2008.

Researcher : Yuk SC

List of Research Outputs

Yuk S.C., A Probabilistic Framework for Real-Time Head Shape Detection and Tracking. Hong Kong, 2008.

Yuk S.C., Wong K.K.Y., Chung H.Y., Chow K.P., Chin F.Y.L. and Tsang K.S.H., Object-Based Surveillance Video Retrieval System With Real-Time Indexing Methodology, International Conference on Image Analysis and Recognition. Montreal, Canada, 2007, 626-637.

Researcher : Zhang H

List of Research Outputs

Zhang H., Temporal subtraction of chest radiograph using graph cuts and free-form deformations. 2008.

Researcher : Zhang Y

List of Research Outputs

Chan W.T., Chin F.Y.L., Ye D., Zhang G. and Zhang Y., On-line scheduling of parallel jobs on two machines, Journal of Discrete Algorithms . Amsterdam, The Netherlands, Elsevier Science Publishers B. V., 2008, 6(1): 3-10.

Chin F.Y.L., Zhang Y. and Zhu H., A 1-local 13/9-competitive Algorithm for Multicoloring Hexagonal Graphs, The 13th Annual International Computing and Combinatorics Conference (COCOON 2007). Banff, Alberta, Canada, 2007, 526-536.

Researcher : Zhang Z

List of Research Outputs

Zhang Z., Chan W.K. and Tse T.H., Synthesizing component-based WSN applications via automatic combination of code optimization techniques, Proceedings of the 7th International Conference on Quality Software (QSIC 2007), IEEE Computer Society Press, Los Alamitos, CA. 2007, 181−190.

Researcher : Zheng D

List of Research Outputs

Wang W.P., Juttler B., Zheng D. and Liu Y., Computation of rotation minimizing frames, ACM Transactions on Graphics. 2008, 27, Issue 1.

-- End of Listing --