Search For:

Displaying 1-19 out of 19 total
Nonmigratory Multiprocessor Scheduling for Response Time and Energy
Found in: IEEE Transactions on Parallel and Distributed Systems
By Tak-Wah Lam, Lap-Kei Lee, Isaac K.K. To, Prudence W.H. Wong
Issue Date:November 2008
pp. 1527-1539
Energy usage has been an important concern in recent research on online job scheduling, where processors are allowed to vary the speed dynamically so as to save energy whenever possible. Notice that providing good quality of service such as response time (...
 
Compressed Index for Dictionary Matching
Found in: Data Compression Conference
By Wing-Kai Hon, Tak-Wah Lam, Rahul Shah, Siu-Lung Tam, Jeffrey Scott Vitter
Issue Date:March 2008
pp. 23-32
The past few years have witnessed several exciting results on compressed representation of a string T that supports efficient pattern matching, and the space complexity has been reduced to |T|H_k(T) + o(|T| log s) bits, where H_k(T) denotes the kth-order e...
 
Compressed Index for Dynamic Text
Found in: Data Compression Conference
By Wing-Kai Hon, Tak-Wah Lam, Kunihiko Sadakane, Wing-Kin Sung, Siu-Ming Yiu
Issue Date:March 2004
pp. 102
This paper investigates how to index a text which is subject to updates. The best solution in the literature is based on suffix tree using O(n log n) bits of storage, where n is the length of the text. It supports finding all occurrences of a pattern P in ...
 
A 5-Competitive On-line Scheduler for Merging Video Streams
Found in: Parallel and Distributed Processing Symposium, International
By Wun-Tat Chan, Tak-Wah Lam, Hin-Fung Ting, Wai-Ha Wong
Issue Date:April 2001
pp. 30201b
We study an on-line scheduling problem arising from video-on-demand(VOD)systems that support stream merging. A VOD system often receives many requests for a hot video over a short period of time (say, Friday 7 pm to 9 pm). If the video server uses a dedica...
 
On the Speed Requirement for Optimal Deadline Scheduling in Overloaded Systems
Found in: Parallel and Distributed Processing Symposium, International
By Tak-Wah Lam, Tsuen-Wan Ngan, Kar-Keung To
Issue Date:April 2001
pp. 30202
We consider the problem of scheduling jobs with deadlines in an on-line single-processor system. It is known for long that unless the system is underloaded, any on-line algorithm is not optimal in the sense that it may fail to match the optimal offline alg...
 
Predicting RNA Secondary Structures with Arbitrary Pseudoknots by Maximizing the Number of Stacking Pairs
Found in: Bioinformatic and Bioengineering, IEEE International Symposium on
By Samuel Ieong, Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung, Siu-Ming Yiu
Issue Date:March 2001
pp. 183
In this paper we investigate the computational problem of predicting RNA secondary structures that allow any kinds of pseudoknots. The general belief is that allowing pseudoknots makes the problem very difficult. Existing polynomial-time algorithms, which ...
 
Construction of Online Catalog Topologies Using Decision Trees
Found in: Advanced Issues of E-Commerce and Web-Based Information Systems, International Workshop on
By David Yang, Wing-kin Sung, Siu-Ming Yiu, David Cheung, Wai-Shing Ho, Tak-Wah Lam, Sau-Dan Lee
Issue Date:June 2000
pp. 223
Organization of a web site is important to help users get the most out of the site. A good web site should help visitor's _nd the information they want easily. Visitors typically find information by searching for selected terms of interest or by following ...
 
Nonclairvoyant sleep management and flow-time scheduling on multiple processors
Found in: Proceedings of the 25th ACM symposium on Parallelism in algorithms and architectures (SPAA '13)
By Jianqiao Zhu, Lap-Kei Lee, Sze-Hang Chan, Tak-Wah Lam
Issue Date:July 2013
pp. 261-270
In large data centers, managing the availability of servers is often non-trivial, especially when the workload is unpredictable. Using too many servers would waste energy, while using too few would affect the performance. A recent theoretical study, which ...
     
Non-clairvoyant weighted flow time scheduling with rejection penalty
Found in: Proceedinbgs of the 24th ACM symposium on Parallelism in algorithms and architectures (SPAA '12)
By Ho-Leung Chan, Jianqiao Zhu, Lap-Kei Lee, Sze-Hang Chan, Tak-Wah Lam
Issue Date:June 2012
pp. 246-254
This paper initiates the study of online scheduling with rejection penalty in the non-clairvoyant setting, i.e., the size (processing time) of a job is not assumed to be known at its release time. In the rejection penalty model, jobs can be rejected with a...
     
Optimizing throughput and energy in online deadline scheduling
Found in: ACM Transactions on Algorithms (TALG)
By Ho-Leung Chan, Joseph Wun-Tat Chan, Kin-Sum Mak, Lap-Kei Lee, Prudence W. H. Wong, Tak-Wah Lam
Issue Date:December 2009
pp. 1-22
This article extends the study of online algorithms for energy-efficient deadline scheduling to the overloaded setting. Specifically, we consider a processor that can vary its speed between 0 and a maximum speed T to minimize its energy usage (the rate is ...
     
Competitive non-migratory scheduling for flow time and energy
Found in: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures (SPAA '08)
By Isaac K. K. To, Lap-Kei Lee, Prudence W. H. Wong, Tak-Wah Lam
Issue Date:June 2008
pp. 13-14
Energy usage has been an important concern in recent research on online scheduling. In this paper we extend the study of the tradeoff between flow time and energy from the single-processor setting [8, 6] to the multi-processor setting. Our main result is a...
     
Compressed indexes for dynamic text collections
Found in: ACM Transactions on Algorithms (TALG)
By Ho-Leung Chan, Kunihiko Sadakane, Tak-Wah Lam, Wing-Kai Hon
Issue Date:May 2007
pp. 21-es
Let T be a string with n characters over an alphabet of constant size. A recent breakthrough on compressed indexing allows us to build an index for T in optimal space (i.e., O(n) bits), while supporting very efficient pattern matching [Ferragina and Manzin...
     
Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling
Found in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (SODA '06)
By Ho-Leung Chan, Kin-Shing Liu, Tak-Wah Lam
Issue Date:January 2006
pp. 334-343
We study online scheduling of jobs to minimize the flow time and stretch on parallel machines. We consider algorithms that are given extra resources so as to compensate the lack of future information. Recent results show that a modest increase in machine s...
     
Extra processors versus future information in optimal deadline scheduling
Found in: Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures (SPAA '02)
By Chiu-Yuen Koo, Kar-Keung To, Tak-Wah Lam, Tsuen-Wan Ngan
Issue Date:August 2002
pp. 133-142
This paper is concerned with the extra-resource analysis of online scheduling algorithms. In particular, it studies how to make use of multiple processors to counteract the lack of future information in online deadline scheduling. Our results extend the pr...
     
A unified analysis of hot video schedulers
Found in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (STOC '02)
By Hing-Fung Ting, Tak-Wah Lam, Wai-Ha Wong, Wun-Tat Chan
Issue Date:May 2002
pp. 179-188
In this paper we consider the notion of relative competitive analysis, which is a simple generalization of the conventional competitive analysis and extra-resource analysis for on-line algorithms. We apply this analysis to study on-line schedulers for stre...
     
Requirement-based data cube schema design
Found in: Proceedings of the eighth international conference on Information and knowledge management (CIKM '99)
By Ben Kao, Bo Zhou, David W. Cheung, Hing Fung Ting, Hongjun Lu, Tak Wah Lam
Issue Date:November 1999
pp. 162-169
On-line analytical processing (OLAP) requires efficient processing of complex decision support queries over very large databases. It is well accepted that pre-computed data cubes can help reduce the response time of such queries dramatically. A very import...
     
General techniques for comparing unrooted evolutionary trees
Found in: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (STOC '97)
By Hing-Fung Ting, Ming-Yang Kao, Tak-Wah Lam, Teresa M. Przytycka, Wing-Kin Sung
Issue Date:May 1997
pp. 54-65
We present efficient new randomized and deterministic methods for transforming optimal solutions for a type of relaxed integer linear program into provably good solutions for the corresponding NP-hard discrete optimization problem. Without any constraint v...
     
Approximating biconnectivity in parallel
Found in: Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures (SPAA '95)
By Ka Wong Chong, Tak Wah Lam
Issue Date:June 1995
pp. 224-233
We present efficient algorithms for two all-to-all communication operations in message-passing systems: index (or all-to-all personalized communication) and concatenation (or all-to-all broadcast). We assume a model of a fully-connected message-passing sys...
     
Concurrent threads and optimal parallel minimum spanning trees algorithm
Found in: Journal of the ACM (JACM)
By Ka Wong Chong, Tak Wah Lam, Yijie Han
Issue Date:January 1988
pp. 297-323
This paper resolves a long-standing open problem on whether the concurrent write capability of parallel random access machine (PRAM) is essential for solving fundamental graph problems like connected components and minimum spanning trees in O(logn) time. S...
     
 1