More Web Proxy on the site http://driver.im/

Article

Group Nearest Neighbor Queries

Authors:

Dimitris Papadias,

Kyriakos MouratidisAuthors Info & Claims

ICDE '04: Proceedings of the 20th International Conference on Data Engineering

Page 301

Published: 30 March 2004 Publication History

Abstract

Given two sets of points P and Q, a group nearest neighbor(GNN) query retrieves the point(s) of P with the smallestsum of distances to all points in Q. Consider, for instance,three users at locations q1, q2 and q3 that want to find a meeting point (e.g., a restaurant); the corresponding queryreturns the data point p that minimizes the sum of Euclideandistances |pqi| for 1 i 3. Assuming that Q fits in memoryand P is indexed by an R-tree, we propose severalalgorithms for finding the group nearest neighborsefficiently. As a second step, we extend our techniques forsituations where Q cannot fit in memory, covering bothindexed and non-indexed query points. An experimentalevaluation identifies the best alternative based on the dataand query properties.

References

[1]

Arya, S., Mount, D., Netanyahu, N., Silverman, R., Wu, A. An Optimal Algorithm for Approximate Nearest Neighbor Searching, Journal of the ACM , 45(6): 891-923, 1998.

Digital Library

[2]

Aggrawal, C., Yu, P. Outlier Detection for High Dimensional Data. SIGMOD , 2001.

Digital Library

[3]

Bohm, C. A Cost Model for Query Processing in High Dimensional Data Spaces. TODS , Vol. 25(2): 129- 178, 2000.

Digital Library

[4]

Bruno, N., Chaudhuri, S., Gravano, L. Top-k Selection Queries over Relational Databases: Mapping Strategies and Performance Evaluation. TODS 27(2): 153-187, 2002.

Digital Library

[5]

Beyer, K., Goldstein, J., Ramakrishnan, R., Shaft, U. When Is Nearest Neighbor Meaningful? ICDT , 1999.

Digital Library

[6]

Benetis, R., Jensen, C., Karciauskas, G., Saltenis, S. Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects. IDEAS , 2002.

Digital Library

[7]

Beckmann, N., Kriegel, H.P., Schneider, R., Seeger, B. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD , 1990.

Digital Library

[8]

Corral, A., Manolopoulos, Y., Theodoridis, Y., Vassilakopoulos, M. Closest Pair Quenes in Spatial Databases. SIGMOD , 2000.

Digital Library

[9]

Fagin, R. Combining Fuzzy Information: an Overview. SIGMOD Record , 31 (2): 109-118, 2002.

Digital Library

[10]

Fagin, R., Lotem, A., Naor, M. Optimal Aggregation Algorithms for Middleware. PODS , 2001.

Digital Library

[11]

Ferhatosmanoglu, H., Stanoi, I., Agrawal, D., Abbadi, A. Constrained Nearest Neighbor Queries. SSTD , 2001.

Digital Library

[12]

Guttman, A. R-trees: A Dynamic Index Structure for Spatial Searching. SIGMOD , 1984.

Digital Library

[13]

Jain, A., Murthy, M., Flynn, P., Data Clustering: A Review. ACM Comp. Surveys , 31(3): 264-323, 1999.

Digital Library

[14]

Hjaltason, G., Samet, H. Incremental Distance Join Algorithms for Spatial Databases. SIGMOD , 1998.

Digital Library

[15]

Hjaltason, G., Samet, H. Distance Browsing in Spatial Databases. TODS , 24(2), 265-318, 1999.

Digital Library

[16]

Hochreiter, S., Younger, A.S., Conwell, P. Learning to Learn Using Gradient Descent. ICANN , 2001.

Digital Library

[17]

Kollios, G., Gunopulos, D., Tsotras, V. Nearest Neighbor Queries in Mobile Environment. STDBM , 1999.

Digital Library

[18]

Korn, F., Muthukrishnan, S. Influence Sets Based on Reverse Nearest Neighbor Queries. SIGMOD , 2000.

Digital Library

[19]

Korn, F., Muthukrishnan, S. Srivastava, D. Reverse Nearest Neighbor Aggregates Over Data Streams. VLDB , 2002.

Digital Library

[20]

Nakano, K., Olariu, S. An Optimal Algorithm for the Angle-Restricted All Nearest Neighbor Problem on the Reconfigurable Mesh, with Applications. IEEE Trans. on Parallel and Distributed Systems 8(9): 983- 990, 1997.

Digital Library

[21]

Papadopoulos, A., Manolopoulos, Y. Performance of Nearest Neighbor Queries in R-trees. ICDT , 1997.

Digital Library

[22]

Papadias, D., Zhang, J., Mamoulis, N., Tao, Y. Query Processing in Spatial Network Databases. VLDB , 2003.

Digital Library

[23]

Roussopoulos, N., Kelly, S., Vincent, F. Nearest Neighbor Queries. SIGMOD , 1995.

Digital Library

[24]

Sproull, R. Refinements to Nearest Neighbor Searching in K-Dimensional Trees. Algorithmica , 6(4): 579-589, 1991.

Digital Library

[25]

Shahabi, C., Kolahdouzan, M., Sharifzadeh, M. A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Object Databases. ACM GIS , 2002.

Digital Library

[26]

Song, Z., Roussopoulos, N. K-Nearest Neighbor Search for Moving Query Point. SSTD , 2001.

Digital Library

[27]

Sakurai, Y., Yoshikawa, M., Uemura, S. Kojima, H. The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation. VLDB , 2000.

Digital Library

[28]

Tao, Y., Papadias, D. Time Parameterized Queries in Spatio-Temporal Databases. SIGMOD , 2002.

Digital Library

[29]

Tao, Y., Papadias, D. Spatial Queries in Dynamic Environments. ACM TODS , 28(2): 101-139, 2003.

Digital Library

[30]

Tao, Y., Papadias, D., Shen, Q. Continuous Nearest Neighbor Search. VLDB , 2002.

Digital Library

[31]

www.maproom.psu.edu/dcw/

[32]

dke.cti.gr/People/ytheod/research/datasets/

[33]

Weber, R., Schek, H.J., Blott, S. A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. VLDB , 1998.

Digital Library

[34]

Yu, C., Ooi, B, Tan, K., Jagadish, H. Indexing the Distance: An Efficient Method to KNN Processing. VLDB , 2001.

Digital Library

Cited By

Apon SAli MGhosh BSellis T(2021)Social-Spatial Group Queries with KeywordsACM Transactions on Spatial Algorithms and Systems10.1145/34759628:1(1-32)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3475962
Yan DZhao ZNg W(2020)Efficient algorithms for finding optimal meeting point on road networksProceedings of the VLDB Endowment10.14778/3402707.34027344:11(968-979)Online publication date: 3-Jun-2020
https://dl.acm.org/doi/10.14778/3402707.3402734
Moutafis PGarcía-García FMavrommatis GVassilakopoulos MCorral AIribarne LHung CPapadopoulos G(2019)MapReduce algorithms for the K group nearest-neighbor queryProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3299733(448-455)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3299733
Show More Cited By

Index Terms

Group Nearest Neighbor Queries
1. Information systems
  1. Information retrieval
  2. Information systems applications
    1. Data mining

Recommendations

Privacy preserving group nearest neighbor queries
EDBT '10: Proceedings of the 13th International Conference on Extending Database Technology

User privacy in location-based services has attracted great interest in the research community. We introduce a novel framework based on a decentralized architecture for privacy preserving group nearest neighbor queries. A group nearest neighbor (GNN) ...
Nearest neighbor queries

A frequently encountered type of query in Geographic Information Systems is to find the k nearest neighbor objects to a given point in space. Processing such queries requires substantially different search algorithms than those for location or range ...
Probabilistic Group Nearest Neighbor Queries in Uncertain Databases

The importance of query processing over uncertain data has recently arisen due to its wide usage in many real-world applications. In the context of uncertain databases, previous work have studied many query types such as nearest neighbor query, range ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ICDE '04: Proceedings of the 20th International Conference on Data Engineering

March 2004

ISBN:0769520650

Copyright © Copyright (c) 2004 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 30 March 2004

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

72
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Apon SAli MGhosh BSellis T(2021)Social-Spatial Group Queries with KeywordsACM Transactions on Spatial Algorithms and Systems10.1145/34759628:1(1-32)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3475962
Yan DZhao ZNg W(2020)Efficient algorithms for finding optimal meeting point on road networksProceedings of the VLDB Endowment10.14778/3402707.34027344:11(968-979)Online publication date: 3-Jun-2020
https://dl.acm.org/doi/10.14778/3402707.3402734
Moutafis PGarcía-García FMavrommatis GVassilakopoulos MCorral AIribarne LHung CPapadopoulos G(2019)MapReduce algorithms for the K group nearest-neighbor queryProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3299733(448-455)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3299733
Hashem TKulik LRamamohanarao KZhang RSoma S(2019)Protecting privacy for distance and rank based group nearest neighbor queriesWorld Wide Web10.1007/s11280-018-0570-522:1(375-416)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s11280-018-0570-5
Wang YLi JZhong YZhu SGuo DShang S(2019)Discovery of accessible locations using region-based geo-social dataWorld Wide Web10.1007/s11280-018-0538-522:3(929-944)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s11280-018-0538-5
Dai YShao JHu GGuo L(2019)A resource-aware approach for authenticating privacy preserving GNN queriesWorld Wide Web10.1007/s11280-017-0507-422:2(437-454)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s11280-017-0507-4
Ghosh BAli MChoudhury FApon SSellis TLi J(2018)The flexible socio spatial group queriesProceedings of the VLDB Endowment10.14778/3282495.328249712:2(99-111)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.14778/3282495.3282497
Hua HXie HTanin EThakur GStorandt S(2018)Is Euclidean Distance Really that Bad with Road Networks?Proceedings of the 11th ACM SIGSPATIAL International Workshop on Computational Transportation Science10.1145/3283207.3283215(11-20)Online publication date: 6-Nov-2018
https://dl.acm.org/doi/10.1145/3283207.3283215
Khan AKulik LTanin EHua HHashem T(2018)Efficient Computation of the Optimal Accessible Location for a Group of Mobile AgentsACM Transactions on Spatial Algorithms and Systems10.1145/32391244:4(1-32)Online publication date: 10-Sep-2018
https://dl.acm.org/doi/10.1145/3239124
Dong YChen HYu JFuruse KKitagawa H(2018)Weighted Aggregate Reverse Rank QueriesACM Transactions on Spatial Algorithms and Systems10.1145/32252164:2(1-23)Online publication date: 10-Aug-2018
https://dl.acm.org/doi/10.1145/3225216
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents