اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدResolving SINR Queries in a Dynamic Setting
59
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We consider a set of transmitters broadcasting simultaneously on the same frequency under the SINR model. Transmission power may vary from one transmitter to another, and a transmitters signal strength at a given point is modeled by the transmitters power divided by some constant power $alpha$ of the distance it traveled. Roughly, a receiver at a given location can hear a specific transmitter only if the transmitters signal is stronger by a specified ratio than the signals of all other transmitters combined. An SINR query is to determine whether a receiver at a given location can hear any transmitter, and if yes, which one. An approximate answer to an SINR query is such that one gets a definite YES or definite NO, when the ratio between the strongest signal and all other signals combined is well above or well below the reception threshold, while the answer in the intermediate range is allowed to be either YES or NO. We describe compact data structures that support approximate SINR queries in the plane in a dynamic context, i.e., where transmitters may be inserted and deleted over time. We distinguish between two main variants --- uniform power and non-uniform power. In both variants the preprocessing time is $O(n mathop{textrm{polylog}} n)$ and the amortized update time is $O(mathop{textrm{polylog}} n)$, while the query time is $O(mathop{textrm{polylog}} n)$ for uniform power, and randomized time $O(sqrt{n} mathop{textrm{polylog}} n)$ with high probability for non-uniform power. Finally, we observe that in the static context the latter data structure can be implemented differently, so that the query time is also $O(mathop{textrm{polylog}} n)$, thus significantly improving all previous results for this problem.
قيم البحث
اقرأ أيضاً
The Frechet distance is a popular similarity measure between curves. For some applications, it is desirable to match the curves under translation before computing the Frechet distance between them. This variant is called the Translation Invariant Fre
chet distance, and algorithms to compute it are well studied. The query version, finding an optimal placement in the plane for a query segment where the Frechet distance becomes minimized, is much less well understood. We study Translation Invariant Frechet distance queries in a restricted setting of horizontal query segments. More specifically, we preprocess a trajectory in $mathcal O(n^2 log^2 n) $ time and $mathcal O(n^{3/2})$ space, such that for any subtrajectory and any horizontal query segment we can compute their Translation Invariant Frechet distance in $mathcal O(text{polylog } n)$ time. We hope this will be a step towards answering Translation Invariant Frechet queries between arbitrary trajectories.
The it Convex Hull Membership(CHM) problem is: Given a point $p$ and a subset $S$ of $n$ points in $mathbb{R}^m$, is $p in conv(S)$? CHM is not only a fundamental problem in Linear Programming, Computational Geometry, Machine Learning and Statistics,
it also serves as a query problem in many applications e.g. Topic Modeling, LP Feasibility, Data Reduction. The {it Triangle Algorithm} (TA) cite{kalantari2015characterization} either computes an approximate solution in the convex hull, or a separating hyperplane. The {it Spherical}-CHM is a CHM, where $p=0$ and each point in $S$ has unit norm. First, we prove the equivalence of exact and approxima
Load balancing by proactively offloading users onto small and otherwise lightly-loaded cells is critical for tapping the potential of dense heterogeneous cellular networks (HCNs). Offloading has mostly been studied for the downlink, where it is gener
ally assumed that a user offloaded to a small cell will communicate with it on the uplink as well. The impact of coupled downlink-uplink offloading is not well understood. Uplink power control and spatial interference correlation further complicate the mathematical analysis as compared to the downlink. We propose an accurate and tractable model to characterize the uplink SINR and rate distribution in a multi-tier HCN as a function of the association rules and power control parameters. Joint uplink-downlink rate coverage is also characterized. Using the developed analysis, it is shown that the optimal degree of channel inversion (for uplink power control) increases with load imbalance in the network. In sharp contrast to the downlink, minimum path loss association is shown to be optimal for uplink rate. Moreover, with minimum path loss association and full channel inversion, uplink SIR is shown to be invariant of infrastructure density. It is further shown that a decoupled association---employing differing association strategies for uplink and downlink---leads to significant improvement in joint uplink-downlink rate coverage over the standard coupled association in HCNs.
Let $mathcal{P}$ be a polygonal domain of $h$ holes and $n$ vertices. We study the problem of constructing a data structure that can compute a shortest path between $s$ and $t$ in $mathcal{P}$ under the $L_1$ metric for any two query points $s$ and $
t$. To do so, a standard approach is to first find a set of $n_s$ gateways for $s$ and a set of $n_t$ gateways for $t$ such that there exist a shortest $s$-$t$ path containing a gateway of $s$ and a gateway of $t$, and then compute a shortest $s$-$t$ path using these gateways. Previous algorithms all take quadratic $O(n_scdot n_t)$ time to solve this problem. In this paper, we propose a divide-and-conquer technique that solves the problem in $O(n_s + n_t log n_s)$ time. As a consequence, we construct a data structure of $O(n+(h^2log^3 h/loglog h))$ size in $O(n+(h^2log^4 h/loglog h))$ time such that each query can be answered in $O(log n)$ time.
We study metric data structures for curves in doubling spaces, such as trajectories of moving objects in Euclidean $mathbb{R}^d$, where the distance between two curves is measured using the discrete Frechet distance. We design data structures in an e
mph{asymmetric} setting where the input is a curve (or a set of $n$ curves) each of complexity $m$ and the queries are with curves of complexity $kll m$. We show that there exist approximate data structures that are independent of the input size $N = d cdot n cdot m$ and we study how to maintain them dynamically if the input is given in the stream. Concretely, we study two types of data structures: (i) distance oracles, where the task is to store a compressed version of the input curve, which can be used to answer queries for the distance of a query curve to the input curve, and (ii) nearest-neighbor data structures, where the task is to preprocess a set of input curves to answer queries for the input curve closest to the query curve. In both cases we are interested in approximation. For curves embedded in Euclidean $mathbb{R}^d$ with constant $d$, our distance oracle uses space in $mathcal{O}((k log(epsilon^{-1}) epsilon^{-d})^k)$ ($epsilon$ is the precision parameter). The oracle performs $(1+epsilon)$-approximate queries in time in $mathcal{O}(k^2)$ and is deterministic. We show how to maintain this distance oracle in the stream using polylogarithmic additional memory. In the stream, we can dynamically answer distance queries to the portion of the stream seen so far in $mathcal{O}(k^4 log^2 m)$ time. We apply our techniques to the second problem, approximate near neighbor (ANN) data structures, and achieve an exponential improvement in the dependency on the complexity of the input curves compared to the state of the art.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
