<p>Collecting user data is crucial for advancing machine learning, social science, and government policies, but the privacy of the users whose data is being collected is a growing concern. {\em Differential Privacy (DP)} has emerged as the most standard notion for privacy protection with robust mathematical guarantees. Analyzing such massive amounts of data in a privacy-preserving manner motivates the need to study differentially-private algorithms that are also super-efficient.  </p> <p><br></p> <p>This thesis initiates a systematic study of differentially-private sublinear-time and sublinear-space algorithms. The contributions of this thesis are two-fold. First, we design some of the first differentially private sublinear algorithms for many fundamental problems. Second, we develop general DP techniques for designing differentially-private sublinear algorithms. </p> <p><br></p> <p>We give the first DP sublinear algorithm for clustering by generalizing a subsampling framework from the non-DP sublinear-time literature. We give the first DP sublinear algorithm for estimating the maximum matching size. Our DP sublinear algorithm for estimating the average degree of the graph achieves a better approximation than previous works. We give the first DP algorithm for releasing $L_2$-heavy hitters in the sliding window model and a pure $L_1$-heavy hitter algorithm in the same model, which improves upon previous works.  </p> <p><br></p> <p>We develop general techniques that address the challenges of designing sublinear DP algorithms. First, we introduce the concept of Coupled Global Sensitivity (CGS). Intuitively, the CGS of a randomized algorithm generalizes the classical  notion of global sensitivity of a function, by considering a coupling of the random coins of the algorithm when run on neighboring inputs. We show that one can achieve pure DP by adding Laplace noise proportional to the CGS of an algorithm. Second, we give a black box DP transformation for a specific class of approximation algorithms. We show that such algorithms can be made differentially private without sacrificing accuracy, as long as the function has small global sensitivity. In particular, this transformation gives rise to sublinear DP algorithms for many problems, including triangle counting, the weight of the minimum spanning tree, and norm estimation.</p>

No description available.

No description available.

This thesis presents a data structure for the interactive editing of logic diagrams by means of a storage graphics terminal. It presents an overview of Computer-Aided Design of digital systems, and outlines the requirements of an interactive graphics system. The use of sequential list, hashing, binary tree, and linked list data structures are evaluated, and the data structure is formulated, which includes a combination of linked lists, binary trees, and sequential lists. An illustrative example is presented, along with recommendations for further study. / M.S.

This dissertation deals with the application of efficient data structures and hashing algorithms to the problems of textual information storage and retrieval. We have developed static and dynamic techniques for handling large dictionaries, inverted lists, and optimizations applied to ranking algorithms. We have carried out an experiment called REVTOLC that demonstrated the efficiency and applicability of our algorithms and data structures. Also, the REVTOLC experiment revealed the effectiveness and ease of use of advanced information retrieval methods, namely extended Boolean (p-norm), vector, and vector with probabilistic feedback methods. We have developed efficient static and dynamic data structures and linear algorithms to find a class of minimal perfect hash functions for the efficient implementation of dictionaries, inverted lists, and stop lists. Further, we have developed a linear algorithm that produces order preserving minimal perfect hash functions. These data structures and algorithms enable much faster indexing of textual data and faster retrieval of best match documents using advanced information retrieval methods. Finally, we summarize our research findings and some open problems that are worth further investigation. / Ph. D.

The DIRECT (DIviding RECTangles) algorithm JONESJOTi, a variant of Lipschitzian methods for bound constrained global optimization, has been applied to the optimal transmitter placement for indoor wireless systems. Power coverage and BER (bit error rate) are considered as two criteria for optimizing locations of a specified number of transmitters across the feasible region of the design space. The performance of a DIRECT implementation in such applications depends on the characteristics of the objective function, the problem dimension, and the desired solution accuracy. Implementations with static data structures often fail in practice because of unpredictable memory requirements. This is especially critical in S⁴W (Site-Specific System Simulator for Wireless communication systems), where the DIRECT optimization is just one small component connected to a parallel 3D propagation ray tracing modeler running on a 200-node Beowulf cluster of Linux workstations, and surrogate functions for a WCDMA (wideband code division multiple access) simulator are also used to estimate the channel performance. Any component failure of this large computation would abort the entire design process. To make the DIRECT global optimization algorithm efficient and robust, a set of dynamic data structures is proposed here to balance the memory requirements with execution time, while simultaneously adapting to arbitrary problem size. The focus is on design issues of the dynamic data structures, related memory management strategies, and application issues of the DIRECT algorithm to the transmitter placement optimization for wireless communication systems. Results for two indoor systems are presented to demonstrate the effectiveness of the present work. / Master of Science

<p dir="ltr">Continuous optimization is a fundamental topic both in theoretical computer science and applications of machine learning. Meanwhile, an important idea in the development modern algorithms it the use of randomness to achieve empirical speedup and improved theoretical runtimes. Stochastic gradient descent (SGD) and matrix-multiplication time linear program solvers [1] are two important examples of such achievements. Matrix sketching and related ideas provide a theoretical framework for the behavior of random matrices and vectors that arise in these algorithms, thereby provide a natural way to better understand the behavior of such randomized algorithms. In this dissertation, we consider three general problems in this area.</p>

Computer representation of the continuous two-dimensional features on a map is complicated by the spatial properties not found in typical alphanumeric data. We have designed an entity-oriented relational system for representing the cartographic data, using the concept of spatial data structures. Each geographic entity such as a region, road, or city is represented by a set of relations describing its properties, its related entities, and all the relationships among them. The thesis presents the description of the first experimental cartographic information system based on these concepts to store and retrieve watershed data for a portion of the Wise county in the state of Virginia. The thesis describes the logical structure of the database, the physical structures in memory and on the dist, a guery language interpreter which is used to access the information in the database, and a memory management scheme to transfer the structures back and forth between memory and secondary device. / Master of Science

An interactive color graphics layout editor for VLSI has been implemented on the IBM PC. The software, PC-ICICLE, is written in Microsoft PASCAL and the 8086/88 Assembly Language under the DOS 2.0 environment. The basic hardware requirement is the standard configuration of the IBM PC with 256K bytes, and color graphics monitor and adapter. Without the need for any special hardware, PC-ICICLE makes layout editors more readily available to VLSI chip designers. PC-ICICLE has also been executed on the IBM PC-XT, IBM PC-AT, and Zenith's IBM compatible PC without any modifications. / Master of Science

In Chapter 2, several other relational database systems will be reviewed. The primary goal of each analysis will be to identify the logical and physical approaches to data representation, as well as the user interface. Chapters 3 and 4 identify the physical and logical structure of the experimental disk-resident spatial information system developed for this project. As will be seen, this experimental system combines features of existing relational databases with new approaches to represent and manipulate information in a database. The Query Language Interpreter will be presented in Chapter 5. Through the interpreter, a database user can issue a variety of commands to perform database operations, as well as create sophisticated program control structures. Chapters 6-8 discuss the security, integrity, and recovery aspects of the disk-resident system. During the development of this project, various implementation problems were encountered. These problems and solutions are presented in Chapter 9. Chapter 10 discusses the performance of the disk-resident system. Statistics are presented comparing how the database commands performed when run under a variety of test environments. Chapter 11 uses the results from earlier chapters to draw conclusions concerning the disk-resident system and presents some directions for future work. Following the bibliography are related appendices that illustrate the various types of files recognized by the query language interpreter. / Master of Science