Efficient AKNN spatial network queries using the M-Tree

ABSTRACT

Aggregate K Nearest Neighbor (AKNN) queries are problematic when performed within spatial networks. While simpler network queries may be solved by a single network traversal search, the AKNN requires a large number costly network distance computations to completely compute results. The M-Tree index, when used with Road Network Embedding, provides an efficient alternative which can return estimates of the AKNN results. The M-Tree index can then be used as a filter for AKNN results by quickly computing a superset of the query results. The final AKNN query results can be computed by sorting the results from the M-Tree. In comparison to Incremental Euclidean Restriction (IER), the M-Tree reduces the overall query processing time and the total number of necessary network distance computations required to complete a query. In addition, the M-Tree filtering method is tunable to allow increasing performance at the expense of accuracy, making it suitable for a wide variety of applications.

REFERENCES

• 1: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 2: Haibo Hu , Dik Lun Lee , Victor C. S. Lee, Distance indexing on road networks, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 3: Cyrus Shahabi , Mohammad R. Kolahdouzan , Mehdi Sharifzadeh, A road network embedding technique for k-nearest neighbor search in moving object databases, Proceedings of the 10th ACM international symposium on Advances in geographic information systems, November 08-09, 2002, McLean, Virginia, USA [doi>10.1145/585147.585167]
• 4: Kevin Shaw , Elias Ioup , John Sample , Mahdi Abdelguerfi , Olivier Tabone, Efficient Approximation of Spatial Network Queries using the M-Tree with Road Network Embedding, Proceedings of the 19th International Conference on Scientific and Statistical Database Management, p.11, July 09-11, 2007 [doi>10.1109/SSDBM.2007.11]
• 5: Man Lung Yiu , Nikos Mamoulis , Dimitris Papadias, Aggregate Nearest Neighbor Queries in Road Networks, IEEE Transactions on Knowledge and Data Engineering, v.17 n.6, p.820-833, June 2005 [doi>10.1109/TKDE.2005.87]