检索结果-内蒙古大学图书馆

pliable index coding via Conflict-Free Colorings of Hypergraphs

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第6期70卷 3903-3921页

作者： Krishnan, Prasad Mathew, Rogers Kalyanasundaram, Subrahmanyam Int Inst Informat Technol Hyderabad Signal Proc & Commun Res Ctr Hyderabad 500032 India Indian Inst Technol Hyderabad Dept Comp Sci & Engn Hyderabad 502205 India

We present a hypergraph coloring based approach to pliable index coding (PICOD). We represent the given PICOD problem using a hypergraph consisting of m messages as vertices and the request-sets of the n clients as hyperedges. A conflict-free coloring of a hypergraph is an assignment of colors to its vertices so that each hyperedge contains a uniquely colored vertex. We show that various parameters arising out of conflict-free colorings (and some new variants) of the PICOD hypergraph result in new upper bounds for the optimal PICOD length. Using these new upper bounds, we show the existence of single-request PICOD schemes with length O(log(2 )Gamma) , where Gamma is the maximum number of hyperedges overlapping with any hyperedge. For the t -request PICOD scenario, we show the existence of PICOD schemes of length max(O(log Gamma log m),O(t log m)) , under some mild conditions on the graph parameters. These results improve upon earlier work in general. We also show that our achievable lengths in the t -request case are asymptotically optimal, up to a multiplicative factor of log t . Our existence results are accompanied by randomized constructive algorithms, which have complexity polynomial in the parameters of the PICOD problem, in expectation or with high probability.

关键词： indexes Encoding Codes Receivers Upper bound Servers Symbols index coding pliable index coding conflict-free coloring hypergraph coloring

来源：评论

学校读者我要写书评

暂无评论

pliable index coding with Restricted Decoding Sets

Pliable Index Coding with Restricted Decoding Sets

引用

2024 Information Theory Workshop

作者： Wu, Junping Ong, Lawrence Johnson, Sarah Tan, Jin Yeong Univ Newcastle Newcastle NSW Australia

ISBN: (纸本)9798350348941;9798350348934

pliable index coding studies flexible communication networks where each receiver just needs to receive any message that it does not already have. In this work, we consider a more practical but restricted scenario where each receiver wants any message it does not have from a particular subset of messages. We first adapt coding schemes from pliable index coding to this new restricted pliable index coding setting. We show that the adapted scheme is optimal under certain conditions. We simplify the computational complexity when constructing coding schemes for restricted pliable index coding from exponential to linear. We also construct two new coding schemes for the restricted setting, which can outperform the adapted scheme.

关键词： index coding pliable index coding restricted pliable index coding

来源：评论

学校读者我要写书评

暂无评论

Sparse and Low-Rank Optimization for pliable index coding via Alternating Projection

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2022年第6期70卷 3708-3724页

作者： Fu, Min Jiang, Tao Choi, Hayoung Zhou, Yong Shi, Yuanming ShanghaiTech Univ Sch Informat Sci & Technol Shanghai 201210 Peoples R China Chinese Acad Sci Shanghai Inst Microsyst & Informat Technol Shanghai 200050 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China Univ Toronto Edward S Rogers Sr Dept Elect & Comp Engn Toronto ON M5S 3G4 Canada Kyungpook Natl Univ Dept Math Daegu 41566 South Korea Yoke Intelligence Shanghai 201210 Peoples R China

pliable index coding (PICOD) has recently been regarded as a promising solution that exploits the coding advantage to improve communication efficiency of content-type systems (e.g., recommendation system), where clients are pliable and are interested in receiving any new message that they do not have. PICOD aims to find an effective coding strategy that satisfies the demands of all clients with the minimum number of transmissions. However, most of the previous works mainly provided theoretical understanding on PICOD in special instances based on greedy algorithms. In contrast, in this paper, we present a flexible sparse and low-rank matrix modeling approach to minimize the number of transmissions for the general PICOD problems. This is achieved by establishing generalized pliable alignment conditions to guarantee the requirements of all clients. As the resulting non-convex problem is highly intractable, we further develop an alternating pursuit framework to detect the rank of the matrix to be recovered by using the rank-increasing strategy. To address the feasibility-detection issues in the existing methods, we propose an alternating projection algorithm, which admits closed-form expressions and avoids excessive sparsity inducing. Moreover, we establish the global convergence of the alternating projection algorithm with random initial points. Simulation results demonstrate that the proposed alternating pursuit algorithm significantly reduces the number of transmissions compared to the state-of-the-art methods.

关键词： Encoding indexes Sparse matrices Servers Optimization Minimization Decoding pliable index coding sparse and low-rank optimization alternating projection method

来源：评论

学校读者我要写书评

暂无评论

A pliable index coding Approach to Data Shuffling

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2020年第3期66卷 1333-1353页

作者： Song, Linqi Fragouli, Christina Zhao, Tianchu Univ Calif Los Angeles Dept Elect & Comp Engn Los Angeles CA 90095 USA City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Tsinghua Univ Dept Elect Engn Beijing 100084 Peoples R China

A promising research area that has recently emerged, is on how to use index coding to improve the communication efficiency in distributed computing systems, especially for data shuffling in iterative computations. In this paper, we posit that pliable index coding can offer a more efficient framework for data shuffling, as it can better leverage the many possible shuffling choices to reduce the number of transmissions. We theoretically analyze pliable index coding under data shuffling constraints, and design a hierarchical data-shuffling scheme that uses pliable coding as a component. We find benefits up to $O(ns/m)$ over index coding, where $ns/m$ is the average number of workers caching a message, and $m$ , $n$ , and $s$ are the numbers of messages, workers, and cache size, respectively.

关键词： pliable index coding data shuffling distributed computing random graph coded computing

来源：评论

学校读者我要写书评

暂无评论

A Polynomial-Time Algorithm for pliable index coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2018年第2期64卷 979-999页

作者： Song, Linqi Fragouli, Christina Univ Calif Los Angeles Dept Elect Engn Los Angeles CA 90095 USA

In pliable index coding, we consider a server with m messages and n clients, where each client has as side information a subset of the messages. We seek to minimize the number of broadcast transmissions, so that each client can recover any one unknown message she does not already have. Previous work has shown that the pliable index coding problem is NP-hard and requires at most O(log(2)(n)) broadcast transmissions, which indicates exponential savings over the conventional index coding that requires in the worst case O(n) transmissions. In this paper, building on a decoding criterion that we propose, we first design a deterministic polynomial-time algorithm that can realize the exponential benefits, by achieving, in the worst case, a performance upper bounded by O(log(2)(n)) broadcast transmissions. We extend our algorithm to the t-requests case, where each client requires t unknown messages that she does not have, and show that our algorithm requires at most O(t log(n) + log(2)(n)) broadcast transmissions. We construct lower bound instances that require at least Omega(log(n)) transmissions for linear pliable index coding and at least Omega(t + log(n)) transmissions for the t-requests case, indicating that both our upper and lower bounds are polynomials of log(n) and differ within a factor of O(log(n)). We provide a probabilistic analysis over random instances and show that the required number of transmissions is almost surely Theta(log(n)), as compared with the Theta(n/log(n)) for index coding. In addition, we show that these upper and lower bounds also hold for vector pliable index coding in the worst case instances and the random graph instances, implying that vector coding does not provide benefits in terms of these bounds. Our numerical experiments show that our algorithm outperforms existing algorithms for pliable index coding by up to 50% less transmissions.

关键词： pliable index coding index coding t-requests polynomial time algorithm greedy algorithm random graphs

来源：评论

学校读者我要写书评

暂无评论

SPARSE AND LOW-RANK OPTIMIZATION FOR pliable index coding

SPARSE AND LOW-RANK OPTIMIZATION FOR PLIABLE INDEX CODING

引用

IEEE Global Conference on Signal and Information Processing (GlobalSIP)

作者： Jiang, Tao Shi, Yuanming ShanghaiTech Univ Sch Informat Sci & Technol Shanghai Peoples R China

ISBN: (纸本)9781728112954

In this paper, we investigate the pliable index coding problem, where clients are interested in receiving any messages (instead of specific messages) that they do not have. The motivating applications including caching networks, recommendation systems and distributed computing systems, where the clients are happy to receive any messages not available in them. However, the pliable index coding problem turns out to be computationally intractable, for which we propose a novel sparse and low-rank optimization framework to assist efficient algorithms design in real field, thereby minimizing the number of channel uses for message delivery. To address the nonconvex challenges in this framework, we further propose the alternating projection algorithm to solve the sparse and low-rank optimization problem with local convergence guarantees. Simulation results demonstrate that the number of channel uses can be significantly reduced for message delivery via the sparse and low-rank optimization.

关键词： pliable index coding sparse and low-rank optimization alternating projection method

来源：评论

学校读者我要写书评

暂无评论

Making Recommendations Bandwidth Aware

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2018年第11期64卷 7031-7050页

作者： Song, Linqi Fragouli, Christina Univ Calif Los Angeles Elect & Comp Engn Dept Los Angeles CA 90095 USA City Univ Hong Kong Comp Sci Dept Hong Kong Hong Kong Peoples R China

This paper asks how much we can gain in terms of bandwidth and user satisfaction, if recommendation systems became bandwidth aware and took into account not only the user preferences, but also the fact that they may need to serve these users under bandwidth constraints, as is the case over wireless networks. We formulate this as a new problem in the context of index coding: we relax the index coding requirements to capture scenarios where each client has preferences associated with messages. The client is satisfied to receive any message she does not already have, with a satisfaction proportional to her preference for that message. We consistently find, over a number of scenarios we sample, that although the optimization problems are in general NP-hard, significant bandwidth savings are possible even when restricted to polynomial time algorithms.

关键词： pliable index coding recommendation systems bandwidth constraints index coding

来源：评论

学校读者我要写书评

暂无评论

pliable DATA SHUFFLING FOR ON-DEVICE DISTRIBUTED LEARNING 44

PLIABLE DATA SHUFFLING FOR ON-DEVICE DISTRIBUTED LEARNING

引用

44th IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

作者： Jiang, Tao Yang, Kai Shi, Yuanming ShanghaiTech Univ Sch Informat Sci & Technol Shanghai 201210 Peoples R China

ISBN: (纸本)9781479981311

Dataset reshuffling across mobile devices allows for speeding up on-device distributed machine learning, which however requires significant communication bandwidth. In this paper, we propose a pliable data shuffling approach to significantly reduce the communication cost for on-device distributed learning via joint data placement and transmission design. This is achieved by establishing the novel interference alignment conditions and diversity constraints for data shuffling to improve the statistical learning performance. Unfortunately, the presented pliable data shuffling problem is a highly intractable mixed combinatorial optimization problem, for which a novel sparse and low-rank framework is developed, supported by the computationally efficient difference-of-convex (DC) algorithm. Numerical results demonstrate that the proposed pliable data shuffling is able to significantly reduce the communication bandwidth while achieving desirable learning performance.

关键词： Distributed learning data shuffling wireless pliable index coding sparse and low rank

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：