Abstract

The performance of replication-based distributed databases is affected due to non-uniform storage across storage nodes (also called data skew) and reduction in the replication factor during operation, particularly due to node additions or removals. Data rebalancing refers to the communication involved between the nodes in correcting this data skew, while maintaining the replication factor. For carefully designed distributed databases, transmitting coded symbols during the rebalancing phase has been recently shown to reduce the communication load of rebalancing. In this work, we look at balanced distributed databases with random placement, in which each data segment is stored in a random subset of r nodes in the system, where r refers to the replication factor of the distributed database. We call these as decentralized databases. For a natural class of such decentralized databases, we propose rebalancing schemes for correcting data skew and the reduction in the replication factor arising due to a single node addition or removal. We give converse arguments which show that our proposed rebalancing schemes are optimal asymptotically in the size of the file.Due to space restrictions, the full version of this paper, containing proofs and additional results, is made available in [1].

Abstract

We consider the centralized coded caching system where a library of files is available at the server and their subfiles are cached at the clients as prescribed by a placement delivery array (PDA). We are interested in the problem where a specific file in the library is replaced with a new file at the server, the contents of which are correlated with the file being replaced, and this replacement needs to be communicated to the caches. The server loses the original file when the replacement is done and is unaware of the differences between the two files, whereas each cache has access to specific subfiles of the original file as dictated by the PDA. We model the correlation between the two files by assuming that they differ in at the most subfiles, and aim to reduce the number of bits broadcast by the server to update the caches. We design a new elegant coded transmission strategy for the server to update the caches blindly, and also identify another simple scheme that is based on MDS codes. We then derive converse bounds on the minimum cost among all linear strategies. Equipped with these results, we identify when the caching system uses a PDA of Yan et al. For two other families of PDAs--the Maddah-Ali-Niesen scheme and a scheme by Tang& Ramamoorthy and Yan et al.--we show that our new scheme has cost when the updates are sufficiently sparse, while the scheme using MDS codes has order-optimal cost when the updates are dense.

Abstract

Large gains in the rate of cache-aided broadcast communication are obtained using coded caching, but to obtain this most existing centralized coded caching schemes require that the files at the server be divisible into a large number of parts (this number is called subpacketization). In fact, most schemes require the subpacketization to be growing asymptotically as exponential in some root of the number of users . On the other extreme, few schemes having subpacketization linear in are known; however they require large number of users to exist, or they offer only little gain in rate. In this work, we propose a new framework known astextit {caching line graphs} for centralized coded caching and utilize projective geometries over finite fields to construct two new coded caching schemes with low subpacketization and moderate rate gains. Both the schemes achieve the same asymptotic subpacketization, which is …

Abstract

An index code for broadcast channel with receiver side information is locally decodable if each receiver can decode its demand by observing only a subset of the transmitted codeword symbols instead of the entire codeword. Local decodability in index coding is known to reduce receiver complexity, improve user privacy and decrease decoding error probability in wireless fading channels. Conventional index coding solutions assume that the receivers observe the entire codeword, and as a result, for these codes the number of codeword symbols queried by a user per decoded message symbol, which we refer to as locality, could be large. In this paper, we pose the index coding problem as that of minimizing the broadcast rate for a given value of locality (or vice versa) and designing codes that achieve the optimal trade-off between locality and rate. We identify the optimal broadcast rate corresponding to the minimum possible value of locality for all single unicast problems. We present new structural properties of index codes which allow us to characterize the optimal trade-off achieved by: vector linear codes when the side information graph is a directed cycle; and scalar linear codes when the minrank of the side information graph is one less than the order of the problem. We also identify the optimal trade-off among all codes, including non-linear codes, when the side information graph is a directed 3-cycle. Finally, we present techniques to design locally decodable index codes for arbitrary single unicast problems and arbitrary values of locality. Index Terms— Broadcast rate, directed cycle, index coding, linear codes, locally decodable codes, minrank.

Abstract

The problem of data exchange between multiple nodes with (not necessarily uniform) storage and communication capabilities models several current multi-user communication problems like Coded Caching, Data shuffling, Coded Computing, etc. The goal in such problems is to design communication schemes which accomplish the desired data exchange between the nodes with the optimal (minimum) amount of communication load. In this work, we present a converse to such a general data exchange problem between multiple nodes. The expression of the converse depends only on the number of bits to be moved between different subsets of nodes, and does not assume anything further specific about the parameters in the problem. Specific problem formulations, such as those in Coded Caching, Coded Data Shuffling, Coded Distributed Computing, and some of their variants, naturally can be seen as instances of this generic data exchange problem. Applying our generic converse to such problems, we recover known important converses for these settings and some of their variants in a simpler way. Further, for a generic coded caching problem with multiple transmitters, receivers and cache sizes, we show a new general converse which subsumes many existing results. We also employ our bound to obtain a new tight converse bound for the multi-node removal case in the Coded Data Rebalancing problem, in which nodes must exchange information to `rebalance' a storage cluster after some node failures occur. Finally we relate a `centralized' version of our bound to the known generalized independence number bound in index coding, and discuss our bound's tightness in this context.

Abstract

The performance of replication-based distributed databases is affected due to non-uniform storage across storage nodes (also called \textit{data skew}) and reduction in the replication factor during operation, particularly due to node additions or removals. Data rebalancing refers to the communication involved between the nodes in correcting this data skew, while maintaining the replication factor. For carefully designed distributed databases, transmitting coded symbols during the rebalancing phase has been recently shown to reduce the communication load of rebalancing. In this work, we look at balanced distributed databases with \textit{random placement}, in which each data segment is stored in a random subset of r nodes in the system, where r refers to the replication factor of the distributed database. We call these as decentralized databases. For a natural class of such decentralized databases, we propose rebalancing schemes for correcting data skew and the reduction in the replication factor arising due to a single node addition or removal. We give converse arguments which show that our proposed rebalancing schemes are optimal asymptotically in the size of the file.

Abstract

The shift from one-hot to distributed representation, popularly referred to as word embedding has changed the landscape of natural language processing (nlp) and information retrieval (ir) communities. In the domain of document images, we have always appreciated the need for learning a holistic word image representation which is popularly used for the task of word spotting. The representations proposed for word spotting is different from word embedding in text since the later captures the semantic aspects of the word which is a crucial ingredient to numerous nlp and ir tasks. In this work, we attempt to encode the notion of semantics into word image representation by bringing the advancements from the textual domain. We propose two novel forms of representations where the first form is designed to be inflection invariant by focusing on the approximate linguistic root of the word, while the second form is built …

Abstract

Distributed databases often suffer unequal distribution of data among storage nodes, which is known asdata skew'. Data skew arises from a number of causes such as removal of existing storage nodes and addition of new empty nodes to the database. Data skew leads to performance degradations and necessitatesrebalancing'at regular intervals to reduce the amount of skew. We define an -balanced distributed database as a distributed database in which the storage across the nodes has uniform size, and each bit of the data is replicated in distinct storage nodes. We consider the problem of designing such balanced databases along with associated rebalancing schemes which maintain the -balanced property under node removal and addition operations. We present a class of -balanced databases (parameterized by the number of storage nodes) which have the property of structural invariance, ie, the databases designed for different number of storage nodes have the same structure. For this class of -balanced databases, we present rebalancing schemes which use coded transmissions between storage nodes, and characterize their communication loads under node addition and removal. We show that the communication cost incurred to rebalance our distributed database for node addition and removal is optimal, ie, it achieves the minimum possible cost among all possible balanced distributed databases and rebalancing schemes.

Abstract

We consider the distributed computing framework of Map-Reduce, which consists of three phases, the Map phase, the Shuffle phase and the Reduce phase. For this framework, we propose the use of binary matrices (with entries) calledtextit {computing matrices} to describe the map phase and the shuffle phase. Similar binary matrices were recently proposed for the coded caching framework. The structure of ones and zeroes in the binary computing matrix captures the map phase of the Map-reduce framework. We present a new simple coded data shuffling scheme for this binary matrix model, based on atextit {identity submatrix cover} of the computing matrix. This new coded shuffling scheme has in general a larger communication load than existing schemes, but has the advantage of less complexity overhead than the well-known earlier schemes in literature in terms of the file-splitting and associated indexing and coordination required. We also show that there exists a binary matrix based distributed computing scheme with our new data-shuffling scheme which has strictly less than twice than the communication load of the known optimal scheme in literature. The structure of this new scheme enables it to be applied to the framework of Map-reduce with stragglers also, in a straightforward manner, borrowing its advantages and disadvantages from the no-straggler situation. Finally, using binary matrices derived from combinatorial designs, we show specific classes of computing schemes with very lowtextit {file complexity}(number of subfiles in the file), but with higher communication load compared to the optimal scheme for equivalent parameters.

Abstract

Circular perfect graphs are those undirected graphs such that the circular clique number is equal to the circular chromatic number for each induced subgraph. They form a strict superclass of the perfect graphs, whose index coding broadcast rates are well known. We present the broadcast rate of index coding for side-information graphs whose complements are circular perfect, along with an optimal achievable scheme. We thus enlarge the known classes of graphs for which the broadcast rate is exactly characterized. In an attempt to understand the broadcast rate of a graph given that of its complement, we obtain upper and lower bounds for the product and sum of the vector linear broadcast rates of a graph and its complement. We show that these bounds are satisfied with equality even for some perfect graphs. Curating prior results, we show that there are circular perfect but imperfect graphs which satisfy the lower bound on the product of the broadcast rate of the complementary graphs with equality.