File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Range search on multidimensional uncertain data

TitleRange search on multidimensional uncertain data
Authors
KeywordsRange Search
Uncertain Databases
Issue Date2007
Citation
Acm Transactions On Database Systems, 2007, v. 32 n. 3 How to Cite?
AbstractIn an uncertain database, every object o is associated with a probability density function, which describes the likelihood that o appears at each position in a multidimensional workspace. This article studies two types of range retrieval fundamental to many analytical tasks. Specifically, a nonfuzzy query returns all the objects that appear in a search region r q with at least a certain probability t q. On the other hand, given an uncertain object q, fuzzy search retrieves the set of objects that are within distance ε q from q with no less than probability t q. The core of our methodology is a novel concept of probabilistically constrained rectangle, which permits effective pruning/validation of nonqualifying/ qualifying data. We develop a new index structure called the U-tree for minimizing the query overhead. Our algorithmic findings are accompanied with a thorough theoretical analysis, which reveals valuable insight into the problem characteristics, and mathematically confirms the efficiency of our solutions. We verify the effectiveness of the proposed techniques with extensive experiments. © 2007 ACM.
Persistent Identifierhttp://hdl.handle.net/10722/152361
ISSN
2015 Impact Factor: 0.633
2015 SCImago Journal Rankings: 0.792
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorTao, Yen_US
dc.contributor.authorXiao, Xen_US
dc.contributor.authorCheng, Ren_US
dc.date.accessioned2012-06-26T06:37:37Z-
dc.date.available2012-06-26T06:37:37Z-
dc.date.issued2007en_US
dc.identifier.citationAcm Transactions On Database Systems, 2007, v. 32 n. 3en_US
dc.identifier.issn0362-5915en_US
dc.identifier.urihttp://hdl.handle.net/10722/152361-
dc.description.abstractIn an uncertain database, every object o is associated with a probability density function, which describes the likelihood that o appears at each position in a multidimensional workspace. This article studies two types of range retrieval fundamental to many analytical tasks. Specifically, a nonfuzzy query returns all the objects that appear in a search region r q with at least a certain probability t q. On the other hand, given an uncertain object q, fuzzy search retrieves the set of objects that are within distance ε q from q with no less than probability t q. The core of our methodology is a novel concept of probabilistically constrained rectangle, which permits effective pruning/validation of nonqualifying/ qualifying data. We develop a new index structure called the U-tree for minimizing the query overhead. Our algorithmic findings are accompanied with a thorough theoretical analysis, which reveals valuable insight into the problem characteristics, and mathematically confirms the efficiency of our solutions. We verify the effectiveness of the proposed techniques with extensive experiments. © 2007 ACM.en_US
dc.languageengen_US
dc.relation.ispartofACM Transactions on Database Systemsen_US
dc.subjectRange Searchen_US
dc.subjectUncertain Databasesen_US
dc.titleRange search on multidimensional uncertain dataen_US
dc.typeArticleen_US
dc.identifier.emailCheng, R:ckcheng@cs.hku.hken_US
dc.identifier.authorityCheng, R=rp00074en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1145/1272743.1272745en_US
dc.identifier.scopuseid_2-s2.0-34548430892en_US
dc.identifier.hkuros176451-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-34548430892&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume32en_US
dc.identifier.issue3en_US
dc.identifier.eissn1557-4644-
dc.identifier.isiWOS:000249890400002-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridTao, Y=7402420191en_US
dc.identifier.scopusauthoridXiao, X=14831850700en_US
dc.identifier.scopusauthoridCheng, R=7201955416en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats