Title

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

Research Areas

Data Management and Analytics

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