File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/TKDE.2006.1599391
- Scopus: eid_2-s2.0-33644644150
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Article: Reverse nearest neighbors in large graphs
Title | Reverse nearest neighbors in large graphs |
---|---|
Authors | |
Keywords | Graphs and networks Query processing Spatial databases |
Issue Date | 2006 |
Publisher | I 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 Identifier | http://hdl.handle.net/10722/47092 |
ISSN | 2023 Impact Factor: 8.9 2023 SCImago Journal Rankings: 2.867 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Yiu, ML | en_HK |
dc.contributor.author | Papadias, D | en_HK |
dc.contributor.author | Mamoulis, N | en_HK |
dc.contributor.author | Tao, Y | en_HK |
dc.date.accessioned | 2007-10-30T07:06:57Z | - |
dc.date.available | 2007-10-30T07:06:57Z | - |
dc.date.issued | 2006 | en_HK |
dc.identifier.citation | Ieee Transactions On Knowledge And Data Engineering, 2006, v. 18 n. 4, p. 540-553 | en_HK |
dc.identifier.issn | 1041-4347 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/47092 | - |
dc.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. © 2006 IEEE. | en_HK |
dc.format.extent | 3882120 bytes | - |
dc.format.extent | 1768 bytes | - |
dc.format.extent | 1945 bytes | - |
dc.format.extent | 4295 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.format.mimetype | text/plain | - |
dc.format.mimetype | text/plain | - |
dc.format.mimetype | text/plain | - |
dc.language | eng | en_HK |
dc.publisher | I E E E. The Journal's web site is located at http://www.computer.org/tkde | en_HK |
dc.relation.ispartof | IEEE Transactions on Knowledge and Data Engineering | en_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. | - |
dc.subject | Graphs and networks | en_HK |
dc.subject | Query processing | en_HK |
dc.subject | Spatial databases | en_HK |
dc.title | Reverse nearest neighbors in large graphs | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://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+graphs | en_HK |
dc.identifier.email | Mamoulis, N:nikos@cs.hku.hk | en_HK |
dc.identifier.authority | Mamoulis, N=rp00155 | en_HK |
dc.description.nature | published_or_final_version | en_HK |
dc.identifier.doi | 10.1109/TKDE.2006.1599391 | en_HK |
dc.identifier.scopus | eid_2-s2.0-33644644150 | en_HK |
dc.identifier.hkuros | 122098 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-33644644150&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 18 | en_HK |
dc.identifier.issue | 4 | en_HK |
dc.identifier.spage | 540 | en_HK |
dc.identifier.epage | 553 | en_HK |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Yiu, ML=8589889600 | en_HK |
dc.identifier.scopusauthorid | Papadias, D=7005757795 | en_HK |
dc.identifier.scopusauthorid | Mamoulis, N=6701782749 | en_HK |
dc.identifier.scopusauthorid | Tao, Y=7402420191 | en_HK |
dc.identifier.issnl | 1041-4347 | - |