Evaluating proximity relations under uncertainty

Zhengdao Xu, Hans Arno Jacobsen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations


For location-based services it is often essential to efficiently process proximity relations among mobile objects, such as to establish whether a group of friends or family members are within a given distance of each other. A severe limitation in accurately establishing such relations is the inaccuracy of dynamically obtained position data, the point in time, and the frequency with which the position data is collected. In this paper, we use the common model of interpreting the unknown position of an object by a probability distribution centered around the last know position of the object. While this approach is straight forward, it poses severe difficulties for establishing the truth or falsehood of the proximity relation. To address this problem, we analytically quantify the lower and upper bounds of the size of the smallest circle that covers the mobile objects involved in the proximity relation. Based on this result we propose two novel algorithms that closely monitor the relation at low location update cost. Furthermore, we develop a cost-effective estimation technique to determine the probability of match for a given proximity relation.

Original languageEnglish
Title of host publication23rd International Conference on Data Engineering, ICDE 2007
Number of pages10
StatePublished - 2007
Externally publishedYes
Event23rd International Conference on Data Engineering, ICDE 2007 - Istanbul, Turkey
Duration: 15 Apr 200720 Apr 2007

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Conference23rd International Conference on Data Engineering, ICDE 2007


Dive into the research topics of 'Evaluating proximity relations under uncertainty'. Together they form a unique fingerprint.

Cite this