BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Barna Saha

Barna Saha appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsMachine LearningDatabasesDiscrete MathematicsInformation Theorymath.ITArtificial IntelligenceFormal Languages and Automata Theory

Catalog footprint

What is connected

9works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2020arXiv

Connectivity in Random Annulus Graphs and the Geometric Block Model

We provide new connectivity results for {\em vertex-random graphs} or {\em random annulus graphs} which are significant generalizations of random geometric graphs. Random geometric graphs (RGG) are one of the most basic models of random graphs for spatial networks proposed by Gilbert in 1961, shortly after the introduction of the Erdős-R\'{en}yi random graphs. They resemble social networks in many ways (e.g. by spontaneously creating cluster of nodes with high modularity). The connectivity properties of RGG have been studied since its introduction, and analyzing them has been significantly harder than their Erdős-R\'{en}yi counterparts due to correlated edge formation. Our next contribution is in using the connectivity of random annulus graphs to provide necessary and sufficient conditions for efficient recovery of communities for {\em the geometric block model} (GBM). The GBM is a probabilistic model for community detection defined over an RGG in a similar spirit as the popular {\em stochastic block model}, which is defined over an Erdős-R\'{en}yi random graph. The geometric block model inherits the transitivity properties of RGGs and thus models communities better than a stochastic block model. However, analyzing them requires fresh perspectives as all prior tools fail due to correlation in edge formation. We provide a simple and efficient algorithm that can recover communities in GBM exactly with high probability in the regime of connectivity.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fair Correlation Clustering

In this paper we study the problem of correlation clustering under fairness constraints. In the classic correlation clustering problem, we are given a complete graph where each edge is labeled positive or negative. The goal is to obtain a clustering of the vertices that minimizes disagreements -- the number of negative edges trapped inside a cluster plus positive edges between different clusters. We consider two variations of fairness constraint for the problem of correlation clustering where each node has a color, and the goal is to form clusters that do not over-represent vertices of any color. The first variant aims to generate clusters with minimum disagreements, where the distribution of a feature (e.g. gender) in each cluster is same as the global distribution. For the case of two colors when the desired ratio of the number of colors in each cluster is $1:p$, we get $\mathcal{O}(p^2)$-approximation algorithm. Our algorithm could be extended to the case of multiple colors. We prove this problem is NP-hard. The second variant considers relative upper and lower bounds on the number of nodes of any color in a cluster. The goal is to avoid violating upper and lower bounds corresponding to each color in each cluster while minimizing the total number of disagreements. Along with our theoretical results, we show the effectiveness of our algorithm to generate fair clusters by empirical evaluation on real world data sets.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Clustering Via Crowdsourcing

In recent years, crowdsourcing, aka human aided computation has emerged as an effective platform for solving problems that are considered complex for machines alone. Using human is time-consuming and costly due to monetary compensations. Therefore, a crowd based algorithm must judiciously use any information computed through an automated process, and ask minimum number of questions to the crowd adaptively. One such problem which has received significant attention is {\em entity resolution}. Formally, we are given a graph $G=(V,E)$ with unknown edge set $E$ where $G$ is a union of $k$ (again unknown, but typically large $O(n^α)$, for $α>0$) disjoint cliques $G_i(V_i, E_i)$, $i =1, \dots, k$. The goal is to retrieve the sets $V_i$s by making minimum number of pair-wise queries $V \times V\to\{\pm1\}$ to an oracle (the crowd). When the answer to each query is correct, e.g. via resampling, then this reduces to finding connected components in a graph. On the other hand, when crowd answers may be incorrect, it corresponds to clustering over minimum number of noisy inputs. Even, with perfect answers, a simple lower and upper bound of $Θ(nk)$ on query complexity can be shown. A major contribution of this paper is to reduce the query complexity to linear or even sublinear in $n$ when mild side information is provided by a machine, and even in presence of crowd errors which are not correctable via resampling. We develop new information theoretic lower bounds on the query complexity of clustering with side information and errors, and our upper bounds closely match with them. Our algorithms are naturally parallelizable, and also give near-optimal bounds on the number of adaptive rounds required to match the query complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median

In this paper, we consider the fault-tolerant $k$-median problem and give the \emph{first} constant factor approximation algorithm for it. In the fault-tolerant generalization of classical $k$-median problem, each client $j$ needs to be assigned to at least $r_j \ge 1$ distinct open facilities. The service cost of $j$ is the sum of its distances to the $r_j$ facilities, and the $k$-median constraint restricts the number of open facilities to at most $k$. Previously, a constant factor was known only for the special case when all $r_j$s are the same, and a logarithmic approximation ratio for the general case. In addition, we present the first polynomial time algorithm for the fault-tolerant $k$-median problem on a path or a HST by showing that the corresponding LP always has an integral optimal solution. We also consider the fault-tolerant facility location problem, where the service cost of $j$ can be a weighted sum of its distance to the $r_j$ facilities. We give a simple constant factor approximation algorithm, generalizing several previous results which only work for nonincreasing weight vectors.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Distributed Data Placement via Graph Partitioning

With the widespread use of shared-nothing clusters of servers, there has been a proliferation of distributed object stores that offer high availability, reliability and enhanced performance for MapReduce-style workloads. However, relational workloads cannot always be evaluated efficiently using MapReduce without extensive data migrations, which cause network congestion and reduced query throughput. We study the problem of computing data placement strategies that minimize the data communication costs incurred by typical relational query workloads in a distributed setting. Our main contribution is a reduction of the data placement problem to the well-studied problem of {\sc Graph Partitioning}, which is NP-Hard but for which efficient approximation algorithms exist. The novelty and significance of this result lie in representing the communication cost exactly and using standard graphs instead of hypergraphs, which were used in prior work on data placement that optimized for different objectives (not communication cost). We study several practical extensions of the problem: with load balancing, with replication, with materialized views, and with complex query plans consisting of sequences of intermediate operations that may be computed on different servers. We provide integer linear programs (IPs) that may be used with any IP solver to find an optimal data placement. For the no-replication case, we use publicly available graph partitioning libraries (e.g., METIS) to efficiently compute nearly-optimal solutions. For the versions with replication, we introduce two heuristics that utilize the {\sc Graph Partitioning} solution of the no-replication case. Using the TPC-DS workload, it may take an IP solver weeks to compute an optimal data placement, whereas our reduction produces nearly-optimal solutions in seconds.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Efficiently Computing Edit Distance to Dyck Language

Given a string $σ$ over alphabet $Σ$ and a grammar $G$ defined over the same alphabet, how many minimum number of repairs: insertions, deletions and substitutions are required to map $σ$ into a valid member of $G$ ? We investigate this basic question in this paper for $Dyck(s)$. $Dyck(s)$ is a fundamental context free grammar representing the language of well-balanced parentheses with s different types of parentheses and has played a pivotal role in the development of theory of context free languages. Computing edit distance to $Dyck(s)$ significantly generalizes string edit distance problem and has numerous applications ranging from repairing semi-structured documents such as XML to memory checking, automated compiler optimization, natural language processing etc. In this paper we give the first near-linear time algorithm for edit distance computation to $Dyck(s)$ that achieves a nontrivial approximation factor of $O(\frac{1}ε\log{OPT}(\log{n})^{\frac{1}ε})$ in $O(n^{1+ε}\log{n})$ time. In fact, given there exists an algorithm for computing string edit distance on input of size $n$ in $α(n)$ time with $β(n)$-approximation factor, we can devise an algorithm for edit distance problem to $Dyck(s)$ running in $\tilde{O}(n^{1+ε}+α(n))$ and achieving an approximation factor of $O(\frac{1}εβ(n)\log{OPT})$. We show that the framework for efficiently approximating edit distance to $Dyck(s)$ can be applied to many other languages. We illustrate this by considering various memory checking languages which comprise of valid transcripts of stacks, queues, priority queues, double-ended queues etc. Therefore, any language that can be recognized by these data structures, can also be repaired efficiently by our algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

AdCell: Ad Allocation in Cellular Networks

With more than four billion usage of cellular phones worldwide, mobile advertising has become an attractive alternative to online advertisements. In this paper, we propose a new targeted advertising policy for Wireless Service Providers (WSPs) via SMS or MMS- namely {\em AdCell}. In our model, a WSP charges the advertisers for showing their ads. Each advertiser has a valuation for specific types of customers in various times and locations and has a limit on the maximum available budget. Each query is in the form of time and location and is associated with one individual customer. In order to achieve a non-intrusive delivery, only a limited number of ads can be sent to each customer. Recently, new services have been introduced that offer location-based advertising over cellular network that fit in our model (e.g., ShopAlerts by AT&T) . We consider both online and offline version of the AdCell problem and develop approximation algorithms with constant competitive ratio. For the online version, we assume that the appearances of the queries follow a stochastic distribution and thus consider a Bayesian setting. Furthermore, queries may come from different distributions on different times. This model generalizes several previous advertising models such as online secretary problem \cite{HKP04}, online bipartite matching \cite{KVV90,FMMM09} and AdWords \cite{saberi05}. ...

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

New Constructive Aspects of the Lovasz Local Lemma

The Lovász Local Lemma (LLL) states that the probability that none of a set of "bad" events happens is nonzero if the probability of each event is small compared to the number of bad events it depends on. A series of results have provided algorithms to efficiently construct structures whose existence is (non-constructively) guaranteed by the full asymmetric LLL, culminating in the recent breakthrough of Moser & Tardos. We show that the output distribution of the Moser-Tardos procedure has sufficient randomness, leading to two classes of algorithmic applications. We first show that when an LLL application provides a small amount of slack, the running time of the Moser-Tardos algorithm is polynomial in the number of underlying independent variables (not events!), and can thus be used to give efficient constructions in cases where the underlying proof applies the LLL to super-polynomially many events (or where finding a bad event that holds is computationally hard). We demonstrate our method on applications including: the first constant-factor approximation algorithm for the Santa Claus problem, as well as efficient algorithms for acyclic edge coloring, non-repetitive graph colorings, and Ramsey-type graphs. Second, we show applications to cases where a few of the bad events can hold, leading to the first such algorithmic applications of the LLL: MAX $k$-SAT is an illustrative example of this.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Unified Approach to Ranking in Probabilistic Databases

The dramatic growth in the number of application domains that naturally generate probabilistic, uncertain data has resulted in a need for efficiently supporting complex querying and decision-making over such data. In this paper, we present a unified approach to ranking and top-k query processing in probabilistic databases by viewing it as a multi-criteria optimization problem, and by deriving a set of features that capture the key properties of a probabilistic dataset that dictate the ranked result. We contend that a single, specific ranking function may not suffice for probabilistic databases, and we instead propose two parameterized ranking functions, called PRF-w and PRF-e, that generalize or can approximate many of the previously proposed ranking functions. We present novel generating functions-based algorithms for efficiently ranking large datasets according to these ranking functions, even if the datasets exhibit complex correlations modeled using probabilistic and/xor trees or Markov networks. We further propose that the parameters of the ranking function be learned from user preferences, and we develop an approach to learn those parameters. Finally, we present a comprehensive experimental study that illustrates the effectiveness of our parameterized ranking functions, especially PRF-e, at approximating other ranking functions and the scalability of our proposed algorithms for exact or approximate ranking.

0 citations0 reviewsNo code linkedOpen access