Finding "Mobile" Data
|
Finding "Mobile" Data | |
[Home] [People] [Publications]
Last update: January 21 2011 10:43:05.
Disclaimer: this page is under constant construction. Comments and questions will be appreciated. Please send them to
In today's distributed information systems, we are frequently looking for "some information" or "some entity". However, we do not always know the exact location of the information. Instead, we might have some a-priori knowledge about possible locations and the probabilities of the information residing in the locations. We imagine the subject of the search as a "mobile data" that may move from one location to another location and thus creating some uncertainty for its exact whereabout. Our goal is to design, analyze, implement, and evaluate efficient searching strategies for the mobile data while taking advantage of any partial knowledge of its whereabout. Our optimization goals are to find the data as fast as possible while querying as few as possible locations. We seek strategies for finding one mobile data, many mobile datum, or one out of many mobile datum.
M≥1 tokens, T1,...,TM, are placed in N≥1 boxes B1,...,BN, and then the boxes are locked. Each token Ti is placed in one of the boxes and is associated with a vector of probabilities pi1,...,piN where pij is the probability of token Ti to be placed at box Bj. Each token may be associated with a different vector. All the probabilities are independent and ∑j=1N pij=1 for each 1≤i≤M. A searcher is looking for either all the tokens, some of them, or one of them. When the searcher unlocks box Bj, it collects all the tokens in this box. The cost of unlocking box Bj is cj. Without loss of generality, it is assumed that ∑j=1N cj=1. The searcher conducts its search in rounds and must accomplish its task in at most D(≥1) rounds. In each round, the searcher may unlock any set of locked boxes concurrently. The optimization goal is to minimize the expected cost of unlocking boxes until the task is accomplished.
This problem attracted a lot of attention in recent years for the special case of one user (M=1) in which the costs of unlocking boxes are the same. This case can be solved optimally via an efficient (Θ(DN)) polynomial time dynamic programming scheme for any number of rounds D. The case of different boxes having different unlocking costs is strongly NP-hard even for D=2 and pi=ci for all i. The conference call problem for M=2 is also NP hard.
Disclaimer: The copyrights of all papers below belong to original publisher and authors. By downloading the paper, one acknowledges the copyright agreement with the corresponding publisher and authors under copyright law.
Abstract Mobile users are roaming in a zone of cells in a cellular network system. The probabilities of each user residing in each cell are known, and all probabilities are independent. The task is to find any one, or all, of the users, by paging the cells in a predetermined number of rounds. In each round, any subset of the cells can be paged. When a cell is paged, the list of users in it is returned. The paging process terminates when the required user(s) are found. The objective is to minimize the expected number of paged cells. Finding any one user is known as the yellow page problem, and finding all users is known as the conference call problem. The conference call problem has been proved NP-hard, and a polynomial time approximation scheme exists. We study both problems in a unified framework. We introduce three methods for computing the paging cost. We give a hierarchical classification of users. For certain classes of users, we either provide polynomial time optimal solutions, or provide relatively efficient exponential time solutions. We design a family of twelve fast greedy heuristics that generate competitive paging strategies. We implement optimal algorithms and non-optimal heuristics. We test the performance of our greedy heuristics on many patterns of input data with different parameters. We select the best heuristics for both problems based on our simulation. We evaluate their performances on randomly generated Zipf and uniform data and on real user data.
Abstract A token is hidden in one of several boxes and then the boxes are locked. The probability
of placing the token in each of the boxes is known. A searcher is looking for the token by
unlocking boxes where each box is associated with an unlocking cost. The searcher conducts
its search in rounds and must find the token in a predetermined number of rounds. In each
round, the searcher may unlock any set of locked boxes concurrently. The optimization goal is
to minimize the expected cost of unlocking boxes until the token is found. The motivation and
main application of this game is the task of paging a mobile user (token) who is roaming in a zone
of cells (boxes) in a Cellular Network system. Here, the unlocking costs reflect cell congestions
and the placing probabilities represent the likelihood of the user residing in particular cells.
Another application is the task of finding some data (token) that may be known to one of the
sensors (boxes) of a Sensor Network. Here, the unlocking costs reflect the energy consumption
of querying sensors and the placing probabilities represent the likelihood of the data being found
in particular sensors. In general, we call mobile data any entity that has to be searched for.
The special case, in which all the boxes have equal unlocking costs has been well studied in
recent years and several optimal polynomial time solutions exist. To the best of our knowledge,
this paper is the first to study the general problem in which each box may be associated with
a different unlocking cost. We first present three special interesting and important cases for
which optimal polynomial time algorithms exist: (i) There is no a priori knowledge about the
location of the token and therefore all the placing probabilities are the same. (ii) There are
no delay constraints so in each round only one box is unlocked. (iii) The token is atypical in
the sense that it is more likely to be placed in boxes whose unlocking cost is low. Next, we
consider the case of a typical token for which the unlocking cost of any box is proportional to
the probability of placing the token in this box. We show that computing the optimal strategy
is strongly NP-Hard for any number of unlocking rounds, we provide a PTAS algorithm, and
analyze a greedy solution. We propose a natural dynamic programming heuristic that unlocks
the boxes in a non-increasing order of the ratio probability over cost. For two rounds, we
prove that this strategy is an 8/7≈1.143-approximation solution for an arbitrary token and a
~1.108-approximation for a typical token and that both bounds are tight. We conduct
simulations in the application of Cellular Networks, which show that for any number of rounds
the approximation factor is even less than 8/7. We test our algorithms on random data (that
either follows the Zipf distribution or the uniform distribution) and on "real" data that includes
171929 appearances of 996 users in 5625 cells. The results indicate that our algorithms perform
remarkably better than their guaranteed theoretical bounds.
Abstract A mobile user is roaming in a zone composed of
many cells in a cellular network system. When a call arrives, the
system pages the user in these cells since the user never reports
its location unless it leaves the zone. Each cell is associated with
a positive value which is the probability that the user resides in
this cell. A delay constraint requires the user to be found within a
predetermined number of paging rounds where in each round a
subset of the cells is paged. The goal is to design a paging strategy
that minimizes the expected number of paged cells until the user
is found. Optimal solutions based on dynamic programming are
known. The running time of former implementations is quadratic
in the number of cells and linear in the number of rounds. We
introduce two implementations whose running times are also
linear in the number of cells, by proving that the dynamic
programming formulation satisfies properties (like the Monge
property) that enable us to use various dynamic programming
speed-up techniques. We also propose a new heuristic of almost
linear complexity that outperforms a known linear complexity
heuristic while running faster when the number of rounds is far
less than the number of cells. Our comprehensive simulations
compare the non-optimal heuristics with the optimal solutions,
demonstrating the trade-off between optimality and running time
efficiency as well as implementation simplicity.
Abstract A token is hidden in one out of n boxes following some known probability distribution and then all the boxes are locked. The goal of a searcher is to find the token in at most D≤N rounds by opening as few boxes as possible, where in each round any set of boxes may be opened. We design and analyze strategies for a searcher who does not know the exact values of the probabilities associated with the locked boxes. Instead, the searcher might know only the complete order or a partial order of the probabilities, or ranges in which these probabilities fall. We show that with limited information the searcher can find the token without opening significantly more boxes compared to a searcher who has full knowledge. This problem is equivalent to finding mobile users (tokens) in cellular networks (boxes) and finding data (tokens) in sensor networks (boxes).
visits since October 10, 2008.
Last update: January 21 2011 10:43:05.