File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Reverse nearest neighbors in large graphs

TitleReverse nearest neighbors in large graphs
Authors
KeywordsGraphs and networks
Query processing
Spatial databases
Issue Date2006
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, 2006, v. 18 n. 4, p. 540-553 How to Cite?
Abstract
A reverse nearest neighbor (RNN) query returns the data objects that have a query point as their nearest neighbor (NN). Although such queries have been studied quite extensively in Euclidean spaces, there is no previous work in the context of large graphs. In this paper, we provide a fundamental lemma, which can be used to prune the search space while traversing the graph in search for RNN. Based on it, we develop two RNN methods; an eager algorithm that attempts to prune network nodes as soon as they are visited and a lazy technique that prunes the search space when a data point is discovered. We study retrieval of an arbitrary number k of reverse nearest neighbors, investigate the benefits of materialization, cover several query types, and deal with cases where the queries and the data objects reside on nodes or edges of the graph. The proposed techniques are evaluated in various practical scenarios involving spatial maps, computer networks, and the DBLP coauthorship graph. © 2006 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/47092
ISSN
2013 Impact Factor: 1.815
2013 SCImago Journal Rankings: 1.763
References

 

Author Affiliations
  1. The University of Hong Kong
  2. City University of Hong Kong
  3. Hong Kong University of Science and Technology
DC FieldValueLanguage
dc.contributor.authorYiu, MLen_HK
dc.contributor.authorPapadias, Den_HK
dc.contributor.authorMamoulis, Nen_HK
dc.contributor.authorTao, Yen_HK
dc.date.accessioned2007-10-30T07:06:57Z-
dc.date.available2007-10-30T07:06:57Z-
dc.date.issued2006en_HK
dc.identifier.citationIeee Transactions On Knowledge And Data Engineering, 2006, v. 18 n. 4, p. 540-553en_HK
dc.identifier.issn1041-4347en_HK
dc.identifier.urihttp://hdl.handle.net/10722/47092-
dc.description.abstractA reverse nearest neighbor (RNN) query returns the data objects that have a query point as their nearest neighbor (NN). Although such queries have been studied quite extensively in Euclidean spaces, there is no previous work in the context of large graphs. In this paper, we provide a fundamental lemma, which can be used to prune the search space while traversing the graph in search for RNN. Based on it, we develop two RNN methods; an eager algorithm that attempts to prune network nodes as soon as they are visited and a lazy technique that prunes the search space when a data point is discovered. We study retrieval of an arbitrary number k of reverse nearest neighbors, investigate the benefits of materialization, cover several query types, and deal with cases where the queries and the data objects reside on nodes or edges of the graph. The proposed techniques are evaluated in various practical scenarios involving spatial maps, computer networks, and the DBLP coauthorship graph. © 2006 IEEE.en_HK
dc.format.extent3882120 bytes-
dc.format.extent1768 bytes-
dc.format.extent1945 bytes-
dc.format.extent4295 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypetext/plain-
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©2006 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.en_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectGraphs and networksen_HK
dc.subjectQuery processingen_HK
dc.subjectSpatial databasesen_HK
dc.titleReverse nearest neighbors in large graphsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1041-4347&volume=18&issue=4&spage=540&epage=553&date=2006&atitle=Reverse+nearest+neighbors+in+large+graphsen_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.2006.1599391en_HK
dc.identifier.scopuseid_2-s2.0-33644644150en_HK
dc.identifier.hkuros122098-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33644644150&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume18en_HK
dc.identifier.issue4en_HK
dc.identifier.spage540en_HK
dc.identifier.epage553en_HK
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridYiu, ML=8589889600en_HK
dc.identifier.scopusauthoridPapadias, D=7005757795en_HK
dc.identifier.scopusauthoridMamoulis, N=6701782749en_HK
dc.identifier.scopusauthoridTao, Y=7402420191en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats