Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Ching Law

dblp:18/1056 · DBLP profile ↗
in reviewer pool ← Back
21ranked-venue papers
7as first author
13since 2021 · last 2026
0009-0001-3275-2528ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Databases, data management, data science and information retrieval · 12 · 1 first-author · 10 since 2021Artificial intelligence and machine learning · 5 · 1 first-author · 4 since 2021Computer networks · 5 · 5 first-authorGraphics, computer vision, multimedia, augmented reality and games · 3 · 3 since 2021Applied, interdisciplinary, general and emerging computing · 3 · 3 since 2021Theory of computation · 1 · 1 first-author

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Databases, data mining, and information retrieval
9 papers
Recommender systems · 61% Information retrieval · 34% Machine learning and data management · 2%
Artificial intelligence
5 papers
Generative modeling · 34% Reinforcement learning · 34% Optimization for machine learning · 15%
Computer graphics and multimedia
3 papers
Visual content generation and editing · 100%
Theoretical computer science
3 papers
Algorithmic game theory and mechanism design · 99% Approximation and online algorithms · 1% Graph algorithms and graph theory · 1%

Topics — the 30 heaviest of 41, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Recommender systems
generative recommendation
3.032026
A Generative Contextual Comprehension Paradigm for Takeout Ranking Model · WWW 2026
AIPO: Adaptive Anchored Intent-aware Policy Optimization for Generative Recommendation · SIGIR 2026
Reasoning-Grounded Intent Injection for Generative Recommendation · SIGIR 2026
Recommender systems
click-through rate prediction
1.922026
DPEO: Dynamic Preference Evolution Optimization for Self-Evolving CTR Prediction · SIGIR 2026
Post-event Modeling via Causal Optimal Transport for CTR Prediction · SIGIR 2025
Visual content generation and editing
layout generation
1.922026
AutoPP: Towards Automated Product Poster Generation and Optimization · AAAI 2026
Uni-Layout: Integrating Human Feedback in Unified Layout Generation and Evaluation · ACM Multimedia 2025
Machine learning › Generative modeling
diffusion model
1.012026
MoFu: Scale-Aware Modulation and Fourier Fusion for Multi-Subject Video Generation · AAAI 2026
Machine learning › Reinforcement learning
policy optimization
1.012026
AIPO: Adaptive Anchored Intent-aware Policy Optimization for Generative Recommendation · SIGIR 2026
Machine learning › Reinforcement learning › reward design
reward hacking mitigation
1.012026
AIPO: Adaptive Anchored Intent-aware Policy Optimization for Generative Recommendation · SIGIR 2026
Machine learning › Generative modeling › diffusion model
video diffusion model
1.012026
MoFu: Scale-Aware Modulation and Fourier Fusion for Multi-Subject Video Generation · AAAI 2026
Information retrieval › ranking
context-aware ranking
1.012026
A Generative Contextual Comprehension Paradigm for Takeout Ranking Model · WWW 2026
Recommender systems › interactive recommendation
conversational recommendation
1.012026
Think Then Recommend: An LLM-Powered Multi-Agent Framework for Personalized Conversational Recommender System in E-Commerce · WWW 2026
Information retrieval › ranking
ranking model
1.012026
A Generative Contextual Comprehension Paradigm for Takeout Ranking Model · WWW 2026
Visual content generation and editing
video generation
1.012026
MoFu: Scale-Aware Modulation and Fourier Fusion for Multi-Subject Video Generation · AAAI 2026
Algorithmic game theory and mechanism design › auction theory
advertising auctions
1.012026
Auto-bidding under Return-on-Spend Constraints with Uncertainty Quantification · WWW 2026
Algorithmic game theory and mechanism design › auction theory › bidding strategy
auto-bidding
1.012026
Auto-bidding under Return-on-Spend Constraints with Uncertainty Quantification · WWW 2026
Information retrieval
e-commerce search
0.912025
UniERF: A Uniform Embedding-based Retrieval Framework for E-commerce Search · KDD (2) 2025
Information retrieval › retrieval models › neural retrieval
embedding-based retrieval
0.912025
UniERF: A Uniform Embedding-based Retrieval Framework for E-commerce Search · KDD (2) 2025
Machine learning › Trustworthy machine learning › uncertainty estimation
conformal prediction
0.312026
Auto-bidding under Return-on-Spend Constraints with Uncertainty Quantification · WWW 2026
Machine learning › Kernel, tree and ensemble methods
ensemble learning
0.312026
DPEO: Dynamic Preference Evolution Optimization for Self-Evolving CTR Prediction · SIGIR 2026
Natural language and speech › Language models and text generation
large language model
0.312026
Think Then Recommend: An LLM-Powered Multi-Agent Framework for Personalized Conversational Recommender System in E-Commerce · WWW 2026
Machine learning › Reinforcement learning
policy diversity
0.312026
DPEO: Dynamic Preference Evolution Optimization for Self-Evolving CTR Prediction · SIGIR 2026
Machine learning › Generative modeling › video generation
text-to-video generation
0.312026
MoFu: Scale-Aware Modulation and Fourier Fusion for Multi-Subject Video Generation · AAAI 2026
Machine learning › Trustworthy machine learning
uncertainty estimation
0.312026
Auto-bidding under Return-on-Spend Constraints with Uncertainty Quantification · WWW 2026
Recommender systems
click-through rate optimization
0.312026
AutoPP: Towards Automated Product Poster Generation and Optimization · AAAI 2026
Machine learning and data management
distribution shift
0.312026
AIPO: Adaptive Anchored Intent-aware Policy Optimization for Generative Recommendation · SIGIR 2026
Recommender systems › generative recommendation
semantic ID
0.312026
Reasoning-Grounded Intent Injection for Generative Recommendation · SIGIR 2026
Information retrieval › similarity search › nearest neighbor search
approximate nearest neighbor search
0.312025
UniERF: A Uniform Embedding-based Retrieval Framework for E-commerce Search · KDD (2) 2025
Data mining
causal inference
0.312025
Post-event Modeling via Causal Optimal Transport for CTR Prediction · SIGIR 2025
Information retrieval › online advertising
ad targeting
0.212016
Profiling Users from Online Social Behaviors with Applications for Tencent Social Ads · KDD 2016
Recommender systems
user profiling
0.212016
Profiling Users from Online Social Behaviors with Applications for Tencent Social Ads · KDD 2016
Web and social media mining
social network analysis
0.112016
Profiling Users from Online Social Behaviors with Applications for Tencent Social Ads · KDD 2016
Distributed systems
distributed algorithms
0.012003
Distributed Construction of Random Expander Networks · INFOCOM 2003

Methods — techniques the papers use, named apart from their topics

scale-aware modulation · 2.0role arbitration · 2.0prior anchoring · 2.0machine learning · 2.0intent-aware resampling · 2.0fast fourier transform · 2.0element rendering · 2.0direct preference optimization · 2.0conformal prediction · 2.0barrier mapping · 2.0asymmetric gradient flow · 2.0LLM-guided feature modulation · 2.0reinforcement learning · 1.0low-rank adaptation · 1.0large language model distillation · 1.0generative model · 1.0GRPO · 1.0layout evaluation · 0.9
YearPublicationVenuePosition
2026 AutoPP: Towards Automated Product Poster Generation and Optimization
abstract
Product posters blend striking visuals with informative text to highlight the product and capture customer attention. However, crafting appealing posters and manually optimizing them based on online performance is laborious and resource-consuming. To address this, we introduce AutoPP, an automated pipeline for product poster generation and optimization that eliminates the need for human intervention. Specifically, the generator, relying solely on basic product information, first uses a unified design module to integrate the three key elements of a poster (background, text, and layout) into a cohesive output. Then, an element rendering module encodes these elements into condition tokens, efficiently and controllably generating the product poster. Based on the generated poster, the optimizer enhances its Click-Through Rate (CTR) by leveraging online feedback. It systematically replaces elements to gather fine-grained CTR comparisons and utilizes Isolated Direct Preference Optimization (IDPO) to attribute CTR gains to isolated elements. Our work is supported by AutoPP1M, the largest dataset specifically designed for product poster generation and optimization, which contains one million high-quality posters and feedback collected from over one million users. Experiments demonstrate that AutoPP achieves state-of-the-art results in both offline and online settings.
Yuxin Qin, Yanyin Chen, Yixiu Li, Li Zhuang, Haoyi Bian, Jingjing Lv, Ching Law
AAAI13
2026 MoFu: Scale-Aware Modulation and Fourier Fusion for Multi-Subject Video Generation
abstract
Multi-subject video generation aims to synthesize videos from textual prompts and multiple reference images, ensuring that each subject preserves natural scale and visual fidelity. However, current methods face two challenges: scale inconsistency, where variations in subject size lead to unnatural generation, and permutation sensitivity, where the order of reference inputs causes subject distortion. In this paper, we propose MoFu, a unified framework that tackles both challenges. For scale inconsistency, we introduce Scale-Aware Modulation (SMO), an LLM-guided module that extracts implicit scale cues from the prompt and modulates features to ensure consistent subject sizes. To address permutation sensitivity, we present a simple yet effective Fourier Fusion strategy that processes the frequency information of reference features via the Fast Fourier Transform to produce a unified representation. Besides, we design a Scale-Permutation Stability Loss to jointly encourage scale-consistent and permutation-invariant generation. To further evaluate these challenges, we establish a dedicated benchmark with controlled variations in subject scale and reference permutation. Extensive experiments demonstrate that MoFu significantly outperforms existing methods in preserving natural scale, subject fidelity, and overall visual quality.
Run Ling, Ke Cao 0001, Ao Ma 0005, Runze He, Changwei Wang 0001, Rongtao Xu, Yihua Shao, Zhanjie Zhang, Guibing Guo, Jingjing Lv, Junjie Shen 0008, Ching Law, Xingwei Wang 0001
AAAI17
2026 Reasoning-Grounded Intent Injection for Generative Recommendation
abstract
Industrial generative recommendation systems operating over discrete Semantic IDs (SIDs) are largely behavior-driven, and thus struggle to proactively activate latent demand before explicit user signals emerge, leading to intent cold-start. To address this, we propose RIGER (Reasoning-grounded Intent injection for GE nerative Recommendation), a deployable two-stage framework that integrates offline large language model (LLM) reasoning into an online generative recommender under strict latency constraints. Offline, to ensure scalable deployment, we distill the latent-intent inference capability of a strong LLM into a lightweight forecasting model using an automated data curation pipeline---leveraging judge-guided prompt calibration and future-query-guided rejection filtering. Online, to bridge the representation mismatch between free-form textual intents and the discrete SID token space, predicted intents are converted into SID-native tokens through a behavior-grounded mapping and injected into the deployed decoder-only retrieval backbone. We further fine-tune the model with beam-aware GRPO, introducing a hierarchical intent-alignment exploration reward in SID space while preserving exploitation behavior through KL regularization. Offline evaluations demonstrate a substantial increase in intent-aligned density and diversity with only a marginal reduction in hindsight recall, indicating that RIGER effectively enhances proactive intent exploration while preserving its capability to exploit historical behaviors. In a large-scale e-commerce display advertising system, RIGER improves clicks by 1.6% and advertiser spend by 1.3%.
Xusong Chen, Peini Guo, Yiyang Hu, Mengqin Que, Zhiwei Fang, Changping Peng, Ching Law
SIGIR12
2026 DPEO: Dynamic Preference Evolution Optimization for Self-Evolving CTR Prediction
abstract
Click-through rate (CTR) prediction is a pivotal component in large-scale industrial systems. Historically, CTR prediction paradigms have been confined to monolithic architectures governed by a single-policy optimization process. However, such isolated learning paths lack the intrinsic evolutionary mechanisms necessary for optimal convergence. Without policy diversity and internal competition, models tend to get trapped in local optima as performance reaches saturation, hindering further breakthroughs in modeling capacity. In this paper, we propose DPEO (Dynamic Preference Evolution Optimization), a co-evolutionary framework that transforms CTR modeling into a dynamic policy contention task. DPEO decouples the monolithic architecture into dual sub-learners to induce policy diversity, constructing an internal preference landscape without external rewards. A performance-driven Role Arbiter then dynamically designates the superior sub-learner as the Reference Policy and the other sub-learner as the Target Policy per batch, driving continuous model evolution. Through an asymmetric gradient flow, the target policy is optimized to surpass the reference policy in both probability and logit spaces. This process drives a co-evolution, enabling the sub-learners to serve as alternating evolutionary benchmarks and 'self-evolve' toward the global optimum. Extensive experiments on public benchmarks and a massive industrial dataset with over 10 billion samples demonstrate that DPEO significantly outperforms state-of-the-art models.
Ziheng Ni, Changping Peng, Ching Law
SIGIR6
2026 AIPO: Adaptive Anchored Intent-aware Policy Optimization for Generative Recommendation
abstract
Generative Recommendation (GenRec) has emerged as a significant evolutionary direction in the field of recommendation systems in recent years. However, during the reinforcement learning (RL) alignment stage of end-to-end GenRec, a core challenge is that the low signal-to-noise ratio (SNR) of feedback signals triggers reward hacking, which in turn leads to severe distributional drift. Massive click noise and sparse rewards result in highly unstable policy gradients, making it difficult to balance reward optimization and generative stability. To address this, we propose AIPO (Adaptive Anchored Intent-aware Policy Optimization) framework. AIPO synergistically enhances both optimization stability and performance from both data and prior anchoring perspectives. First, it introduces an intent-aware asymmetric resampling mechanism to purify high-confidence conversion intent data, thereby amplifying the gradient contribution of high-value paths. Second, it introduces a prior anchoring mechanism, which dynamically regulates its intensity through a barrier mapping based on the degree of policy distributional drift, mitigating distributional drift and reward hacking caused by low-SNR data. Offline experiments on both public benchmarks and JD's industrial datasets validated the superior performance of AIPO.
Ziheng Ni, Cai Shang, Changping Peng, Ching Law
SIGIR7
2026 Auto-bidding under Return-on-Spend Constraints with Uncertainty Quantification
abstract
Auto-bidding systems are widely used in advertising to automatically determine bid values under constraints such as total budget and Return-on-Spend (RoS) targets. Existing works often assume that the value of an ad impression, such as the conversion rate, is known. This paper considers the more realistic scenario where the true value is unknown. We propose a novel method that uses conformal prediction to quantify the uncertainty of these values based on machine learning methods trained on historical bidding data with contextual features, without assuming the data are i.i.d. This approach is compatible with current industry systems that use machine learning to predict values. Building on prediction intervals, we introduce an adjusted value estimator derived from machine learning predictions, and show that it provides performance guarantees without requiring knowledge of the true value. We apply this method to enhance existing auto-bidding algorithms with budget and RoS constraints, and establish theoretical guarantees for achieving high reward while keeping RoS violations low. Empirical results on both simulated and real-world industrial datasets demonstrate that our approach improves performance while maintaining computational efficiency.
Jiale Han 0002, Chun Gan, Jie He 0005, Zhangang Lin, Ching Law, Xiaowu Dai
WWW6
2026 A Generative Contextual Comprehension Paradigm for Takeout Ranking Model
abstract
The ranking stage serves as the central optimization and allocation hub in advertising systems, governing economic value distribution through eCPM and orchestrating the user-centric blending of organic and advertising content. Prevailing ranking models often rely on fragmented modules and hand-crafted features, limiting their ability to interpret complex user intent. This challenge is further amplified in location-based services such as food delivery, where user decisions are shaped by dynamic spatial, temporal, and individual contexts. To address these limitations, we propose a novel generative framework that reframes ranking as a context comprehension task, modeling heterogeneous signals in a unified architecture. Our architecture consists of two core components: the Generative Contextual Encoder (GCE) and the Generative Contextual Fusion (GCF). The GCE comprises three specialized modules: a Personalized Context Enhancer (PCE) for user-specific modeling, a Collective Context Enhancer (CCE) for group-level patterns, and a Dynamic Context Enhancer (DCE) for real-time situational adaptation. The GCF module then seamlessly integrates these contextual representations through low-rank adaptation. Extensive experiments confirm that our method achieves significant gains in critical business metrics, including click-through rate and platform revenue. We have successfully deployed our method on a large-scale food delivery advertising platform, demonstrating its substantial practical impact. This work pioneers a new perspective on generative recommendation and highlights its practical potential in industrial advertising systems.
Ziheng Ni, Cai Shang, Zhiwei Fang, Guangpeng Chen, Li Jian, Zehua Zhang 0005, Changping Peng, Zhangang Lin, Ching Law, Jingping Shao
WWW12
2026 Think Then Recommend: An LLM-Powered Multi-Agent Framework for Personalized Conversational Recommender System in E-Commerce
Yuankun Zu, Chuchu Yu, Jia Duan, Long Chen 0029, Kunyao Wang, Zehua Zhang 0005, Changping Peng, Zhangang Lin, Ching Law
WWW11
2025 SMTIR: Scenario-Aware Multi-Trigger Induction Network for CTR Prediction
abstract
Trigger-Induced Recommendation (TIR), which aims to predict user interest based on a trigger item, has gained considerable traction on e-commerce platforms. Current TIR methods typically analyze user intent by integrating explicit interest in the trigger item and implicit interest derived from user historical behaviors. However, these methods often overlook the contextual information and occurring scenarios related to the trigger, resulting in an undue emphasis on isolated trigger items and a consequently restrictive understanding of users' short-term intentions. To address these challenges, we propose a novel scenario-aware multi-trigger induction method featuring three key enhancements: (1) The Context Modeling Network learns contextual information associated with the trigger during the request, improving the understanding of users' real intentions regarding the trigger item; (2) The Multi-Trigger Learning Network introduces user latent triggers from various scenarios to uncover users' potential external preferences; (3) The Scenario Induction Network captures the characteristics of the scenarios in which triggers occur and performs induction to yield scenario-aware user intentions prediction. We validate our approach through experiments on multiple industrial datasets, demonstrating the model's effectiveness. Furthermore, we have integrated the model into an online advertising system, achieving a 5.46% improvement in Click-Through Rate (CTR).
Jia Duan, Zhanhao Ye, Kunyao Wang, Long Chen 0029, Zehua Zhang 0005, Changping Peng, Zhangang Lin, Ching Law
CIKM12
2025 UniERF: A Uniform Embedding-based Retrieval Framework for E-commerce Search
abstract
E-commerce has become an integral part of daily life, and the ability to effectively retrieve items relevant to a user's query is crucial for enhancing the shopping experience. Embedding-based retrieval (EBR) has proven to be an effective approach in industrial e-commerce search systems. This method involves training models to generate high-quality representations of queries and items, followed by the use of efficient approximate nearest neighbor (ANN) search techniques to find relevant items. However, current EBR methods face several critical limitations: (1) multiple EBR branches often retrieve overlapping or redundant result sets; (2) allocation and utilization of computational resources remain suboptimal, hindering performance; (3) the differentiation modeling of features is somewhat neglected, which restricts the system's ability to retrieve diverse and representative results. These issues hinder the retrieval performance of online search systems. In this paper, we introduce a novel e-commerce search framework called the Uniform Embedding-based Retrieval Framework (UniERF). This framework is meticulously designed to incorporate diverse samples for joint model training, enabling the model to effectively leverage both the semantic information of queries and the personalized features of different users. Extensive offline and online experiments demonstrate that UniERF surpasses baseline methods across various evaluation metrics. UniERF has been successfully implemented in the existing retrieval system at JD.COM, a renowned online shopping website.
Hao Jiang 0051, Fanyi Qu, Changping Peng, Zhangang Lin, Ching Law, Jingping Shao
KDD (2)8
2025 Uni-Layout: Integrating Human Feedback in Unified Layout Generation and Evaluation
Shuo Lu, Yanyin Chen, Fengheng Li, Jingjing Lv, Junjie Shen 0008, Ching Law, Jian Liang 0001
ACM Multimedia9
2025 Stream Normalization for CTR Prediction
Yizhou Sang, Yuying Chen, Zhiwei Fang, Changping Peng, Zhangang Lin, Ching Law, Jingping Shao
RecSys8
2025 Post-event Modeling via Causal Optimal Transport for CTR Prediction
abstract
Accurate click-through rate (CTR) prediction is critical for online advertising, relying on regular features like browsing history and demographics and post-event features such as exposed position and detailed page behaviors. However, post-event features, unavailable during inference, often face training-inference inconsistency and low coverage issues, especially post-click features like dwell time that are available only for clicked items. To address these challenges, we propose Causal Optimal Transport (COT), a novel framework that (1) generates pseudo post-click features via semi-supervised pseudo-labeling (2) causally generates accurate feature distributions using a Causal Distribution Shaper (CDS), and (3) refines generated features through optimal transport to minimize distributional divergence, facilitating further knowledge transfer. Experiments on real-world data confirm COT's superiority and practical efficacy in enhancing CTR prediction via improved user interest modeling and bias mitigation. Theoretical guarantees underpin the framework's robustness.
Yizhou Sang, Yuying Chen, Zhiwei Fang, Changping Peng, Zhangang Lin, Ching Law, Jingping Shao
SIGIR8
2016 Profiling Users from Online Social Behaviors with Applications for Tencent Social Ads
abstract
QQ and Wechat are the two largest instant messaging & social networks in China. Tencent Social Ads is the advertising platform for both Wechat and QQ, serving over 10B page views per day for several hundred million users. We strive to understand as much as possible on our users' characteristics, so as to serve the best personalized ads for them. The rich user behaviors on Tencent's diverse products lay a foundation in our user profiles on many dimensions, including demographics, interests, intents, transactions, physical locations, and devices, etc. In this talk, we will share our experience in large scale user data mining based on online social activities. We will discuss the challenges we face and the solutions we have devised so far. Some demographics data are obtained from user input, and thus would have gaps in both accuracy and coverage. We discuss the techniques in calibrating and verifying these data. We infer user interests from their social behaviors. For example, most QQ groups are not labelled properly, but by applying a large-scale topic model on the QQ memberships, we can effectively classify most QQ groups into an interest taxonomy. We also infer user interests from user's physical location check-ins and uploaded photos. User data can be collected from many diverse sources, including behaviors in various Tencent products, click and conversion in ad platform, and even seed customers collected by advertisers. We'll discuss the systems to merge these diverse data to provide a coherent view for our advertisers. High quality user labels are usually sparse. We implemented an algorithm for advertisers to reach more potential customers through user similarity computation based on user features as well as social graph inferences. We'll describe the system's contributions to ads quality. Top advertisers demand rich audience targeting solutions in combination of their own customer data, Tencent data, and possibly 3rd-party data. We'll discuss the data exchange platform that can facilitate collaborative applications with 3rd-party DSPs and DMPs.
Ching Law
KDD1
2015 Peacock: Learning Long-Tail Topic Features for Industrial Applications
abstract
Latent Dirichlet allocation (LDA) is a popular topic modeling technique in academia but less so in industry, especially in large-scale applications involving search engine and online advertising systems. A main underlying reason is that the topic models used have been too small in scale to be useful; for example, some of the largest LDA models reported in literature have up to 10 3 topics, which difficultly cover the long-tail semantic word sets. In this article, we show that the number of topics is a key factor that can significantly boost the utility of topic-modeling systems. In particular, we show that a “big” LDA model with at least 10 5 topics inferred from 10 9 search queries can achieve a significant improvement on industrial search engine and online advertising systems, both of which serve hundreds of millions of users. We develop a novel distributed system called Peacock to learn big LDA models from big data. The main features of Peacock include hierarchical distributed architecture, real-time prediction, and topic de-duplication. We empirically demonstrate that the Peacock system is capable of providing significant benefits via highly scalable LDA topic models for several industrial applications.
Xuemin Zhao, Zhenlong Sun, Zhihui Jin, Liubin Wang, Yang Gao 0026, Ching Law
ACM Trans. Intell. Syst. Technol.9
2003 Distributed Construction of Random Expander Networks
abstract
A novel distributed algorithm for constructing random overlay networks that are composed of d Hamilton cycles is presented. The protocol is completely decentralized as no globally-known server is required. The constructed topologies are expanders with O(log/sub d/ n) diameter with high probability. Our construction is highly scalable because both the processing and the space requirements at each node grow logarithmically with the network size. A new node can join the network in O(log/sub d/ n) time with O(d log/sub d/ n) messages. A node can leave in O(1) time with O(d) messages. The protocol is robust against an offline adversary selecting the sequence of the join and leave operations. We also discuss a layered construction of the random expander networks in which any node can be located in O(log n) time. The random expander networks have applications in community discovery, distributed lookup service, and dynamic connectivity.
Ching Law, Kai-Yeung Siu
INFOCOM1
2003 A New Bluetooth Scatternet Formation Protocol
Ching Law, Amar K. Mehta, Kai-Yeung Siu
Mob. Networks Appl.1
2001 A Bluetooth scatternet formation algorithm
abstract
A Bluetooth ad hoc network can be formed by interconnecting piconets into scatternets. The constraints and properties of Bluetooth scatternets present special challenges in forming an ad hoc network efficiently. We present and analyse a new randomized distributed algorithm for Bluetooth scatternet formation. We prove that our algorithm achieves O(log n) time complexity and O(n) message complexity. We show that: (1) in the scatternet formed by our algorithm, any device is a member of at most two piconets; (2) the number of piconets is close to being minimal.
Ching Law, Kai-Yeung Siu
GLOBECOM1
2001 Performance of a new Bluetooth scatternet formation protocol
abstract
A Bluetooth ad hoc network can be formed by interconnecting piconets into scatternets. The constraints and properties of Bluetooth scatternets present special challegnes in forming an ad hoc network efficiently. In this paper, we evaluate the performance of a new randomized distributed Bluetooth scatternet formation protocol. Our simulations validate the theoretical results that our scatternet formation protocol runs in O(log n) time and sends O(n) messages. The scatternets formed have the following properties: 1) any device is a member of at most two piconets, and 2) the number of piconets is close to be optimal. These properties can avoid overloading of any single device and lead to low interference between piconets. In addition, the simulations show that the scatternets formed have O(log n) diameter. As an essential part of the scatternet formation protocol, we study the problem of device discovery: establishing multiple connecitons with many masters and slaves in parallel. We investigate the collision rate and time requirement of the inquiry and page processes. Deducing from the simulation results of scatternet formation and device discovery, we can verify that the total number of packets sent is O(n) and demonstrate that the maximum number of packets sent by any single device is O(log n). At last, we give estimates of the total time requirement of the protocol and suggest further improvements
Ching Law, Amar K. Mehta, Kai-Yeung Siu
MobiHoc1
2000 A New Competitive Analysis of Randomized Caching
Ching Law, Charles E. Leiserson
ISAAC1
2000 Online routing and wavelength assignment in single-hub WDM rings
abstract
We present new theoretical results on the performance limits of online routing and wavelength assignment (RWA) algorithms in a single-hub wavelength division multiplexing (WDM) ring network architecture. A routing and wavelength assignment (RWA) algorithm is said to be online if at each point in time, the algorithm assigns a route and a color to the current connection request based only on past information, without knowledge of future requests. We study the throughput performance of deterministic online RWA algorithms in terms of competitive ratio, i.e., the maximum ratio of the throughput of an optimal off-line algorithm to that of an online algorithm over any satisfiable sequence of requests. We show that the competitive ratio for the min-hop algorithm is exactly 2. When there are sufficient wavelengths, smaller competitive ratio W/(W+1-N) can be achieved by the greedy-complete algorithm for infinite-duration requests, and by the pair-complete algorithm for uniform-duration requests, where W is the number of wavelengths and N is the number of nodes. In the general case where requests can have arbitrary durations, we prove that a natural deterministic online algorithm can achieve a competitive ratio of 1+2g, where g>1 is the ratio of the longest duration of any request to the shortest duration of any request. These results exhibit the performance tradeoffs among the number of nodes, the number of wavelengths, and the range of request durations.
Ching Law, Kai-Yeung Siu
IEEE J. Sel. Areas Commun.1