An Incremental Approach to Closest Pair Queries in Spatial Networks Using Best-First Search
Conference Proceeding Article
This paper addresses the problem of k Closest Pairs (kCP) query in spatial network databases. A Best-First search approach namely BFCP (Best-First Closest Pair) is proposed. Given two data sets of objects in a spatial network, BFCP first finds the 1st CP by computing the 1st NN (nearest neighbor) of each object in the set with smaller cardinality. Then BFCP retrieves the 2nd , 3rd , ... , kth CP in an incremental way by searching the next NN of the currently found CP's source point. Furthermore, a novel buffer replacement policy called MDU (Minimum Distance Unit) is proposed to reduce I/O cost of BFCP. Unlike LRU, which records only the last reference time, the MDU policy considers both temporal locality and spatial locality when selecting a buffer page as the victim. A comprehensive experimental study is conducted to demonstrate the advantage of BFCP and MDU.
Closest Pair, Spatial networks, Location-based services, Buffer management
Databases and Information Systems | Digital Communications and Networking
Data Management and Analytics
22nd International Conference on Database and Expert Systems Applications (DEXA'11)
City or Country
CHEN, Chunan; SUN, Weiwei; ZHENG, Baihua; Mao, Dingding; and LIU, Weimo.
An Incremental Approach to Closest Pair Queries in Spatial Networks Using Best-First Search. (2011). 22nd International Conference on Database and Expert Systems Applications (DEXA'11). 136-143. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/1411