File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Scalable processing of snapshot and continuous nearest-neighbor queries over one-dimensional uncertain data

TitleScalable processing of snapshot and continuous nearest-neighbor queries over one-dimensional uncertain data
Authors
KeywordsContinuous query
Incremental evaluation
Partial evaluation
Probabilistic nearest-neighbor query
Uncertain data
Issue Date2009
PublisherSpringer Verlag. The Journal's web site is located at http://link.springer.de/link/service/journals/00778/index.htm
Citation
Vldb Journal, 2009, v. 18 n. 5, p. 1219-1240 How to Cite?
AbstractIn several emerging and important applications, such as location-based services, sensor monitoring and biological databases, the values of the data items are inherently imprecise. A useful query class for these data is the Probabilistic Nearest-Neighbor Query (PNN), which yields the IDs of objects for being the closest neighbor of a query point, together with the objects' probability values. Previous studies showed that this query takes a long time to evaluate. To address this problem, we propose the Constrained Nearest-Neighbor Query (C-PNN), which returns the IDs of objects whose probabilities are higher than some threshold, with a given error bound in the answers. We show that the C-PNN can be answered efficiently with verifiers. These are methods that derive the lower and upper bounds of answer probabilities, so that an object can be quickly decided on whether it should be included in the answer. We design five verifiers, which can be used on uncertain data with arbitrary probability density functions. We further develop a partial evaluation technique, so that a user can obtain some answers quickly, without waiting for the whole query evaluation process to be completed (which may incur a high response time). In addition, we examine the maintenance of a long-standing, or continuous C-PNN query. This query requires any update to be applied to the result immediately, in order to reflect the changes to the database values (e.g., due to the change of the location of a moving object). We design an incremental update method based on previous query answers, in order to reduce the amount of I/O and CPU cost in maintaining the correctness of the answers to such a query. Performance evaluation on realistic datasets show that our methods are capable of yielding timely and accurate results. © 2009 Springer-Verlag.
Persistent Identifierhttp://hdl.handle.net/10722/88971
ISSN
2015 Impact Factor: 1.744
2015 SCImago Journal Rankings: 0.899
ISI Accession Number ID
Funding AgencyGrant Number
Research Grants Council of Hong KongHKU 5138/06E
HKU 513307
HKU 513508
Seed Funding Programme of the University of Hong Kong200808159002
RGCHKU 5138/06E
National Science FoundationIIS0811998
IIS0811935
CNS0708604
Funding Information:

Reynold Cheng was supported by the Research Grants Council of Hong Kong (Projects HKU 5138/06E, HKU 513307, HKU 513508), and the Seed Funding Programme of the University of Hong Kong (grant no. 200808159002). Jinchuan Chen was supported by RGC project HKU 5138/06E. Mohamed Mobkel and Chi-Yin Chow are supported in part by the National Science Foundation under Grants IIS0811998, IIS0811935, and CNS0708604. We also thank the reviewers for their insightful comments.

References
Grants

 

DC FieldValueLanguage
dc.contributor.authorChen, Jen_HK
dc.contributor.authorCheng, Ren_HK
dc.contributor.authorMokbel, Men_HK
dc.contributor.authorChow, CYen_HK
dc.date.accessioned2010-09-06T09:50:46Z-
dc.date.available2010-09-06T09:50:46Z-
dc.date.issued2009en_HK
dc.identifier.citationVldb Journal, 2009, v. 18 n. 5, p. 1219-1240en_HK
dc.identifier.issn1066-8888en_HK
dc.identifier.urihttp://hdl.handle.net/10722/88971-
dc.description.abstractIn several emerging and important applications, such as location-based services, sensor monitoring and biological databases, the values of the data items are inherently imprecise. A useful query class for these data is the Probabilistic Nearest-Neighbor Query (PNN), which yields the IDs of objects for being the closest neighbor of a query point, together with the objects' probability values. Previous studies showed that this query takes a long time to evaluate. To address this problem, we propose the Constrained Nearest-Neighbor Query (C-PNN), which returns the IDs of objects whose probabilities are higher than some threshold, with a given error bound in the answers. We show that the C-PNN can be answered efficiently with verifiers. These are methods that derive the lower and upper bounds of answer probabilities, so that an object can be quickly decided on whether it should be included in the answer. We design five verifiers, which can be used on uncertain data with arbitrary probability density functions. We further develop a partial evaluation technique, so that a user can obtain some answers quickly, without waiting for the whole query evaluation process to be completed (which may incur a high response time). In addition, we examine the maintenance of a long-standing, or continuous C-PNN query. This query requires any update to be applied to the result immediately, in order to reflect the changes to the database values (e.g., due to the change of the location of a moving object). We design an incremental update method based on previous query answers, in order to reduce the amount of I/O and CPU cost in maintaining the correctness of the answers to such a query. Performance evaluation on realistic datasets show that our methods are capable of yielding timely and accurate results. © 2009 Springer-Verlag.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://link.springer.de/link/service/journals/00778/index.htmen_HK
dc.relation.ispartofVLDB Journalen_HK
dc.subjectContinuous queryen_HK
dc.subjectIncremental evaluationen_HK
dc.subjectPartial evaluationen_HK
dc.subjectProbabilistic nearest-neighbor queryen_HK
dc.subjectUncertain dataen_HK
dc.titleScalable processing of snapshot and continuous nearest-neighbor queries over one-dimensional uncertain dataen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1066-8888&volume=18&spage=1219 &epage= 1240&date=2009&atitle=Scalable+Processing+of+Snapshot+and+Continuous+Nearest-Neighbor+Queries+over+One-Dimensional+Uncertain+Data.+en_HK
dc.identifier.emailCheng, R:ckcheng@cs.hku.hken_HK
dc.identifier.authorityCheng, R=rp00074en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/s00778-009-0152-3en_HK
dc.identifier.scopuseid_2-s2.0-70349845762en_HK
dc.identifier.hkuros162397en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-70349845762&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume18en_HK
dc.identifier.issue5en_HK
dc.identifier.spage1219en_HK
dc.identifier.epage1240en_HK
dc.identifier.eissn0949-877X-
dc.identifier.isiWOS:000270651600011-
dc.publisher.placeGermanyen_HK
dc.relation.projectPrivacy Protection in Location-based Services with Location Cloaking-
dc.identifier.scopusauthoridChen, J=23501401700en_HK
dc.identifier.scopusauthoridCheng, R=7201955416en_HK
dc.identifier.scopusauthoridMokbel, M=6603620488en_HK
dc.identifier.scopusauthoridChow, CY=7402578459en_HK
dc.identifier.citeulike5406234-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats