Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 197 for “"O-log"”.
-
Time and space tradeoffs in point location
… subdivision with n points on the plane in O(n√log n) time and store them in O(n/t) space to facilitate point location in O(log t) time, where t is an adjustable parameter. When t is a constant we get O(n) space and constant time. When t = O(n) we get constant space and O(log n) time.
-
Algorithms on Clustering, Orienteering, and Conflict -Free Coloring
… all these cases, the coloring algorithms use O(log n) colors, with high probability. We also present the first efficient deterministic algorithm for the CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using O(log 12 n) colors.
-
The Relationship Of Bedside Assessment Of Orientation And Cognition To Treatment Outcome In Moderate To Severe Traumatic Brain Injury: A Growth Curve Analysis
… of rehabilitation research. The Orientation-Log (O-log) and Cognition-Log (Cog-log) are important clinical measures used to monitor cognitive progress during treatment and previous research has shown them to be predictive of long-term outcome. This study used two-level growth curve modeling …
-
Cache Oblivious Data Structures
… This layout allows Searches to be performed in O(log n) time and in O(log n/log L) (the optimal number) cache misses. An algorithm for building this layout from a sorted array in linear time is given. One use for this layout is a heap-like implementation of the priority queue. This structure …
-
Efficient parallel computation on multiprocessors with optical interconnection networks
… maximum-finding algorithm on an LARPBS. • An O((log log n)<sup>2</sup>) time parallel selection algorithm on an LARPBS. • An O(k(log log n)<sup>2</sup>) time parallel multi-selection algorithm on an LARPBS. While studying the computation and communication properties of the LARPBS model, we find …
-
Density of the Numerators or Denominators of a Continued Fraction
… paper we improve this result as P ( n ) = O (log n) and Q ( n ) = O (log n), where it follows that P ( n )= o ( nε ) and Q ( n ) = o ( nε ) for any ε >0.
-
Inverting Permutations In Place
… we present a naive algorithm to do it using $O(\log n)$ extra bits in $O(n^2)$ time in the worst case. We then improve that algorithm, using a small bit vector, to use $O(\sqrt n)$ extra bits in $O(n \sqrt n)$ time. Using a different approach, we present an algorithm to do it using $O(\sqrt n …
-
Three-Sided Skyline Counting Queries
… of a top-open three-sided query range in O(log log n) time. We also consider a variation of the skyline problem where each of the points have some category, which we call color. An orthogonal color skyline query Q on a set of points P returns the distinct color of points on the skyline of P …
-
Parallel Efficient Secure DBSCAN Approximation
… efficient approximation of DBSCAN that takes O(log²n) parallel time and O(nlog²n) total work, breaking the quadratic barrier in Secure Multiparty implementations of DBSCAN algorithms and reducing the communication rounds asymptotically from O(n²) to O(log²n).
-
Parallel Parsing in a Multiprocessor Environment
… a string of L tokens can be parsed in O (log L) time with (L /log L) processors. The parsing algorithm uses a parenthesis-matching algorithm developed here. The parenthesis-matching algorithm can find matching of a sequence of parentheses in O (log L) time with (L /log L) processors. Thus, …
-
Dynamic Algorithms for Partially-Sorted Lists
… not adequate. Then, we solve the problem in O(k log(n)) time for queries and O(log(n)) time for updates using the tournament tree data structure, where n is the number of elements in the lists. We then introduce a layered tournament tree data structure and solve the same problem in O(log '(n) k …
-
Massively parallel algorithms for sparse graphs
… of the graph D. We establish the first O(log D)-round algorithm for connectivity, as well as the first O(log log n)- and O(log D)-round algorithms for 3-coloring, maximal matching, and maximal independent set on forest graphs. We also show that strengthening the MPC model, by allowing …
-
Approximation Algorithms for (S,T)-Connectivity Problems
… its special cases. For any $k$, we give an $O(\log k\log n)$-approximation algorithm, where $n$ denotes the number of vertices. The approximation guarantee almost matches the best approximation guarantee known for the minimum cost $k$-vertex connected spanning subgraph problem which is $O(\log …
-
Efficient private information retrieval
… known Oblivious Transfer protocol from O ((log(n))2) to O (log(n)), where n is the size of the database. Our communication-efficient Oblivious Transfer protocol is a non-interactive, single-database scheme that is generally built on Homomorphic Encryption Functions. We also introduce a new …
-
Decentralized multi-user multi-armed bandits with user dependent reward distributions
… a policy that achieves expected regret of O(log T) over a time horizon of duration T. While settings with non-zero rewards on collisions and varying reward distributions of arms across players have been considered separately in prior work, a model allowing for both has not been studied …
-
Minimum Feature Size in Proper Triangulations
… proper triangulation G of P has degradation Ω(log N). The bound holds even when any finite number of Steiner vertices may be added in the bounded face of P and on any of its edges. Together with the known O(log N) upper bound, it establishes that the worst-case optimal degradation for proper …
-
Exploiting the structure of the data in approximate nearest neighbor search
… που δεχόμαστε ως είσοδο βρίσκονται πάνω σε $\log^t n$ άγνωστες ευθείες σε κάποιο χώρο σταθερής διάστασης $d$, όπου $n$ είναι ο αριθμός των σημείων και $t$ είναι μια σταθερά. Οι ευθείες είναι κατανεμημένες ομοιόμορφα σε μια περιορισμένη μπάλα και τα σημεία είναι ομοιόμορφα κατανεμημένα πάνω σε …
-
Selectable Heaps and Their Application to Lazy Search Trees
We show the O(log n) time extract minimum function of efficient priority queues can be generalized to the extraction of the k smallest elements in O(k log(n/k)) time. We first show the heap-ordered tree selection of Kaplan et al. can be applied on the heap-ordered trees of the classic Fibonacci …
-
MPI sobre MOM para suportar log de mensagens pessimista remoto
… emergentes. Em contrapartida, as técnicas de log de mensagens possuem características que as tornam mais apropriadas no novo cenário que se estabelece. O presente trabalho consiste em uma proposta de log de mensagens pessimista remoto com checkpoint não-coordenado e a avaliação de desempenho …
-
Dynamic Data Structures for Two Dimensional Searching
… dynamic planar embedding, considers a topological subdivision of the plane induced by a planar embedding of a graph, and asks for a region that contains two given query vertices on its boundary (if one exists). The third problem, dynamic transitive closure, considers a planar acyclic …
Page 1 of 10