47 results on '"Shah, Nihar B."'
Search Results
2. How do authors' perceptions of their papers compare with co-authors' perceptions and peer-review decisions?
- Author
-
Rastogi, Charvi, Stelmakh, Ivan, Beygelzimer, Alina, Dauphin, Yann N., Liang, Percy, Wortman Vaughan, Jennifer, Xue, Zhenyu, Daumé III, Hal, Pierson, Emma, and Shah, Nihar B.
- Subjects
COMPUTER science conferences ,MALE authors ,AUTHORSHIP collaboration - Abstract
How do author perceptions match up to the outcomes of the peer-review process and perceptions of others? In a top-tier computer science conference (NeurIPS 2021) with more than 23,000 submitting authors and 9,000 submitted papers, we surveyed the authors on three questions: (i) their predicted probability of acceptance for each of their papers, (ii) their perceived ranking of their own papers based on scientific contribution, and (iii) the change in their perception about their own papers after seeing the reviews. The salient results are: (1) Authors had roughly a three-fold overestimate of the acceptance probability of their papers: The median prediction was 70% for an approximately 25% acceptance rate. (2) Female authors exhibited a marginally higher (statistically significant) miscalibration than male authors; predictions of authors invited to serve as meta-reviewers or reviewers were similarly calibrated, but better than authors who were not invited to review. (3) Authors' relative ranking of scientific contribution of two submissions they made generally agreed with their predicted acceptance probabilities (93% agreement), but there was a notable 7% responses where authors predicted a worse outcome for their better paper. (4) The author-provided rankings disagreed with the peer-review decisions about a third of the time; when co-authors ranked their jointly authored papers, co-authors disagreed at a similar rate—about a third of the time. (5) At least 30% of respondents of both accepted and rejected papers said that their perception of their own paper improved after the review process. The stakeholders in peer review should take these findings into account in setting their expectations from peer review. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
3. Parametric Prediction from Parametric Agents
- Author
-
Luo, Yuan, Shah, Nihar B., Huang, Jianwei, and Walrand, Jean
- Published
- 2018
4. Challenges, Experiments, and Computational Solutions in Peer Review.
- Author
-
SHAH, NIHAR B.
- Subjects
- *
SCHOLARLY peer review , *COMPUTER science , *EXPERIMENTS , *PREJUDICES , *STATISTICAL bias - Abstract
The author discusses computational methods utilized in the peer review process. It examines the availability of data in peer review, and experimentation in peer review design. It also discusses author identity bias, overall subjectivity in peer review, and author incentives.
- Published
- 2022
- Full Text
- View/download PDF
5. A large scale randomized controlled trial on herding in peer-review discussions.
- Author
-
Stelmakh, Ivan, Rastogi, Charvi, Shah, Nihar B., Singh, Aarti, and Daumé III, Hal
- Subjects
SCHOLARLY peer review ,ANCHORING effect ,COGNITIVE bias ,RANDOMIZED controlled trials ,MACHINE learning - Abstract
Peer review is the backbone of academia and humans constitute a cornerstone of this process, being responsible for reviewing submissions and making the final acceptance/rejection decisions. Given that human decision-making is known to be susceptible to various cognitive biases, it is important to understand which (if any) biases are present in the peer-review process, and design the pipeline such that the impact of these biases is minimized. In this work, we focus on the dynamics of discussions between reviewers and investigate the presence of herding behaviour therein. Specifically, we aim to understand whether reviewers and discussion chairs get disproportionately influenced by the first argument presented in the discussion when (in case of reviewers) they form an independent opinion about the paper before discussing it with others. In conjunction with the review process of a large, top tier machine learning conference, we design and execute a randomized controlled trial that involves 1,544 papers and 2,797 reviewers with the goal of testing for the conditional causal effect of the discussion initiator's opinion on the outcome of a paper. Our experiment reveals no evidence of herding in peer-review discussions. This observation is in contrast with past work that has documented an undue influence of the first piece of information on the final decision (e.g., anchoring effect) and analyzed herding behaviour in other applications (e.g., financial markets). Regarding policy implications, the absence of the herding effect suggests that the current status quo of the absence of a unified policy towards discussion initiation does not result in an increased arbitrariness of the resulting decisions. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
6. Cite-seeing and reviewing: A study on citation bias in peer review.
- Author
-
Stelmakh, Ivan, Rastogi, Charvi, Liu, Ryan, Chawla, Shuchi, Echenique, Federico, and Shah, Nihar B.
- Subjects
MACHINE learning ,SCIENTIFIC observation ,EXPERTISE - Abstract
Citations play an important role in researchers' careers as a key factor in evaluation of scientific impact. Many anecdotes advice authors to exploit this fact and cite prospective reviewers to try obtaining a more positive evaluation for their submission. In this work, we investigate if such a citation bias actually exists: Does the citation of a reviewer's own work in a submission cause them to be positively biased towards the submission? In conjunction with the review process of two flagship conferences in machine learning and algorithmic economics, we execute an observational study to test for citation bias in peer review. In our analysis, we carefully account for various confounding factors such as paper quality and reviewer expertise, and apply different modeling techniques to alleviate concerns regarding the model mismatch. Overall, our analysis involves 1,314 papers and 1,717 reviewers and detects citation bias in both venues we consider. In terms of the effect size, by citing a reviewer's work, a submission has a non-trivial chance of getting a higher score from the reviewer: an expected increase in the score is approximately 0.23 on a 5-point Likert item. For reference, a one-point increase of a score by a single reviewer improves the position of a submission by 11% on average. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
7. The role of author identities in peer review.
- Author
-
Shah, Nihar B.
- Subjects
- *
CONFLICT of interests , *COMPUTER science - Abstract
There is widespread debate on whether to anonymize author identities in peer review. The key argument for anonymization is to mitigate bias, whereas arguments against anonymization posit various uses of author identities in the review process. The Innovations in Theoretical Computer Science (ITCS) 2023 conference adopted a middle ground by initially anonymizing the author identities from reviewers, revealing them after the reviewer had submitted their initial reviews, and allowing the reviewer to change their review subsequently. We present an analysis of the reviews pertaining to the identification and use of author identities. Our key findings are: (I) A majority of reviewers self-report not knowing and being unable to guess the authors' identities for the papers they were reviewing. (II) After the initial submission of reviews, 7.1% of reviews changed their overall merit score and 3.8% changed their self-reported reviewer expertise. (III) There is a very weak and statistically insignificant correlation of the rank of authors' affiliations with the change in overall merit; there is a weak but statistically significant correlation with respect to change in reviewer expertise. We also conducted an anonymous survey to obtain opinions from reviewers and authors. The main findings from the 200 survey responses are: (i) A vast majority of participants favor anonymizing author identities in some form. (ii) The "middle-ground" initiative of ITCS 2023 was appreciated. (iii) Detecting conflicts of interest is a challenge that needs to be addressed if author identities are anonymized. Overall, these findings support anonymization of author identities in some form (e.g., as was done in ITCS 2023), as long as there is a robust and efficient way to check conflicts of interest. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
8. How do Authors' Perceptions of their Papers Compare with Co-authors' Perceptions and Peer-review Decisions?
- Author
-
Rastogi, Charvi, Stelmakh, Ivan, Beygelzimer, Alina, Dauphin, Yann N., Liang, Percy, Vaughan, Jennifer Wortman, Xue, Zhenyu, Daumé, Hal, Pierson, Emma, and Shah, Nihar B.
- Subjects
FOS: Computer and information sciences ,Computer Science - Machine Learning ,Computer Science - Databases ,Databases (cs.DB) ,Digital Libraries (cs.DL) ,Computer Science - Digital Libraries ,Machine Learning (cs.LG) - Abstract
How do author perceptions match up to the outcomes of the peer-review process and perceptions of others? In a top-tier computer science conference (NeurIPS 2021) with more than 23,000 submitting authors and 9,000 submitted papers, we survey the authors on three questions: (i) their predicted probability of acceptance for each of their papers, (ii) their perceived ranking of their own papers based on scientific contribution, and (iii) the change in their perception about their own papers after seeing the reviews. The salient results are: (1) Authors have roughly a three-fold overestimate of the acceptance probability of their papers: The median prediction is 70% for an approximately 25% acceptance rate. (2) Female authors exhibit a marginally higher (statistically significant) miscalibration than male authors; predictions of authors invited to serve as meta-reviewers or reviewers are similarly calibrated, but better than authors who were not invited to review. (3) Authors' relative ranking of scientific contribution of two submissions they made generally agree (93%) with their predicted acceptance probabilities, but there is a notable 7% responses where authors think their better paper will face a worse outcome. (4) The author-provided rankings disagreed with the peer-review decisions about a third of the time; when co-authors ranked their jointly authored papers, co-authors disagreed at a similar rate -- about a third of the time. (5) At least 30% of respondents of both accepted and rejected papers said that their perception of their own paper improved after the review process. The stakeholders in peer review should take these findings into account in setting their expectations from peer review.
- Published
- 2022
9. Integrating Rankings into Quantized Scores in Peer Review
- Author
-
Liu, Yusha, Xu, Yichong, Shah, Nihar B., and Singh, Aarti
- Subjects
Methodology (stat.ME) ,FOS: Computer and information sciences ,Information Retrieval (cs.IR) ,Statistics - Methodology ,Computer Science - Information Retrieval - Abstract
In peer review, reviewers are usually asked to provide scores for the papers. The scores are then used by Area Chairs or Program Chairs in various ways in the decision-making process. The scores are usually elicited in a quantized form to accommodate the limited cognitive ability of humans to describe their opinions in numerical values. It has been found that the quantized scores suffer from a large number of ties, thereby leading to a significant loss of information. To mitigate this issue, conferences have started to ask reviewers to additionally provide a ranking of the papers they have reviewed. There are however two key challenges. First, there is no standard procedure for using this ranking information and Area Chairs may use it in different ways (including simply ignoring them), thereby leading to arbitrariness in the peer-review process. Second, there are no suitable interfaces for judicious use of this data nor methods to incorporate it in existing workflows, thereby leading to inefficiencies. We take a principled approach to integrate the ranking information into the scores. The output of our method is an updated score pertaining to each review that also incorporates the rankings. Our approach addresses the two aforementioned challenges by: (i) ensuring that rankings are incorporated into the updates scores in the same manner for all papers, thereby mitigating arbitrariness, and (ii) allowing to seamlessly use existing interfaces and workflows designed for scores. We empirically evaluate our method on synthetic datasets as well as on peer reviews from the ICLR 2017 conference, and find that it reduces the error by approximately 30% as compared to the best performing baseline on the ICLR 2017 data., 14 main pages, 7 appendix pages
- Published
- 2022
10. Cite-seeing and Reviewing: A Study on Citation Bias in Peer Review
- Author
-
Stelmakh, Ivan, Rastogi, Charvi, Liu, Ryan, Chawla, Shuchi, Echenique, Federico, and Shah, Nihar B.
- Subjects
FOS: Computer and information sciences ,Digital Libraries (cs.DL) ,Applications (stat.AP) ,Computer Science - Digital Libraries ,Statistics - Applications - Abstract
Citations play an important role in researchers' careers as a key factor in evaluation of scientific impact. Many anecdotes advice authors to exploit this fact and cite prospective reviewers to try obtaining a more positive evaluation for their submission. In this work, we investigate if such a citation bias actually exists: Does the citation of a reviewer's own work in a submission cause them to be positively biased towards the submission? In conjunction with the review process of two flagship conferences in machine learning and algorithmic economics, we execute an observational study to test for citation bias in peer review. In our analysis, we carefully account for various confounding factors such as paper quality and reviewer expertise, and apply different modeling techniques to alleviate concerns regarding the model mismatch. Overall, our analysis involves 1,314 papers and 1,717 reviewers and detects citation bias in both venues we consider. In terms of the effect size, by citing a reviewer's work, a submission has a non-trivial chance of getting a higher score from the reviewer: an expected increase in the score is approximately 0.23 on a 5-point Likert item. For reference, a one-point increase of a score by a single reviewer improves the position of a submission by 11% on average., 19 pages, 3 figures
- Published
- 2022
11. A Novice-Reviewer Experiment to Address Scarcity of Qualified Reviewers in Large Conferences
- Author
-
Stelmakh, Ivan, Shah, Nihar B., Singh, Aarti, and Daum��, Hal
- Subjects
FOS: Computer and information sciences ,Computer Science - Machine Learning ,Computer Science - Human-Computer Interaction ,General Medicine ,Human-Computer Interaction (cs.HC) ,Machine Learning (cs.LG) - Abstract
Conference peer review constitutes a human-computation process whose importance cannot be overstated: not only it identifies the best submissions for acceptance, but, ultimately, it impacts the future of the whole research area by promoting some ideas and restraining others. A surge in the number of submissions received by leading AI conferences has challenged the sustainability of the review process by increasing the burden on the pool of qualified reviewers which is growing at a much slower rate. In this work, we consider the problem of reviewer recruiting with a focus on the scarcity of qualified reviewers in large conferences. Specifically, we design a procedure for (i) recruiting reviewers from the population not typically covered by major conferences and (ii) guiding them through the reviewing pipeline. In conjunction with the ICML 2020 --- a large, top-tier machine learning conference --- we recruit a small set of reviewers through our procedure and compare their performance with the general population of ICML reviewers. Our experiment reveals that a combination of the recruiting and guiding mechanisms allows for a principled enhancement of the reviewer pool and results in reviews of superior quality compared to the conventional pool of reviews as evaluated by senior members of the program committee (meta-reviewers).
- Published
- 2020
12. Network coding
- Author
-
Rashmi, K. V., Shah, Nihar B., and Vijay Kumar, P.
- Published
- 2010
- Full Text
- View/download PDF
13. Mitigating Manipulation in Peer Review via Randomized Reviewer Assignments
- Author
-
Jecmen, Steven, Zhang, Hanrui, Liu, Ryan, Shah, Nihar B., Conitzer, Vincent, and Fang, Fei
- Subjects
FOS: Computer and information sciences ,Artificial Intelligence (cs.AI) ,Computer Science - Artificial Intelligence ,Computer Science - Computer Science and Game Theory ,Computer Science and Game Theory (cs.GT) - Abstract
We consider three important challenges in conference peer review: (i) reviewers maliciously attempting to get assigned to certain papers to provide positive reviews, possibly as part of quid-pro-quo arrangements with the authors; (ii) "torpedo reviewing," where reviewers deliberately attempt to get assigned to certain papers that they dislike in order to reject them; (iii) reviewer de-anonymization on release of the similarities and the reviewer-assignment code. On the conceptual front, we identify connections between these three problems and present a framework that brings all these challenges under a common umbrella. We then present a (randomized) algorithm for reviewer assignment that can optimally solve the reviewer-assignment problem under any given constraints on the probability of assignment for any reviewer-paper pair. We further consider the problem of restricting the joint probability that certain suspect pairs of reviewers are assigned to certain papers, and show that this problem is NP-hard for arbitrary constraints on these joint probabilities but efficiently solvable for a practical special case. Finally, we experimentally evaluate our algorithms on datasets from past conferences, where we observe that they can limit the chance that any malicious reviewer gets assigned to their desired paper to 50% while producing assignments with over 90% of the total optimal similarity. Our algorithms still achieve this similarity while also preventing reviewers with close associations from being assigned to the same paper.
- Published
- 2020
14. Two-Sample Testing on Ranked Preference Data and the Role of Modeling Assumptions
- Author
-
Rastogi, Charvi, Balakrishnan, Sivaraman, Shah, Nihar B., and Singh, Aarti
- Subjects
FOS: Computer and information sciences ,Computer Science - Machine Learning ,Statistics - Machine Learning ,Information Theory (cs.IT) ,Computer Science - Information Theory ,Machine Learning (stat.ML) ,Machine Learning (cs.LG) - Abstract
A number of applications require two-sample testing on ranked preference data. For instance, in crowdsourcing, there is a long-standing question of whether pairwise comparison data provided by people is distributed similar to ratings-converted-to-comparisons. Other examples include sports data analysis and peer grading. In this paper, we design two-sample tests for pairwise comparison data and ranking data. For our two-sample test for pairwise comparison data, we establish an upper bound on the sample complexity required to correctly distinguish between the distributions of the two sets of samples. Our test requires essentially no assumptions on the distributions. We then prove complementary lower bounds showing that our results are tight (in the minimax sense) up to constant factors. We investigate the role of modeling assumptions by proving lower bounds for a range of pairwise comparison models (WST, MST,SST, parameter-based such as BTL and Thurstone). We also provide testing algorithms and associated sample complexity bounds for the problem of two-sample testing with partial (or total) ranking data.Furthermore, we empirically evaluate our results via extensive simulations as well as two real-world datasets consisting of pairwise comparisons. By applying our two-sample test on real-world pairwise comparison data, we conclude that ratings and rankings provided by people are indeed distributed differently. On the other hand, our test recognizes no significant difference in the relative performance of European football teams across two seasons. Finally, we apply our two-sample test on a real-world partial and total ranking dataset and find a statistically significant difference in Sushi preferences across demographic divisions based on gender, age and region of residence., 40 pages, 4 figures
- Published
- 2020
15. Stretching the Effectiveness of MLE from Accuracy to Bias for Pairwise Comparisons
- Author
-
Wang, Jingyan, Shah, Nihar B., and Ravi, R.
- Subjects
FOS: Computer and information sciences ,Computer Science - Machine Learning ,Statistics - Machine Learning ,Information Theory (cs.IT) ,Computer Science - Information Theory ,Machine Learning (stat.ML) ,Machine Learning (cs.LG) - Abstract
A number of applications (e.g., AI bot tournaments, sports, peer grading, crowdsourcing) use pairwise comparison data and the Bradley-Terry-Luce (BTL) model to evaluate a given collection of items (e.g., bots, teams, students, search results). Past work has shown that under the BTL model, the widely-used maximum-likelihood estimator (MLE) is minimax-optimal in estimating the item parameters, in terms of the mean squared error. However, another important desideratum for designing estimators is fairness. In this work, we consider fairness modeled by the notion of bias in statistics. We show that the MLE incurs a suboptimal rate in terms of bias. We then propose a simple modification to the MLE, which "stretches" the bounding box of the maximum-likelihood optimizer by a small constant factor from the underlying ground truth domain. We show that this simple modification leads to an improved rate in bias, while maintaining minimax-optimality in the mean squared error. In this manner, our proposed class of estimators provably improves fairness represented by bias without loss in accuracy.
- Published
- 2019
16. A Permutation-Based Model for Crowd Labeling: Optimal Estimation and Robustness.
- Author
-
Shah, Nihar B., Balakrishnan, Sivaraman, and Wainwright, Martin J.
- Subjects
- *
CROWDSOURCING , *CROWDS , *DRUG labeling , *NOISE measurement , *TASK analysis , *LABELS , *GENERALIZATION - Abstract
The task of aggregating and denoising crowd-labeled data has gained increased significance with the advent of crowdsourcing platforms and massive datasets. We propose a permutation-based model for crowd labeled data that is a significant generalization of the classical Dawid-Skene model, and introduce a new error metric by which to compare different estimators. We derive global minimax rates for the permutation-based model that are sharp up to logarithmic factors, and match the minimax lower bounds derived under the simpler Dawid-Skene model. We then design two computationally-efficient estimators: the WAN estimator for the setting where the ordering of workers in terms of their abilities is approximately known, and the OBI- WAN estimator where that is not known. For each of these estimators, we provide non-asymptotic bounds on their performance. We conduct synthetic simulations and experiments on real-world crowdsourcing data, and the experimental results corroborate our theoretical findings. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
17. Loss Functions, Axioms, and Peer Review
- Author
-
Noothigattu, Ritesh, Shah, Nihar B., and Procaccia, Ariel D.
- Subjects
FOS: Computer and information sciences ,Computer Science - Machine Learning ,Artificial Intelligence (cs.AI) ,Computer Science - Artificial Intelligence ,Computer Science - Computer Science and Game Theory ,Computer Science and Game Theory (cs.GT) ,Machine Learning (cs.LG) - Abstract
It is common to see a handful of reviewers reject a highly novel paper, because they view, say, extensive experiments as far more important than novelty, whereas the community as a whole would have embraced the paper. More generally, the disparate mapping of criteria scores to final recommendations by different reviewers is a major source of inconsistency in peer review. In this paper we present a framework inspired by empirical risk minimization (ERM) for learning the community's aggregate mapping. The key challenge that arises is the specification of a loss function for ERM. We consider the class of $L(p,q)$ loss functions, which is a matrix-extension of the standard class of $L_p$ losses on vectors; here the choice of the loss function amounts to choosing the hyperparameters $p, q \in [1,\infty]$. To deal with the absence of ground truth in our problem, we instead draw on computational social choice to identify desirable values of the hyperparameters $p$ and $q$. Specifically, we characterize $p=q=1$ as the only choice of these hyperparameters that satisfies three natural axiomatic properties. Finally, we implement and apply our approach to reviews from IJCAI 2017.
- Published
- 2018
18. On Strategyproof Conference Peer Review
- Author
-
Xu, Yichong, Zhao, Han, Shi, Xiaofei, Zhang, Jeremy, and Shah, Nihar B.
- Subjects
FOS: Computer and information sciences ,Computer Science - Machine Learning ,Artificial Intelligence (cs.AI) ,Computer Science - Computer Science and Game Theory ,Computer Science - Artificial Intelligence ,Statistics - Machine Learning ,Machine Learning (stat.ML) ,Computer Science and Game Theory (cs.GT) ,Machine Learning (cs.LG) - Abstract
We consider peer review in a conference setting where there is typically an overlap between the set of reviewers and the set of authors. This overlap can incentivize strategic reviews to influence the final ranking of one's own papers. In this work, we address this problem through the lens of social choice, and present a theoretical framework for strategyproof and efficient peer review. We first present and analyze an algorithm for reviewer-assignment and aggregation that guarantees strategyproofness and a natural efficiency property called unanimity, when the authorship graph satisfies a simple property. Our algorithm is based on the so-called partitioning method, and can be thought as a generalization of this method to conference peer review settings. We then empirically show that the requisite property on the authorship graph is indeed satisfied in the submission data from the ICLR conference, and further demonstrate a simple trick to make the partitioning method more practically appealing for conference peer review. Finally, we complement our positive results with negative theoretical results where we prove that under various ways of strengthening the requirements, it is impossible for any algorithm to be strategyproof and efficient.
- Published
- 2018
19. Design and Analysis of the NIPS 2016 Review Process
- Author
-
Shah, Nihar B., Tabibian, Behzad, Muandet, Krikamol, Guyon, Isabelle, von Luxburg, Ulrike, Department of Electrical Engineering and Computer Sciences (Berkeley EECS), Max Planck Institute for Intelligent Systems, Max-Planck-Gesellschaft, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), TAckling the Underspecified (TAU), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), University of Tübingen, Carnegie Mellon University [Pittsburgh] (CMU), Mahidol University [Bangkok], and Max Planck Institute for Intelligent Systems [Tübingen]
- Subjects
Social and Information Networks (cs.SI) ,FOS: Computer and information sciences ,Computer Science - Learning ,[INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG] ,Statistics - Machine Learning ,[INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV] ,Computer Science - Digital Libraries ,Computer Science - Social and Information Networks ,Digital Libraries (cs.DL) ,Machine Learning (stat.ML) ,[INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE] ,Machine Learning (cs.LG) ,[INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] - Abstract
International audience; Neural Information Processing Systems (NIPS) is a top-tier annual conference in machine learning. The 2016 edition of the conference comprised more than 2,400 paper submissions, 3,000 reviewers, and 8,000 attendees. This represents a growth of nearly 40% in terms of submissions, 96% in terms of reviewers, and over 100% in terms of attendees as compared to the previous year. The massive scale as well as rapid growth of the conference calls for a thorough quality assessment of the peer-review process and novel means of improvement. In this paper, we analyze several aspects of the data collected during the review process, including an experiment investigating the efficacy of collecting ordinal rankings from reviewers. We make a number of key observations, provide suggestions that may be useful for subsequent conferences, and discuss open problems towards the goal of improving peer review.
- Published
- 2018
20. Simple, Robust and Optimal Ranking from Pairwise Comparisons
- Author
-
Shah, Nihar B. and Wainwright, Martin J.
- Subjects
FOS: Computer and information sciences ,Computer Science - Learning ,Artificial Intelligence (cs.AI) ,Computer Science - Artificial Intelligence ,Statistics - Machine Learning ,Information Theory (cs.IT) ,Computer Science - Information Theory ,Machine Learning (stat.ML) ,Machine Learning (cs.LG) - Abstract
We consider data in the form of pairwise comparisons of n items, with the goal of precisely identifying the top k items for some value of k < n, or alternatively, recovering a ranking of all the items. We analyze the Copeland counting algorithm that ranks the items in order of the number of pairwise comparisons won, and show it has three attractive features: (a) its computational efficiency leads to speed-ups of several orders of magnitude in computation time as compared to prior work; (b) it is robust in that theoretical guarantees impose no conditions on the underlying matrix of pairwise-comparison probabilities, in contrast to some prior work that applies only to the BTL parametric model; and (c) it is an optimal method up to constant factors, meaning that it achieves the information-theoretic limits for recovering the top k-subset. We extend our results to obtain sharp guarantees for approximate recovery under the Hamming distortion metric, and more generally, to any arbitrary error requirement that satisfies a simple and natural monotonicity condition., Changes in version 2: In addition to recovery in the exact and Hamming metrics, v2 analyzes a general, abstract recovery criterion based on a notion of "allowed sets"
- Published
- 2015
21. Approval Voting and Incentives in Crowdsourcing
- Author
-
Shah, Nihar B., Zhou, Dengyong, and Peres, Yuval
- Subjects
FOS: Computer and information sciences ,Computer Science - Learning ,Artificial Intelligence (cs.AI) ,Computer Science - Computer Science and Game Theory ,Computer Science - Artificial Intelligence ,Computer Science - Multiagent Systems ,Computer Science and Game Theory (cs.GT) ,Machine Learning (cs.LG) ,Multiagent Systems (cs.MA) - Abstract
The growing need for labeled training data has made crowdsourcing an important part of machine learning. The quality of crowdsourced labels is, however, adversely affected by three factors: (1) the workers are not experts; (2) the incentives of the workers are not aligned with those of the requesters; and (3) the interface does not allow workers to convey their knowledge accurately, by forcing them to make a single choice among a set of options. In this paper, we address these issues by introducing approval voting to utilize the expertise of workers who have partial knowledge of the true answer, and coupling it with a ("strictly proper") incentive-compatible compensation mechanism. We show rigorous theoretical guarantees of optimality of our mechanism together with a simple axiomatic characterization. We also conduct preliminary empirical studies on Amazon Mechanical Turk which validate our approach.
- Published
- 2015
22. On the Impossibility of Convex Inference in Human Computation
- Author
-
Shah, Nihar B. and Zhou, Dengyong
- Subjects
FOS: Computer and information sciences ,Computer Science - Learning ,Statistics - Machine Learning ,Computer Science - Human-Computer Interaction ,Machine Learning (stat.ML) ,Human-Computer Interaction (cs.HC) ,Machine Learning (cs.LG) - Abstract
Human computation or crowdsourcing involves joint inference of the ground-truth-answers and the worker-abilities by optimizing an objective function, for instance, by maximizing the data likelihood based on an assumed underlying model. A variety of methods have been proposed in the literature to address this inference problem. As far as we know, none of the objective functions in existing methods is convex. In machine learning and applied statistics, a convex function such as the objective function of support vector machines (SVMs) is generally preferred, since it can leverage the high-performance algorithms and rigorous guarantees established in the extensive literature on convex optimization. One may thus wonder if there exists a meaningful convex objective function for the inference problem in human computation. In this paper, we investigate this convexity issue for human computation. We take an axiomatic approach by formulating a set of axioms that impose two mild and natural assumptions on the objective function for the inference. Under these axioms, we show that it is unfortunately impossible to ensure convexity of the inference problem. On the other hand, we show that interestingly, in the absence of a requirement to model "spammers", one can construct reasonable objective functions for crowdsourcing that guarantee convex inference., AAAI 2015
- Published
- 2014
23. Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons.
- Author
-
Shah, Nihar B., Balakrishnan, Sivaraman, and Wainwright, Martin J.
- Subjects
- *
PROBABILITY theory , *PAIRED comparisons (Mathematics) , *STOCHASTIC processes , *LEAST squares , *ACQUISITION of data - Abstract
We study methods for aggregating pairwise comparison data among a collection of $n$ items with the goal of estimating the outcome probabilities for future comparisons. Working within a flexible model that only imposes a form of strong stochastic transitivity, we introduce an “adaptivity index” which compares the risk of our estimator to that of an oracle, over appropriate sub-models, where the oracle knows the specific sub-model in the ground truth. In addition to measuring the usual worst-case risk of an estimator, this adaptivity index also captures the extent to which the estimator adapts to instance-specific difficulty relative to an oracle estimator. First, we propose a three-step estimator termed count-randomize-least squares, and show that it has adaptivity index upper bounded by $\sqrt {n}$ up to logarithmic factors. We then show that conditional on the planted clique hypothesis, no computationally efficient estimator can achieve an adaptivity index smaller than $\sqrt {n}$. Second, we show that a regularized least squares estimator can achieve a poly-logarithmic adaptivity index, thereby demonstrating a $\sqrt {n}$ -gap between optimal and computationally achievable adaptivity. Finally, we prove that the standard least squares estimator, which is known to be optimally adaptive in several closely related problems, fails to adapt in the context of estimating pairwise probabilities. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
24. When is it Better to Compare than to Score?
- Author
-
Shah, Nihar B., Balakrishnan, Sivaraman, Bradley, Joseph, Parekh, Abhay, Ramchandran, Kannan, and Wainwright, Martin
- Subjects
FOS: Computer and information sciences ,Mathematics::Logic ,Computer Science - Learning ,Statistics - Machine Learning ,Machine Learning (stat.ML) ,Machine Learning (cs.LG) - Abstract
When eliciting judgements from humans for an unknown quantity, one often has the choice of making direct-scoring (cardinal) or comparative (ordinal) measurements. In this paper we study the relative merits of either choice, providing empirical and theoretical guidelines for the selection of a measurement scheme. We provide empirical evidence based on experiments on Amazon Mechanical Turk that in a variety of tasks, (pairwise-comparative) ordinal measurements have lower per sample noise and are typically faster to elicit than cardinal ones. Ordinal measurements however typically provide less information. We then consider the popular Thurstone and Bradley-Terry-Luce (BTL) models for ordinal measurements and characterize the minimax error rates for estimating the unknown quantity. We compare these minimax error rates to those under cardinal measurement models and quantify for what noise levels ordinal measurements are better. Finally, we revisit the data collected from our experiments and show that fitting these models confirms this prediction: for tasks where the noise in ordinal measurements is sufficiently low, the ordinal approach results in smaller errors in the estimation.
- Published
- 2014
25. Addendum and Erratum to “The MDS Queue: Analysing the Latency Performance of Erasure Codes”.
- Author
-
Lee, Kangwook, Shah, Nihar B., Huang, Longbo, and Ramchandran, Kannan
- Subjects
- *
LOGICAL prediction , *SCHEDULING , *QUEUING theory , *REED-Solomon codes - Abstract
In the above article , we introduced two scheduling policies and analyzed their average job latencies. With an implicit assumption that the scheduling policies provide sample-path bounds by construction, we claimed that their average job latencies serve as upper and lower bounds on that of a centralized MDS queue. In this note, we present recently discovered counterexamples, disproving the assumption. We replace the assumption with a conjecture that the average latency bounds still hold. We also provide an erratum to the original article to correct any confusing or misleading statements. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
26. Simple, Robust and Optimal Ranking from Pairwise Comparisons.
- Author
-
Shah, Nihar B. and Wainwright, Martin J.
- Subjects
- *
PAIRED comparisons (Mathematics) , *ROBUST statistics , *RANKING (Statistics) , *ALGORITHMS , *INFORMATION theory - Abstract
We consider data in the form of pairwise comparisons of n items, with the goal of identifying the top k items for some value of k < n, or alternatively, recovering a ranking of all the items. We analyze the Borda counting algorithm that ranks the items in order of the number of pairwise comparisons won, and show it has three attractive features: (a) it is an optimal method achieving the information-theoretic limits up to constant factors; (b) it is robust in that its optimality holds without imposing conditions on the underlying matrix of pairwise-comparison probabilities, in contrast to some prior work that applies only to the BTL parametric model; and (c) its computational efficiency leads to speed-ups of several orders of magnitude. We address the problem of exact recovery, and for the top-k recovery problem we also extend our results to obtain sharp guarantees for approximate recovery under the Hamming distortion metric, and more generally, to any arbitrary error requirement that satisfies a simple and natural monotonicity condition. In doing so, we introduce a general framework that allows us to treat a variety of problems in the literature in an unified manner. [ABSTRACT FROM AUTHOR]
- Published
- 2018
27. Information-Theoretically Secure Erasure Codes for Distributed Storage.
- Author
-
Rashmi, K. V., Shah, Nihar B., Ramchandran, Kannan, and Kumar, P. Vijay
- Subjects
- *
EAVESDROPPING , *DATA recovery , *CYCLIC redundancy check codes , *POLYTOPES , *ALGORITHMS - Abstract
Repair operations in erasure-coded distributed storage systems involve a lot of data movement. This can potentially expose data to malicious acts of passive eavesdroppers or active adversaries, putting security of the system at risk. This paper presents coding schemes and repair algorithms that ensure security of the data in the presence of passive eavesdroppers and active adversaries while maintaining high availability, reliability, and resource efficiency in the system. The proposed codes are optimal in that they meet previously proposed lower bounds on storage and network-bandwidth requirements for a wide range of system parameters. The results thus establish the secure storage capacity of such systems. The proposed codes are based on an optimal class of codes called product-matrix codes. The constructions presented for security from active adversaries provide an additional appealing feature of “on-demand security,” where the desired level of security can be chosen separately for each instance of repair, and the proposed algorithms remain optimal simultaneously for all possible security levels. This paper also provides necessary and sufficient conditions governing the transformation of any (non-secure) code into one providing on-demand security. [ABSTRACT FROM PUBLISHER]
- Published
- 2018
- Full Text
- View/download PDF
28. Parametric Prediction from Parametric Agents.
- Author
-
Yuan Luo, Shah, Nihar B., Jianwei Huang, and Walrand, Jean
- Subjects
INFORMATION technology ,PREDICTION theory ,STOCHASTIC processes ,PARAMETERS (Statistics) ,ALGORITHMS - Abstract
We consider a problem of prediction based on opinions elicited from heterogeneous rational agents with private information. Making an accurate prediction with a minimal cost requires a joint design of the incentive mechanism and the prediction algorithm. To elicit heterogeneous agents' private information and incentivize agents with different capabilities to act in the principal's best interest,we design an optimal joint incentive mechanism and prediction algorithm called COPE (COst and Prediction Elicitation), the analysis of which offers several valuable engineering insights. First, when the costs incurred by the agents are linear in the exerted effort, COPE corresponds to a "crowdcontending" mechanism, where the principal only employs the agent with the highest capability. Second, when the costs are quadratic, COPE corresponds to a "crowdsourcing" mechanism that employs multiple agents with different capabilities at the same time. Numerical simulations show that COPE improves the principal's profit (The improvement is 5%-30% in our simulations), comparing to those mechanisms that assume all agents have equal capabilities. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
29. A Piggybacking Design Framework for Read-and Download-Efficient Distributed Storage Codes.
- Author
-
Rashmi, K. V., Shah, Nihar B., and Ramchandran, Kannan
- Subjects
- *
DISTRIBUTED databases , *BANDWIDTHS , *RELIABILITY in engineering , *DATA management , *DOWNLOADING - Abstract
Erasure codes are being extensively deployed in distributed storage systems instead of replication to achieve fault tolerance in a storage efficient manner. While traditional erasure codes are storage efficient, they can result in a significant increase in the amount of data access and downloaded during rebuilding of failed or otherwise unavailable nodes. In this paper, we present a new framework, which we call piggybacking, for constructing distributed storage codes that are efficient in the amount of data read and downloaded during rebuilding, while meeting requirements arising out of system considerations in data centers—maximum-distance-separability (MDS), high-rate, and a small number of so-called substripes. Under this setting, to the best of our knowledge, piggyback codes achieve the minimum average amount of data access and downloaded during rebuilding among all existing explicit solutions. The piggybacking framework also offers a rich design space for constructing codes for a variety of other settings. In particular, we construct codes that require minimum amount of data access and downloaded for rebuilding among all existing solutions for: 1) binary MDS array codes with more than two parities and 2) MDS codes with the smallest locality during rebuilding. In addition, we show how piggybacking can be employed to enable efficient repair of parity nodes in codes that address the rebuilding of only systematic nodes. The basic idea behind the piggybacking framework is to take multiple instances of existing codes and add carefully designed functions of the data from one instance to the others. This framework provides 25% to 50% savings in the average amount of data access and downloaded during rebuilding depending on the choice of the code parameters. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
30. The MDS Queue: Analysing the Latency Performance of Erasure Codes.
- Author
-
Lee, Kangwook, Shah, Nihar B., Huang, Longbo, and Ramchandran, Kannan
- Subjects
- *
CLIENT/SERVER computing , *BACK up systems , *QUEUEING networks , *INFORMATION retrieval , *DATA modeling - Abstract
In order to scale economically, data centers are increasingly evolving their data storage methods from simple data replication to more powerful erasure codes, which provide the same level of reliability as replication, but at a significantly lower storage cost. In particular, it is well known that maximum-distance-separable (MDS) codes, such as Reed–Solomon codes, can achieve a target reliability with the maximum storage efficiency. While the use of codes for providing improved reliability in archival storage systems, where data is less frequently accessed (or so-called “cold data”), is well understood, the role of codes in storing more frequently accessed and active “hot data”, where latency is the key metric, is less clear. In this paper, we study data storage systems based on MDS codes through the lens of queueing theory, and term the queueing system arising under codes as an “MDS queue.” We provide lower and upper bounds on the average job latency for both centralized and decentralized versions of MDS queues. We also provide extensive simulations to corroborate our analysis as well as obtain additional insights. [ABSTRACT FROM PUBLISHER]
- Published
- 2017
- Full Text
- View/download PDF
31. Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues.
- Author
-
Shah, Nihar B., Balakrishnan, Sivaraman, Guntuboyina, Adityanand, and Wainwright, Martin J.
- Subjects
- *
PAIRED comparisons (Mathematics) , *THRESHOLDING algorithms , *STOCHASTIC analysis , *PARAMETER estimation , *PROBABILITY theory - Abstract
There are various parametric models for analyzing pairwise comparison data, including the Bradley–Terry–Luce (BTL) and Thurstone models, but their reliance on strong parametric assumptions is limiting. In this paper, we study a flexible model for pairwise comparisons, under which the probabilities of outcomes are required only to satisfy a natural form of stochastic transitivity. This class includes parametric models, including the BTL and Thurstone models as special cases, but is considerably more general. We provide various examples of models in this broader stochastically transitive class for which classical parametric models provide poor fits. Despite this greater flexibility, we show that the matrix of probabilities can be estimated at the same rate as in standard parametric models up to logarithmic terms. On the other hand, unlike in the BTL and Thurstone models, computing the minimax-optimal estimator in the stochastically transitive model is non-trivial, and we explore various computationally tractable alternatives. We show that a simple singular value thresholding algorithm is statistically consistent but does not achieve the minimax rate. We then propose and study algorithms that achieve the minimax rate over interesting sub-classes of the full stochastically transitive class. We complement our theoretical results with thorough numerical simulations. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
32. When Do Redundant Requests Reduce Latency?
- Author
-
Shah, Nihar B., Lee, Kangwook, and Ramchandran, Kannan
- Subjects
- *
DISTRIBUTED computing , *SERVER farms (Computer network management) , *DATA libraries , *APPROXIMATION theory , *COMPUTER scheduling - Abstract
Many systems possess the flexibility to serve requests in more than one way, such as distributed storage systems that store multiple copies of the data. In such systems, the latency of serving the requests may potentially be reduced by sending redundant requests: a request may be sent to more servers than needed and deemed served when the requisite number of servers complete service. Such a mechanism trades off the possibility of faster execution of the request with the increase in the load on the system. Several recent works empirically evaluate the latency performance of redundant requests in diverse settings. In this paper, we perform an analytical study of the latency performance of redundant requests, with the primary goals of characterizing under what scenarios sending redundant requests will help (and under what scenarios it will not), and of designing optimal redundant-requesting policies. We show that when service times are i.i.d. memoryless or “heavier,” and when the additional copies of already-completed jobs can be removed instantly, maximally scheduling redundant requests achieves the optimal average latency. On the other hand, when service times are i.i.d. “lighter” or when service times are memoryless and removal of jobs is not instantaneous, then not having any redundancy in the requests is optimal under high loads. Our results are applicable to arbitrary arrival processes. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
33. Distributed Secret Dissemination Across a Network.
- Author
-
Shah, Nihar B., Rashmi, K. V., and Ramchandran, Kannan
- Abstract
Shamir's (n,k) threshold secret sharing is an important component of several cryptographic protocols, such as those for secure multiparty-computation and key management. These protocols typically assume the presence of direct communication links from the dealer to all participants, in which case the dealer can directly pass the shares of the secret to each participant. In this paper, we consider the problem of secret sharing when the dealer does not have direct communication links to all the participants, and instead, the dealer and the participants form a general network. Existing methods are based on separate secure message transmissions from the dealer to each participant, requiring considerable coordination and communication in the network. We present a distributed algorithm for disseminating shares over a network, which we call the “SNEAK” algorithm, requiring each node to know only the identities of its one-hop neighbors. While SNEAK imposes a stronger condition on the network by requiring the dealer to be what we call k-propagating rather than k-connected as required by the existing solutions, we show that in addition to being distributed, it achieves significant reduction in the amount of communication and the randomness required. We also derive information-theoretic lower bounds on the amount of communication for secret sharing over networks, which may be of independent interest. [ABSTRACT FROM PUBLISHER]
- Published
- 2015
- Full Text
- View/download PDF
34. Fundamental limits on communication for oblivious updates in storage networks.
- Author
-
Nakkiran, Preetum, Shah, Nihar B., and Rashmi, K. V.
- Published
- 2014
- Full Text
- View/download PDF
35. One extra bit of download ensures perfectly private information retrieval.
- Author
-
Shah, Nihar B., Rashmi, K. V., and Ramchandran, Kannan
- Published
- 2014
- Full Text
- View/download PDF
36. The MDS queue: Analysing the latency performance of erasure codes.
- Author
-
Shah, Nihar B., Lee, Kangwook, and Ramchandran, Kannan
- Published
- 2014
- Full Text
- View/download PDF
37. Secure network coding for distributed secret sharing with low communication cost.
- Author
-
Shah, Nihar B., Rashmi, K. V., and Ramchandran, Kannan
- Published
- 2013
- Full Text
- View/download PDF
38. A piggybacking design framework for read-and download-efficient distributed storage codes.
- Author
-
Rashmi, K. V., Shah, Nihar B., and Ramchandran, Kannan
- Published
- 2013
- Full Text
- View/download PDF
39. When do redundant requests reduce latency ?
- Author
-
Shah, Nihar B., Lee, Kangwook, and Ramchandran, Kannan
- Published
- 2013
- Full Text
- View/download PDF
40. Regenerating codes for errors and erasures in distributed storage.
- Author
-
Rashmi, K. V., Shah, Nihar B., Ramchandran, Kannan, and Kumar, P. Vijay
- Abstract
Regenerating codes are a class of codes proposed for providing reliability of data and efficient repair of failed nodes in distributed storage systems. In this paper, we address the fundamental problem of handling errors and erasures at the nodes or links, during the data-reconstruction and node-repair operations. We provide explicit regenerating codes that are resilient to errors and erasures, and show that these codes are optimal with respect to storage and bandwidth requirements. As a special case, we also establish the capacity of a class of distributed storage systems in the presence of malicious adversaries. While our code constructions are based on previously constructed Product-Matrix codes, we also provide necessary and sufficient conditions for introducing resilience in any regenerating code. [ABSTRACT FROM PUBLISHER]
- Published
- 2012
- Full Text
- View/download PDF
41. Information-Theoretically Secure Regenerating Codes for Distributed Storage.
- Author
-
Shah, Nihar B., Rashmi, K. V., and Kumar, P. Vijay
- Published
- 2011
- Full Text
- View/download PDF
42. Regenerating Codes for Distributed Storage Networks.
- Author
-
Shah, Nihar B., Rashmi, K. V., Kumar, P. Vijay, and Ramchandran, Kannan
- Abstract
In a storage system where individual storage nodes are prone to failure, the redundant storage of data in a distributed manner across multiple nodes is a must to ensure reliability. Reed-Solomon codes possess the reconstruction property under which the stored data can be recovered by connecting to any k of the n nodes in the network across which data is dispersed. This property can be shown to lead to vastly improved network reliability over simple replication schemes. Also of interest in such storage systems is the minimization of the repair bandwidth, i.e., the amount of data needed to be downloaded from the network in order to repair a single failed node. Reed-Solomon codes perform poorly here as they require the entire data to be downloaded. Regenerating codes are a new class of codes which minimize the repair bandwidth while retaining the reconstruction property. This paper provides an overview of regenerating codes including a discussion on the explicit construction of optimum codes. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
43. On Minimizing Data-Read and Download for Storage-Node Recovery.
- Author
-
Shah, Nihar B.
- Abstract
We consider the problem of efficient recovery of the data stored in any individual node of a distributed storage system, from the rest of the nodes. Applications include handling failures and degraded reads. We measure efficiency in terms of the amount of data-read and the download required. To minimize the download, we focus on the minimum bandwidth setting of the `regenerating codes' model for distributed storage. Under this model, the system has a total of n nodes, and the data stored in any node must be (efficiently) recoverable from any d of the other (n-1) nodes. Lower bounds on the two metrics under this model were derived previously; it has also been shown that these bounds are achievable for the amount of data-read and download when d=n-1, and for the amount of download alone when d\neq n-1. In this paper, we complete the picture by proving the converse result, that when d\neq n-1, these lower bounds are strictly loose with respect to the amount of read required. The proof is information-theoretic, and hence applies to non-linear codes as well. We also show that under two (practical) relaxations of the problem setting, these lower bounds can be met for both read and download simultaneously. [ABSTRACT FROM PUBLISHER]
- Published
- 2013
- Full Text
- View/download PDF
44. Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions.
- Author
-
Shah, Nihar B., Rashmi, K. V., Kumar, P. Vijay, and Ramchandran, Kannan
- Subjects
- *
CODING theory , *DISTRIBUTED algorithms , *COMPUTER storage devices , *REED-Solomon codes , *ELECTRONIC data processing , *BANDWIDTHS - Abstract
Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any arbitrary k of n nodes. However regenerating codes possess in addition, the ability to repair a failed node by connecting to any arbitrary d nodes and downloading an amount of data that is typically far less than the size of the data file. This amount of download is termed the repair bandwidth. Minimum storage regenerating (MSR) codes are a subclass of regenerating codes that require the least amount of network storage; every such code is a maximum distance separable (MDS) code. Further, when a replacement node stores data identical to that in the failed node, the repair is termed as exact. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
45. Distributed Storage Codes With Repair-by-Transfer and Nonachievability of Interior Points on the Storage-Bandwidth Tradeoff.
- Author
-
Shah, Nihar B., Rashmi, K. V., Kumar, P. Vijay, and Ramchandran, Kannan
- Subjects
- *
DISTRIBUTED algorithms , *COMPUTER storage devices , *BANDWIDTHS , *MAINTENANCE , *COMPUTATIONAL complexity , *DATA encryption , *GRAPHIC methods - Abstract
Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any subset of k nodes within the n-node network. However, regenerating codes possess in addition, the ability to repair a failed node by connecting to an arbitrary subset of d nodes. It has been shown that for the case of functional repair, there is a tradeoff between the amount of data stored per node and the bandwidth required to repair a failed node. A special case of functional repair is exact repair where the replacement node is required to store data identical to that in the failed node. Exact repair is of interest as it greatly simplifies system implementation. The first result of this paper is an explicit, exact-repair code for the point on the storage-bandwidth tradeoff corresponding to the minimum possible repair bandwidth, for the case when d=n-1. This code has a particularly simple graphical description, and most interestingly has the ability to carry out exact repair without any need to perform arithmetic operations. We term this ability of the code to perform repair through mere transfer of data as repair by transfer. The second result of this paper shows that the interior points on the storage-bandwidth tradeoff cannot be achieved under exact repair, thus pointing to the existence of a separate tradeoff under exact repair. Specifically, we identify a set of scenarios which we term as “helper node pooling,” and show that it is the necessity to satisfy such scenarios that overconstrains the system. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
46. Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction.
- Author
-
Rashmi, K. V., Shah, Nihar B., and Kumar, P. Vijay
- Subjects
- *
CODING theory , *MATRICES (Mathematics) , *BANDWIDTHS , *COMPUTER networks , *INFORMATION theory , *DATA transmission systems , *DATA recovery - Abstract
Regenerating codes are a class of distributed storage codes that allow for efficient repair of failed nodes, as compared to traditional erasure codes. An [n, k, d] regenerating code permits the data to be recovered by connecting to any k of the n nodes in the network, while requiring that a failed node be repaired by connecting to any d nodes. The amount of data downloaded for repair is typically much smaller than the size of the source data. Previous constructions of exact-regenerating codes have been confined to the case n=d+1. In this paper, we present optimal, explicit constructions of (a) Minimum Bandwidth Regenerating (MBR) codes for all values of [n, k, d] and (b) Minimum Storage Regenerating (MSR) codes for all [n, k, d\geq 2k-2], using a new product-matrix framework. The product-matrix framework is also shown to significantly simplify system operation. To the best of our knowledge, these are the first constructions of exact-regenerating codes that allow the number n of nodes in the network, to be chosen independent of the other parameters. The paper also contains a simpler description, in the product-matrix framework, of a previously constructed MSR code with [n=d+1, k, d\geq 2k-1]. [ABSTRACT FROM PUBLISHER]
- Published
- 2011
- Full Text
- View/download PDF
47. Two-Sample Testing on Ranked Preference Data and the Role of Modeling Assumptions.
- Author
-
Rastogi, Charvi, Balakrishnan, Sivaraman, Shah, Nihar B., and Singh, Aarti
- Subjects
- *
DATA modeling , *TURF management , *DISCRETE choice models , *DATA analysis , *SOCIAL choice , *CROWDSOURCING - Abstract
A number of applications require two-sample testing on ranked preference data. For instance, in crowdsourcing, there is a long-standing question of whether pairwise-comparison data provided by people is distributed identically to ratings-converted-to-comparisons. Other applications include sports data analysis and peer grading. In this paper, we design twosample tests for pairwise-comparison data and ranking data. For our two-sample test for pairwise-comparison data, we establish an upper bound on the sample complexity required to correctly test whether the distributions of the two sets of samples are identical. Our test requires essentially no assumptions on the distributions. We then prove complementary lower bounds showing that our results are tight (in the minimax sense) up to constant factors. We investigate the role of modeling assumptions by proving lower bounds for a range of pairwise-comparison models (WST, MST, SST, parameter-based such as BTL and Thurstone). We also provide tests and associated sample complexity bounds for partial (or total) ranking data. Furthermore, we empirically evaluate our results via extensive simulations as well as three real-world data sets consisting of pairwise-comparisons and rankings. By applying our two-sample test on real-world pairwise-comparison data, we conclude that ratings and rankings provided by people are indeed distributed differently. [ABSTRACT FROM AUTHOR]
- Published
- 2022
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.