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

Ke Yi

Ke Yi 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 AlgorithmsCryptography and SecurityDatabasesComputational GeometryComputer Visioncs.CYDistributed, Parallel, and Cluster ComputingNetworking and Internet Architecture

Catalog footprint

What is connected

11works
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

11 published item(s)

preprint2026arXiv

Adaptive Privacy Budgeting

We study the problem of adaptive privacy budgeting under generalized differential privacy. Consider the setting where each user $i\in [n]$ holds a tuple $x_i\in U:=U_1\times \dotsb \times U_T$, where $x_i(l)\in U_l$ represents the $l$-th component of their data. For every $l\in [T]$ (or a subset), an untrusted analyst wishes to compute some $f_l(x_1(l),\dots,x_n(l))$, while respecting the privacy of each user. For many functions $f_l$, data from the users are not all equally important, and there is potential to use the privacy budgets of the users strategically, leading to privacy savings that can be used to improve the utility of later queries. In particular, the budgeting should be adaptive to the outputs of previous queries, so that greater savings can be achieved on more typical instances. In this paper, we provide such an adaptive budgeting framework, with various applications demonstrating its applicability.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

OneDConv: Generalized Convolution For Transform-Invariant Representation

Convolutional Neural Networks (CNNs) have exhibited their great power in a variety of vision tasks. However, the lack of transform-invariant property limits their further applications in complicated real-world scenarios. In this work, we proposed a novel generalized one dimension convolutional operator (OneDConv), which dynamically transforms the convolution kernels based on the input features in a computationally and parametrically efficient manner. The proposed operator can extract the transform-invariant features naturally. It improves the robustness and generalization of convolution without sacrificing the performance on common images. The proposed OneDConv operator can substitute the vanilla convolution, thus it can be incorporated into current popular convolutional architectures and trained end-to-end readily. On several popular benchmarks, OneDConv outperforms the original convolution operation and other proposed models both in canonical and distorted images.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Infnote: A Decentralized Information Sharing Platform Based on Blockchain

Internet censorship has been implemented in several countries to prevent citizens from accessing information and to suppress discussion of specific topics. This paper presents Infnote, a platform that helps eliminate the problem of sharing content in these censorship regimes. Infnote is a decentralized information sharing system based on blockchain and peer-to-peer network, aiming to provide an easy-to-use medium for users to share their thoughts, insights and views freely without worrying about data tampering and data loss. Infnote provides a solution that is able to work on any level of Internet censorship. Infnote uses multi-chains architecture to support various independent applications or different functions in an application.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Nearest-Neighbor Searching Under Uncertainty II

Nearest-neighbor search, which returns the nearest neighbor of a query point in a set of points, is an important and widely studied problem in many fields, and it has wide range of applications. In many of them, such as sensor databases, location-based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest-neighbor queries in a probabilistic framework in which the location of each input point is specified as a probability distribution function. We present efficient algorithms for - computing all points that are nearest neighbors of a query point with nonzero probability; and - estimating the probability of a point being the nearest neighbor of a query point, either exactly or within a specified additive error.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Space Complexity of 2-Dimensional Approximate Range Counting

We study the problem of $2$-dimensional orthogonal range counting with additive error. Given a set $P$ of $n$ points drawn from an $n\times n$ grid and an error parameter $\eps$, the goal is to build a data structure, such that for any orthogonal range $R$, it can return the number of points in $P\cap R$ with additive error $\eps n$. A well-known solution for this problem is the {\em $\eps$-approximation}, which is a subset $A\subseteq P$ that can estimate the number of points in $P\cap R$ with the number of points in $A\cap R$. It is known that an $\eps$-approximation of size $O(\frac{1}{\eps} \log^{2.5} \frac{1}{\eps})$ exists for any $P$ with respect to orthogonal ranges, and the best lower bound is $Ω(\frac{1}{\eps} \log \frac{1}{\eps})$. The $\eps$-approximation is a rather restricted data structure, as we are not allowed to store any information other than the coordinates of the points in $P$. In this paper, we explore what can be achieved without any restriction on the data structure. We first describe a simple data structure that uses $O(\frac{1}{\eps}(\log^2\frac{1} {\eps} + \log n) )$ bits and answers queries with error $\eps n$. We then prove a lower bound that any data structure that answers queries with error $\eps n$ must use $Ω(\frac{1}{\eps}(\log^2\frac{1} {\eps} + \log n) )$ bits. Our lower bound is information-theoretic: We show that there is a collection of $2^{Ω(n\log n)}$ point sets with large {\em union combinatorial discrepancy}, and thus are hard to distinguish unless we use $Ω(n\log n)$ bits.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Tracking the Frequency Moments at All Times

The traditional requirement for a randomized streaming algorithm is just {\em one-shot}, i.e., algorithm should be correct (within the stated $\eps$-error bound) at the end of the stream. In this paper, we study the {\em tracking} problem, where the output should be correct at all times. The standard approach for solving the tracking problem is to run $O(\log m)$ independent instances of the one-shot algorithm and apply the union bound to all $m$ time instances. In this paper, we study if this standard approach can be improved, for the classical frequency moment problem. We show that for the $F_p$ problem for any $1 < p \le 2$, we actually only need $O(\log \log m + \log n)$ copies to achieve the tracking guarantee in the cash register model, where $n$ is the universe size. Meanwhile, we present a lower bound of $Ω(\log m \log\log m)$ bits for all linear sketches achieving this guarantee. This shows that our upper bound is tight when $n=(\log m)^{O(1)}$. We also present an $Ω(\log^2 m)$ lower bound in the turnstile model, showing that the standard approach by using the union bound is essentially optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Equivalence between Priority Queues and Sorting in External Memory

A priority queue is a fundamental data structure that maintains a dynamic ordered set of keys and supports the followig basic operations: insertion of a key, deletion of a key, and finding the smallest key. The complexity of the priority queue is closely related to that of sorting: A priority queue can be used to implement a sorting algorithm trivially. Thorup \cite{thorup2007equivalence} proved that the converse is also true in the RAM model. In particular, he designed a priority queue that uses the sorting algorithm as a black box, such that the per-operation cost of the priority queue is asymptotically the same as the per-key cost of sorting. In this paper, we prove an analogous result in the external memory model, showing that priority queues are computationally equivalent to sorting in external memory, under some mild assumptions. The reduction provides a possibility for proving lower bounds for external sorting via showing a lower bound for priority queues.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Building Wavelet Histograms on Large Data in MapReduce

MapReduce is becoming the de facto framework for storing and processing massive data, due to its excellent scalability, reliability, and elasticity. In many MapReduce applications, obtaining a compact accurate summary of data is essential. Among various data summarization tools, histograms have proven to be particularly important and useful for summarizing data, and the wavelet histogram is one of the most widely used histograms. In this paper, we investigate the problem of building wavelet histograms efficiently on large datasets in MapReduce. We measure the efficiency of the algorithms by both end-to-end running time and communication cost. We demonstrate straightforward adaptations of existing exact and approximate methods for building wavelet histograms to MapReduce clusters are highly inefficient. To that end, we design new algorithms for computing exact and approximate wavelet histograms and discuss their implementation in MapReduce. We illustrate our techniques in Hadoop, and compare to baseline solutions with extensive experiments performed in a heterogeneous Hadoop cluster of 16 nodes, using large real and synthetic datasets, up to hundreds of gigabytes. The results suggest significant (often orders of magnitude) performance improvement achieved by our new algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks

We show that randomization can lead to significant improvements for a few fundamental problems in distributed tracking. Our basis is the {\em count-tracking} problem, where there are $k$ players, each holding a counter $n_i$ that gets incremented over time, and the goal is to track an $\eps$-approximation of their sum $n=\sum_i n_i$ continuously at all times, using minimum communication. While the deterministic communication complexity of the problem is $Θ(k/\eps \cdot \log N)$, where $N$ is the final value of $n$ when the tracking finishes, we show that with randomization, the communication cost can be reduced to $Θ(\sqrt{k}/\eps \cdot \log N)$. Our algorithm is simple and uses only O(1) space at each player, while the lower bound holds even assuming each player has infinite computing power. Then, we extend our techniques to two related distributed tracking problems: {\em frequency-tracking} and {\em rank-tracking}, and obtain similar improvements over previous deterministic algorithms. Both problems are of central importance in large data monitoring and analysis, and have been extensively studied in the literature.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Verifying Computations with Streaming Interactive Proofs

When computation is outsourced, the data owner would like to be assured that the desired computation has been performed correctly by the service provider. In theory, proof systems can give the necessary assurance, but prior work is not sufficiently scalable or practical. In this paper, we develop new proof protocols for verifying computations which are streaming in nature: the verifier (data owner) needs only logarithmic space and a single pass over the input, and after observing the input follows a simple protocol with a prover (service provider) that takes logarithmic communication spread over a logarithmic number of rounds. These ensure that the computation is performed correctly: that the service provider has not made any errors or missed out some data. The guarantee is very strong: even if the service provider deliberately tries to cheat, there is only vanishingly small probability of doing so undetected, while a correct computation is always accepted. We first observe that some theoretical results can be modified to work with streaming verifiers, showing that there are efficient protocols for problems in the complexity classes NP and NC. Our main results then seek to bridge the gap between theory and practice by developing usable protocols for a variety of problems of central importance in streaming and database processing. All these problems require linear space in the traditional streaming model, and therefore our protocols demonstrate that adding a prover can exponentially reduce the effort needed by the verifier. Our experimental results show that our protocols are practical and scalable.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Clustering with diversity

We consider the {\em clustering with diversity} problem: given a set of colored points in a metric space, partition them into clusters such that each cluster has at least $\ell$ points, all of which have distinct colors. We give a 2-approximation to this problem for any $\ell$ when the objective is to minimize the maximum radius of any cluster. We show that the approximation ratio is optimal unless $\mathbf{P=NP}$, by providing a matching lower bound. Several extensions to our algorithm have also been developed for handling outliers. This problem is mainly motivated by applications in privacy-preserving data publication.

0 citations0 reviewsNo code linkedOpen access