An Incremental Approach to Closest Pair Queries in Spatial Networks Using Best-First Search

Publication Type

Conference Proceeding Article

Publication Date

8-2011

Abstract

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.

Keywords

Closest Pair, Spatial networks, Location-based services, Buffer management

Discipline

Databases and Information Systems | Digital Communications and Networking

Publication

22nd International Conference on Database and Expert Systems Applications (DEXA'11)

First Page

136

Last Page

143

ISBN

9783642230905

Identifier

10.1007/978-3-642-23091-2_13

Publisher

Springer Verlag

City or Country

Toulouse, France

Additional URL

http://dx.doi.org10.1007/978-3-642-23091-2_13

Link to Full Text

Share

COinS