NDLI: Interval reverse nearest neighbor queries on uncertain data with Markov correlations

Content Provider	IEEE Xplore Digital Library
Author	Chuanfei Xu Yu Gu Lei Chen Jianzhong Qiao Ge Yu
Copyright Year	2013
Description	Author affiliation: Dept. of Inf. Sci. & Eng., Northeastern Univ., Shenyang, China (Chuanfei Xu; Yu Gu; Jianzhong Qiao; Ge Yu) \|\| Dept. of Comput. Sci. & Eng., Hong Kong Univ. of Sci. & Technol., Hong Kong, China (Lei Chen)
Abstract	Nowadays, many applications return to the user a set of results that take the query as their nearest neighbor, which are commonly expressed through reverse nearest neighbor (RNN) queries. When considering moving objects, users would like to find objects that appear in the RNN result set for a period of time in some real-world applications such as collaboration recommendation and anti-tracking. In this work, we formally define the problem of interval reverse nearest neighbor (IRNN) queries over moving objects, which return the objects that maintain nearest neighboring relations to the moving query objects for the longest time in the given interval. Location uncertainty of moving data objects and moving query objects is inherent in various domains, and we investigate objects that exhibit Markov correlations, that is, each object's location is only correlated with its own location at previous timestamp while being independent of other objects. There exists the efficiency challenge for answering IRNN queries on uncertain moving objects with Markov correlations since we have to retrieve not only all the possible locations of each object at current time but also its historically possible locations. To speed up the query processing, we present a general framework for answering IRNN queries on uncertain moving objects with Markov correlations in two phases. In the first phase, we apply space pruning and probability pruning techniques, which reduce the search space significantly. In the second phase, we verify whether each unpruned object is an IRNN of the query object. During this phase, we propose an approach termed Probability Decomposition Verification (PDV) algorithm which avoid computing the probability of any object being an RNN of the query object exactly and thus improve the efficiency of verification. The performance of the proposed algorithm is demonstrated by extensive experiments on synthetic and real datasets, and the experimental results show that our algorithm is more efficient than the Monte-Carlo based approximate algorithm.
Sponsorship	IEEE Comput. Soc.
Starting Page	170
Ending Page	181
File Size	579894
Page Count	12
File Format	PDF
ISBN	9781467349093
ISSN	10636382
e-ISBN	9781467349109
e-ISBN	9781467349086
DOI	10.1109/ICDE.2013.6544823
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-04-08
Publisher Place	Australia
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Markov processes Correlation Trajectory Monitoring Nearest neighbor searches Query processing
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Probabilistic Reverse Nearest Neighbor Queries on Uncertain Data

Probabilistic nearest neighbor queries on uncertain moving object trajectories (2013).

Visible Reverse k-Nearest Neighbor Queries

On Reverse Nearest Neighbor Queries (2002)

On efficient obstructed reverse nearest neighbor query processing

Efficiently Processing Continuous k-NN Queries on Data Streams

Incremental and General Evaluation of Reverse Nearest Neighbors

High dimensional reverse nearest neighbor queries

Probabilistic reverse nearest neighbor queries on uncertain data (2008).

Interval reverse nearest neighbor queries on uncertain data with Markov correlations

Similar Documents

Probabilistic Reverse Nearest Neighbor Queries on Uncertain Data

Probabilistic nearest neighbor queries on uncertain moving object trajectories (2013).

Visible Reverse k-Nearest Neighbor Queries

On Reverse Nearest Neighbor Queries (2002)

On efficient obstructed reverse nearest neighbor query processing

Efficiently Processing Continuous k-NN Queries on Data Streams

Incremental and General Evaluation of Reverse Nearest Neighbors

High dimensional reverse nearest neighbor queries

Probabilistic reverse nearest neighbor queries on uncertain data (2008).

Interval reverse nearest neighbor queries on uncertain data with Markov correlations