File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: Reverse nearest neighbors in large graphs
  • Basic View
  • Metadata View
  • XML View
TitleReverse nearest neighbors in large graphs
 
AuthorsYiu, ML1
Papadias, D3
Mamoulis, N1
Tao, Y2
 
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
 
CitationIeee Transactions On Knowledge And Data Engineering, 2006, v. 18 n. 4, p. 540-553 [How to Cite?]
DOI: http://dx.doi.org/10.1109/TKDE.2006.1599391
 
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.
 
ISSN1041-4347
2012 Impact Factor: 1.892
2012 SCImago Journal Rankings: 2.675
 
DOIhttp://dx.doi.org/10.1109/TKDE.2006.1599391
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorYiu, ML
 
dc.contributor.authorPapadias, D
 
dc.contributor.authorMamoulis, N
 
dc.contributor.authorTao, Y
 
dc.date.accessioned2007-10-30T07:06:57Z
 
dc.date.available2007-10-30T07:06:57Z
 
dc.date.issued2006
 
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.
 
dc.description.naturepublished_or_final_version
 
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.identifier.citationIeee Transactions On Knowledge And Data Engineering, 2006, v. 18 n. 4, p. 540-553 [How to Cite?]
DOI: http://dx.doi.org/10.1109/TKDE.2006.1599391
 
dc.identifier.doihttp://dx.doi.org/10.1109/TKDE.2006.1599391
 
dc.identifier.epage553
 
dc.identifier.hkuros122098
 
dc.identifier.issn1041-4347
2012 Impact Factor: 1.892
2012 SCImago Journal Rankings: 2.675
 
dc.identifier.issue4
 
dc.identifier.openurl
 
dc.identifier.scopuseid_2-s2.0-33644644150
 
dc.identifier.spage540
 
dc.identifier.urihttp://hdl.handle.net/10722/47092
 
dc.identifier.volume18
 
dc.languageeng
 
dc.publisherI E E E. The Journal's web site is located at http://www.computer.org/tkde
 
dc.publisher.placeUnited States
 
dc.relation.ispartofIEEE Transactions on Knowledge and Data Engineering
 
dc.relation.referencesReferences in Scopus
 
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.
 
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License
 
dc.subjectGraphs and networks
 
dc.subjectQuery processing
 
dc.subjectSpatial databases
 
dc.titleReverse nearest neighbors in large graphs
 
dc.typeArticle
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Yiu, ML</contributor.author>
<contributor.author>Papadias, D</contributor.author>
<contributor.author>Mamoulis, N</contributor.author>
<contributor.author>Tao, Y</contributor.author>
<date.accessioned>2007-10-30T07:06:57Z</date.accessioned>
<date.available>2007-10-30T07:06:57Z</date.available>
<date.issued>2006</date.issued>
<identifier.citation>Ieee Transactions On Knowledge And Data Engineering, 2006, v. 18 n. 4, p. 540-553</identifier.citation>
<identifier.issn>1041-4347</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/47092</identifier.uri>
<description.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. &#169; 2006 IEEE.</description.abstract>
<format.extent>3882120 bytes</format.extent>
<format.extent>1768 bytes</format.extent>
<format.extent>1945 bytes</format.extent>
<format.extent>4295 bytes</format.extent>
<format.mimetype>application/pdf</format.mimetype>
<format.mimetype>text/plain</format.mimetype>
<format.mimetype>text/plain</format.mimetype>
<format.mimetype>text/plain</format.mimetype>
<language>eng</language>
<publisher>I E E E. The Journal&apos;s web site is located at http://www.computer.org/tkde</publisher>
<relation.ispartof>IEEE Transactions on Knowledge and Data Engineering</relation.ispartof>
<rights>&#169;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.</rights>
<rights>Creative Commons: Attribution 3.0 Hong Kong License</rights>
<subject>Graphs and networks</subject>
<subject>Query processing</subject>
<subject>Spatial databases</subject>
<title>Reverse nearest neighbors in large graphs</title>
<type>Article</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=1041-4347&amp;volume=18&amp;issue=4&amp;spage=540&amp;epage=553&amp;date=2006&amp;atitle=Reverse+nearest+neighbors+in+large+graphs</identifier.openurl>
<description.nature>published_or_final_version</description.nature>
<identifier.doi>10.1109/TKDE.2006.1599391</identifier.doi>
<identifier.scopus>eid_2-s2.0-33644644150</identifier.scopus>
<identifier.hkuros>122098</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-33644644150&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>18</identifier.volume>
<identifier.issue>4</identifier.issue>
<identifier.spage>540</identifier.spage>
<identifier.epage>553</identifier.epage>
<publisher.place>United States</publisher.place>
<bitstream.url>http://hub.hku.hk/bitstream/10722/47092/1/129721.pdf</bitstream.url>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. City University of Hong Kong
  3. Hong Kong University of Science and Technology