research-article

Reverse ranking query over imprecise spatial data

Authors:

Wang-Chien LeeAuthors Info & Claims

COM.Geo '10: Proceedings of the 1st International Conference and Exhibition on Computing for Geospatial Research & Application

Article No.: 17, Pages 1 - 8

https://doi.org/10.1145/1823854.1823875

Published: 21 June 2010 Publication History

Abstract

The reverse rank of a (data) object o with respect to a given query object q (that measures the relative nearness of q to o) is said to be k when q is the k-th nearest neighbor of o in a geographical space. Based on the notion of reverse ranks, a <u>R</u>everse <u>R</u>anking (RR) query determines t objects with the smallest k's with respect to a given query object q. In many situations that locations of objects and a query object can be imprecise, objects would receive multiple possible k's. In this paper, we propose a notion of expected reverse ranks and evaluation of RR queries over imprecise data based on expected reverse ranks. For any object o, an expected reverse rank kk is a weighted average of possible reverse ranks for individual instances of o with respect to different instances of a given query object q by taking their probabilities into account. We devise and present incremental kk computation and two kk-Estimating algorithms to efficiently evaluate RR queries over imprecise data. The efficiency of our approach is demonstrated through experiments.

References

[1]

S. Abiteboul, P. Kanellakis, and G. Grahne. On the representation and querying of sets of possible worlds. ACM SIGMOD Record, 16(3):34--48, 1987.

Digital Library

[2]

L. Antova, C. Koch, and D. Olteanu. 10¹⁰ ⁶ Worlds and Beyond: Efficient Representation and Processing of Incomplete Information. In Proc. of IEEE ICDE, pages 606--615, 2007.

[3]

O. Benjelloun, A. D. Sarma, A. Y. Halevy, and J. Widom. ULDBs: Databases with Uncertainty and Lineage. In Proc. of VLDB Conf, pages 953--964, 2006.

Digital Library

[4]

G. Beskales, M. A. Soliman, and I. F. Ilyas. Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases. PVLDB, 1(1):326--339, 2008.

Digital Library

[5]

S. Chaudhuri, K. Ganjam, V. Ganti, and R. Motwani. Robust and Efficient Fuzzy Match for Online Data Cleaning. In Proc. of ACM SIGMOD Conf., pages 313--324, 2003.

Digital Library

[6]

M. A. Cheema, X. Lin, W. Wang, W. Zhang, and J. Pei. Probabilistic Reverse Nearest Neighbor Queries on Uncertain Data. IEEE TKDE, page to appear, accepted.

Digital Library

[7]

R. Cheng, D. V. Kalashnikov, and S. Prabhakar. Evaluating Probabilistic Queries over Imprecise Data. In Proc. of ACM SIGMOD Conf., pages 551--562, 2003.

Digital Library

[8]

R. Cheng, D. V. Kalashnikov, and S. Prabhakar. Querying Imprecise Data in Moving Object Environments. IEEE TKDE, 16(9):1112--1127, 2004.

Digital Library

[9]

G. Cormode, F. Li, and K. Yi. Semantics of Ranking Queries for Probabilistic Data and Expected Ranks. In Proc. of IEEE ICDE, pages 305--316, 2009.

Digital Library

[10]

N. N. Dalvi and D. Suciu. Efficient Query Evaluation on Probabilistic Databases. VLDB Journal, 16(4):523--544, 2007.

Digital Library

[11]

A. Deshpande, C. Guestrin, S. Madden, J. M. Hellerstein, and W. Hong. Model-Driven Data Acquisition in Sensor Networks. In Proc. of VLDB Conf, pages 588--599, 2004.

Digital Library

[12]

N. Fuhr and T. Rölleke. A Probabilistic Relational Algebra for the Integration of Information Retrieval and Database Systems. ACM TOIS, 15(1):32--66, 1997.

Digital Library

[13]

Y. J. García, M. A. Lopez, and S. T. Leutenegger. A Greedy Algorithm for Bulk Loading R-Trees. In Proc of ACM GIS, pages 163--164, 1998.

Digital Library

[14]

A. Y. Halevy, A. Rajaraman, and J. J. Ordille. Data Integration: The Teenage Years. In Proc. of VLDB Conf, pages 9--16, 2006.

Digital Library

[15]

M. A. Hernandez and S. J. Stolfo. Real-world Data is Dirty: Data Cleansing and The Merge/Purge Problem. Data Mining and Knowledge Discovery, 1(1):9--37, 1998.

Digital Library

[16]

M. Hua, J. Pei, W. Zhang, and X. Lin. Ranking Queries on Uncertain data: a Probabilistic Threshold Approach. In Proc. of ACM SIGMOD Conf., pages 673--686, 2008.

Digital Library

[17]

F. Korn and S. Muthukrishnan. Influence Sets Based on Reverse Nearest Neighbor Queries. In Proc. of ACM SIGMOD Conf., pages 201--212, 2000.

Digital Library

[18]

L. V. S. Lakshmanan, N. Leone, R. Ross, and V. S. Subrahmanian. ProbView: a Flexible Probabilistic Database System. ACM TODS, 22(3):419--469, 1997.

Digital Library

[19]

K. C. K. Lee, B. Zheng, and W.-C. Lee. Ranked Reverse Nearest Neighbor Search. IEEE TKDE, 20(7):894--910, 2008.

Digital Library

[20]

X. Lian and L. C. 0002. Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases. In Proc. of ACM SIGMOD Conf, pages 213--226, 2008.

Digital Library

[21]

X. Lian and L. Chen. Efficient Processing of Probabilistic Reverse Nearest Neighbor Queries Over Uncertain Data. VLDB Journal, 18(3):787--808, 2009.

Digital Library

[22]

J. Pei, B. Jiang, X. Lin, and Y. Yuan. Probabilistic Skylines on Uncertain Data. In Proc. of VLDB Conf, pages 15--26, 2007.

Digital Library

[23]

C. Re, N. N. Dalvi, and D. Suciu. Efficient Top-k Query Evaluation on Probabilistic Data. In Proc. of IEEE ICDE, pages 886--895, 2007.

[24]

M. A. Soliman, I. F. Ilyas, and K. C.-C. Chang. Top-k Query Processing in Uncertain Databases. In Proc. of IEEE ICDE, pages 896--905, 2007.

[25]

Y. Tao, X. Xiao, and R. Cheng. Range Search on Multidimensional Uncertain Data. ACM TODS, 32(3):15, 2007.

Digital Library

[26]

X. Zhang and C. J. On the Semantics and Evaluation of Top-k Queries in Probabilistic Databases. In DBRank, pages 556--563, 2008.

Digital Library

Cited By

Zhao PFang HSheng VLi ZXu JWu JCui Z(2017)Monochromatic and bichromatic ranked reverse boolean spatial keyword nearest neighbors searchWorld Wide Web10.1007/s11280-016-0399-820:1(39-59)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s11280-016-0399-8
Fang HZhao PSheng VLi ZXu JWu JCui Z(2015)Ranked Reverse Boolean Spatial Keyword Nearest Neighbors SearchProceedings, Part I, of the 16th International Conference on Web Information Systems Engineering --- WISE 2015 - Volume 941810.1007/978-3-319-26190-4_7(92-107)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1007/978-3-319-26190-4_7
Zhang ZJin CKang Q(2014)Reverse k-ranks queryProceedings of the VLDB Endowment10.14778/2732951.27329527:10(785-796)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.14778/2732951.2732952
Show More Cited By

Reverse ranking query over imprecise spatial data
1. Information systems
  1. Data management systems
    1. Database management system engines
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

Probabilistic Reverse Top-k Query on Probabilistic Data
Databases Theory and Applications
Abstract
Reverse top-k queries have received much attention from research communities. The result of reverse top-k queries is a set of objects, which had the k-most interest based on their objects’ references. Moreover, answering the queries on ...
Bichromatic Reverse Ranking Query in Two Dimensions
ADMA 2013: Part II of the Proceedings of the 9th International Conference on Advanced Data Mining and Applications - Volume 8347

Capturing potential customers for a given product based on individual preferences is very important in many personalized applications. Reverse ranking queries are widely employed in this scenario from the perspective of product in database community. ...
Efficient probabilistic reverse nearest neighbor query processing on uncertain data

Given a query object q, a reverse nearest neighbor (RNN) query in a common certain database returns the objects having q as their nearest neighbor. A new challenge for databases is dealing with uncertain objects. In this paper we consider probabilistic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

COM.Geo '10: Proceedings of the 1st International Conference and Exhibition on Computing for Geospatial Research & Application

June 2010

274 pages

ISBN:9781450300315

DOI:10.1145/1823854

General Chair:
Lindi Liao

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

COM.Geo '10

COM.Geo '10: 1st International Conference on Computing for Geospatial Research and Application

June 21 - 23, 2010

Washington, D.C., USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
160
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhao PFang HSheng VLi ZXu JWu JCui Z(2017)Monochromatic and bichromatic ranked reverse boolean spatial keyword nearest neighbors searchWorld Wide Web10.1007/s11280-016-0399-820:1(39-59)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s11280-016-0399-8
Fang HZhao PSheng VLi ZXu JWu JCui Z(2015)Ranked Reverse Boolean Spatial Keyword Nearest Neighbors SearchProceedings, Part I, of the 16th International Conference on Web Information Systems Engineering --- WISE 2015 - Volume 941810.1007/978-3-319-26190-4_7(92-107)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1007/978-3-319-26190-4_7
Zhang ZJin CKang Q(2014)Reverse k-ranks queryProceedings of the VLDB Endowment10.14778/2732951.27329527:10(785-796)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.14778/2732951.2732952
Kang QZhang ZJin CZhou A(2014)A Product-Customer Matching Framework for Web 2.0 ApplicationsWeb Information Systems Engineering – WISE 201410.1007/978-3-319-11746-1_36(489-504)Online publication date: 2014
https://doi.org/10.1007/978-3-319-11746-1_36
Jin CZhang RKang QZhang ZZhou A(2014)Probabilistic Reverse Top-k QueriesDatabase Systems for Advanced Applications10.1007/978-3-319-05810-8_27(406-419)Online publication date: 2014
https://doi.org/10.1007/978-3-319-05810-8_27
Zhang ZKang QJin CZhou A(2013)Bichromatic Reverse Ranking Query in Two DimensionsPart II of the Proceedings of the 9th International Conference on Advanced Data Mining and Applications - Volume 834710.1007/978-3-642-53917-6_31(348-359)Online publication date: 14-Dec-2013
https://dl.acm.org/doi/10.1007/978-3-642-53917-6_31
Bernecker TKriegel HMamoulis NRenz MZuefle A(2011)Continuous inverse ranking queries in uncertain streamsProceedings of the 23rd international conference on Scientific and statistical database management10.5555/2032397.2032402(37-54)Online publication date: 20-Jul-2011
https://dl.acm.org/doi/10.5555/2032397.2032402
Lee KLiao L(2011)Efficient evaluation of location-dependent skyline queries using non-dominance scopesProceedings of the 2nd International Conference on Computing for Geospatial Research & Applications10.1145/1999320.1999334(1-8)Online publication date: 23-May-2011
https://dl.acm.org/doi/10.1145/1999320.1999334
Bernecker TKriegel HMamoulis NRenz MZuefle A(2011)Continuous Inverse Ranking Queries in Uncertain StreamsScientific and Statistical Database Management10.1007/978-3-642-22351-8_3(37-54)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22351-8_3

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten