Catalogue Search | MBRL
Are you sure you want to remove the book from the shelf?
{{itemTitle}}
16
result(s) for
"Atallah, Mikhail J"
Sort by:
A Scheme for Collaboratively Processing Nearest Neighbor Queries in Oblivious Storage
Security concerns are a substantial impediment to the wider deployment of cloud storage. There are two main concerns on the confidentiality of outsourced data: i) protecting the data, and ii) protecting the access pattern (i.e., which data is being accessed). To mitigate these concerns, schemes for Oblivious Storage (OS) have been proposed. In OS, the data owner outsources a key-value store to a cloud server, and then can later execute get, put, and remove queries, by collaboration with the server; furthermore, both the data and the access pattern are hidden from the server. In this paper, we extend the semantics of OS by proposing an oblivious index that supports nearest neighbor queries. That is, finding the nearest keys to the query in the key-value store. Our proposed index structure for supporting nearest-neighbor has similar performance bounds to previous OS schemes that did not support nearest-neighbor, in terms of client storage, server storage and rounds of communication.
Journal Article
Outsourcing Manufacturing: Secure Price-Masking Mechanisms for Purchasing Component Parts
This paper develops and tests a privacy‐preserving business process that supports the selection of a contract manufacturer by an original equipment manufacturer (OEM), and the determination of whether the OEM or the chosen contract manufacturer will procure each of the components to be used in the manufacture of the OEM's branded product. Our “secure price‐masking (SPM)” technology contributes to procurement theory and practice in four significant ways: First, it preserves the privacy of every party's individual component prices. Second, SPM assures that the contract manufacturers will bid their own private purchase cost (i.e., not add a margin to their cost). Third, SPM is not invertible; i.e., none of the participants can “solve” for the private inputs of any other participant based on its own inputs and the outputs provided to it by SPM. Fourth, the posterior distribution of any other participant's private inputs is practically indistinguishable from its prior distribution. We also describe the results of a proof‐of‐concept implementation.
Journal Article
Reliable detection of episodes in event sequences
Suppose one wants to detect bad or suspicious subsequences in event sequences. Whether an observed pattern of activity (in the form of a particular subsequence) is significant and should be a cause for alarm depends on how likely it is to occur fortuitously. A long-enough sequence of observed events will almost certainly contain any subsequence, and setting thresholds for alarm is an important issue in a monitoring system that seeks to avoid false alarms. Suppose a long sequence, T, of observed events contains a suspicious subsequence pattern, S, within it, where the suspicious subsequence S consists of m events and spans a window of size w within T. We address the fundamental problem: Is a certain number of occurrences of a particular subsequence unlikely to be generated by randomness itself (i.e. indicative of suspicious activity)? If the probability of an occurrence generated by randomness is high and an automated monitoring system flags it as suspicious anyway, then such a system will suffer from generating too many false alarms. This paper quantifies the probability of such an S occurring in T within a window of size w, the number of distinct windows containing S as a subsequence, the expected number of such occurrences, its variance, and establishes its limiting distribution that allows setting up an alarm threshold so that the probability of false alarms is very small. We report on experiments confirming the theory and showing that we can detect bad subsequences with low false alarm rate. [PUBLICATION ABSTRACT]
Journal Article
Efficient parallel algorithms for string editing and related problems
The string editing problem for input strings $x$ and $y$ consists of transforming $x$ into $y$ by performing a series of weighted edit operations on $x$ of overall minimum cost. An edit operation on $x$ can be the deletion of a symbol from $x$, the insertion of a symbol in $x$ or the substitution of a symbol of $x$ with another symbol. This problem has a well-known $O(|x||y|)$ time-sequential solution. Efficient PRAM parallel algorithms for the string editing problem are given. If $m = \\min (|x|,|y|)$ and $n = \\max (|x|,|y|)$, then the CREW bound is $O(\\log m \\log n)$ time with $O({{mn} / {\\log m}})$ processors. The CROW bound is $O(\\log n(\\log \\log m)^{2})$ time with $O(mn/ \\log \\log m)$ processors. In all algorithms, space is $O(mn)$.
Journal Article
Cascading divide-and-conquer: a technique for designing parallel algorithms
Techniques for parallel divide-and-conquer are presented, resulting in improved parallel algorithms for a number of problems. The problems for which improved algorithms are given include segment intersection detection, trapezoidal decomposition, and planar point location. Efficient parallel algorithms are algo given for fractional cascading, three-dimensional maxima, two-set dominance counting, and visibility from a point. All of the algorithms presented run in $O(\\log n)$ time with either a linear or a sublinear number of processors in the CREW PRAM model.
Journal Article
Efficient solutions to some transportation problems with applications to minimizing robot arm travel
We give efficient solutions to transportation problems motivated by the following robotics problem. A robot arm has the task of rearranging $m$ objects between $n$ stations in the plane. Each object is initially at one of these $n$ stations and needs to be moved to another station. The robot arm consists of a single link that rotates about a fixed pivot. The link can extend in and out (like a telescope) so that its length is a variable. At the end of this \"telescoping\" link lies a gripper that is capable of grasping any one of the $m$ given objects (the gripper cannot be holding more than one object at the same time). The robot arm must transport each of the $m$ objects to its destination and come back to where it started. Since the problem of scheduling the motion of the gripper so as to minimize the total distance traveled is NP-hard, we focus on the problem of minimizing only the total angular motion (rotation of the link about the pivot), or only the telescoping motion. We give algorithms for two different modes of operation; (i) No-drops. No object can be dropped before its destination is reached. (ii) With-drops. Any object can be dropped at any number of intermediate points. Our algorithm for case (i) runs in $O(m + n\\log n)$ time for angular motion and in $O(m + n\\alpha (n))$ time for telescoping motion. Our algorithm for case (ii) runs in $O(m + n)$ time for angular motion and with the same time bound for telescoping motion. The most interesting problem turns out to be that of minimizing angular motion for the with-drops mode of operation.
Journal Article
Finding the Cyclic Index of an Irreducible, Nonnegative Matrix
The cyclic index $\\delta $ of an irreducible nonnegative square matrix is the number of eigenvalues of maximum modulus of that matrix. If $\\delta = 1$, the matrix is said to be primitive. The notions of primitivity and cyclic index play an important role in the theory of nonnegative matrices. In the context of discrete Markov chains, the words \"period\" and \"aperiodic\" are sometimes used in place of \"cyclic index\" and \"primitive\", respectively. It is known how to test an irreducible nonnegative square matrix for primitivity, but there is no known practical method for finding the cyclic index $\\delta $ in the general case. This paper presents a time-optimal algorithm for finding $\\delta $.
Journal Article