File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Reverse nearest neighbors search in ad hoc subspaces

TitleReverse nearest neighbors search in ad hoc subspaces
Authors
KeywordsDistributed databases
Query processing
Spatial databases
Issue Date2007
PublisherI E E E. The Journal's web site is located at http://www.computer.org/tkde
Citation
Ieee Transactions On Knowledge And Data Engineering, 2007, v. 19 n. 3, p. 412-426 How to Cite?
AbstractGiven an object q, modeled by a multidimensional point, a reverse nearest neighbors (RNN) query returns the set of objects in the database that have q as their nearest neighbor. In this paper, we study an interesting generalization of the RNN query, where not all dimensions are considered, but only an ad hoc subset thereof. The rationale is that 1) the dimensionality might be too high for the result of a regular RNN query to be useful, 2) missing values may implicitly define a meaningful subspace for RNN retrieval, and 3) analysts may be interested in the query results only for a set of (ad hoc) problem dimensions (i.e., object attributes), We consider a suitable storage scheme and develop appropriate algorithms for projected RNN queries, without relying on multidimensional indexes. Given the significant cost difference between random and sequential data accesses, our algorithms are based on applying sequential accesses only on the projected atomic values of the data at each dimension, to progressively derive a set of RNN candidates. Whether these candidates are actual RNN results is then validated via an optimized refinement step. In addition, we study variants of the projected RNN problem, including RkNN search, bichromatic RNN, and RNN retrieval for the case where sequential accesses are not possible. Our methods are experimentally evaluated with real and synthetic data. © 2007 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/47083
ISSN
2023 Impact Factor: 8.9
2023 SCImago Journal Rankings: 2.867
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorYiu, MLen_HK
dc.contributor.authorMamoulis, Nen_HK
dc.date.accessioned2007-10-30T07:06:44Z-
dc.date.available2007-10-30T07:06:44Z-
dc.date.issued2007en_HK
dc.identifier.citationIeee Transactions On Knowledge And Data Engineering, 2007, v. 19 n. 3, p. 412-426en_HK
dc.identifier.issn1041-4347en_HK
dc.identifier.urihttp://hdl.handle.net/10722/47083-
dc.description.abstractGiven an object q, modeled by a multidimensional point, a reverse nearest neighbors (RNN) query returns the set of objects in the database that have q as their nearest neighbor. In this paper, we study an interesting generalization of the RNN query, where not all dimensions are considered, but only an ad hoc subset thereof. The rationale is that 1) the dimensionality might be too high for the result of a regular RNN query to be useful, 2) missing values may implicitly define a meaningful subspace for RNN retrieval, and 3) analysts may be interested in the query results only for a set of (ad hoc) problem dimensions (i.e., object attributes), We consider a suitable storage scheme and develop appropriate algorithms for projected RNN queries, without relying on multidimensional indexes. Given the significant cost difference between random and sequential data accesses, our algorithms are based on applying sequential accesses only on the projected atomic values of the data at each dimension, to progressively derive a set of RNN candidates. Whether these candidates are actual RNN results is then validated via an optimized refinement step. In addition, we study variants of the projected RNN problem, including RkNN search, bichromatic RNN, and RNN retrieval for the case where sequential accesses are not possible. Our methods are experimentally evaluated with real and synthetic data. © 2007 IEEE.en_HK
dc.format.extent2925527 bytes-
dc.format.extent1762 bytes-
dc.format.extent4295 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypetext/plain-
dc.format.mimetypetext/plain-
dc.languageengen_HK
dc.publisherI E E E. The Journal's web site is located at http://www.computer.org/tkdeen_HK
dc.relation.ispartofIEEE Transactions on Knowledge and Data Engineeringen_HK
dc.rights©2007 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.-
dc.subjectDistributed databasesen_HK
dc.subjectQuery processingen_HK
dc.subjectSpatial databasesen_HK
dc.titleReverse nearest neighbors search in ad hoc subspacesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1041-4347&volume=19&issue=3&spage=412&epage=426&date=2007&atitle=Reverse+Nearest+Neighbors+Search+in+Ad+Hoc+Subspacesen_HK
dc.identifier.emailMamoulis, N:nikos@cs.hku.hken_HK
dc.identifier.authorityMamoulis, N=rp00155en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1109/TKDE.2007.47en_HK
dc.identifier.scopuseid_2-s2.0-33847734773en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33847734773&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume19en_HK
dc.identifier.issue3en_HK
dc.identifier.spage412en_HK
dc.identifier.epage426en_HK
dc.identifier.isiWOS:000243504100006-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridYiu, ML=8589889600en_HK
dc.identifier.scopusauthoridMamoulis, N=6701782749en_HK
dc.identifier.citeulike4176809-
dc.identifier.issnl1041-4347-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats