Efficient difference NN queries for moving objects

Bin Wang*, Xiaochun Yang, Guoren Wang, Ge Yu

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Group Nearest Neighbor query is a relatively prevalent application in spatial databases and overlay network. Unlike the traditional KNN queries, GNN queries maintain several query points and allow aggregate operations among them. Our paper proposes a novel approach for dealing with difference operation of GNN queries on multiple query points. Difference nearest neighbor (DNN) plays an important role on statistical analysis and engineer computation. Seldom existing approaches consider DNN queries. In our paper, we use the properties of hyperbola to efficiently solve DNN queries. A hyperbola divides the query space into several subspaces. Such properties can help us to prune the search spaces. However, the computation cost using hyperbola is not desirable since it is difficult to estimate spaces using curves. Therefore, we adopt asymptotes of hyperbola to simplify the hyperbola-based pruning strategy to reduce the computation cost and the search space. Our experimental results show that the proposed approaches can efficiently solve DNN queries.

Original languageEnglish
Title of host publicationAdvances in Data and Web Management - Joint 9th Asia-Pacific Web Conference, APWeb 2007 and 8th International Conference on Web-Age Information Management, WAIM 2007, Proceedings
PublisherSpringer Verlag
Pages542-553
Number of pages12
ISBN (Print)9783540724834
DOIs
Publication statusPublished - 2007
Externally publishedYes
EventJoint 9th Asia-Pacific Web Conference on Advances in Data and Web Management, APWeb 2007 and 8th International Conference on Web-Age Information Management, WAIM 2007 - Huang Shan, China
Duration: 16 Jun 200718 Jun 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4505 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceJoint 9th Asia-Pacific Web Conference on Advances in Data and Web Management, APWeb 2007 and 8th International Conference on Web-Age Information Management, WAIM 2007
Country/TerritoryChina
CityHuang Shan
Period16/06/0718/06/07

Fingerprint

Dive into the research topics of 'Efficient difference NN queries for moving objects'. Together they form a unique fingerprint.

Cite this