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

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...

Full description

Saved in:
Bibliographic Details
Main Authors: CHEN, Chunan, SUN, Weiwei, ZHENG, Baihua, Mao, Dingding, LIU, Weimo
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2011
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/1411
http://dx.doi.org10.1007/978-3-642-23091-2_13
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-2410
record_format dspace
spelling sg-smu-ink.sis_research-24102011-12-05T09:30:07Z An Incremental Approach to Closest Pair Queries in Spatial Networks Using Best-First Search CHEN, Chunan SUN, Weiwei ZHENG, Baihua Mao, Dingding LIU, Weimo 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. 2011-08-01T07:00:00Z text https://ink.library.smu.edu.sg/sis_research/1411 info:doi/10.1007/978-3-642-23091-2_13 http://dx.doi.org10.1007/978-3-642-23091-2_13 Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Closest Pair Spatial networks Location-based services Buffer management Databases and Information Systems Digital Communications and Networking
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Closest Pair
Spatial networks
Location-based services
Buffer management
Databases and Information Systems
Digital Communications and Networking
spellingShingle Closest Pair
Spatial networks
Location-based services
Buffer management
Databases and Information Systems
Digital Communications and Networking
CHEN, Chunan
SUN, Weiwei
ZHENG, Baihua
Mao, Dingding
LIU, Weimo
An Incremental Approach to Closest Pair Queries in Spatial Networks Using Best-First Search
description 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.
format text
author CHEN, Chunan
SUN, Weiwei
ZHENG, Baihua
Mao, Dingding
LIU, Weimo
author_facet CHEN, Chunan
SUN, Weiwei
ZHENG, Baihua
Mao, Dingding
LIU, Weimo
author_sort CHEN, Chunan
title An Incremental Approach to Closest Pair Queries in Spatial Networks Using Best-First Search
title_short An Incremental Approach to Closest Pair Queries in Spatial Networks Using Best-First Search
title_full An Incremental Approach to Closest Pair Queries in Spatial Networks Using Best-First Search
title_fullStr An Incremental Approach to Closest Pair Queries in Spatial Networks Using Best-First Search
title_full_unstemmed An Incremental Approach to Closest Pair Queries in Spatial Networks Using Best-First Search
title_sort incremental approach to closest pair queries in spatial networks using best-first search
publisher Institutional Knowledge at Singapore Management University
publishDate 2011
url https://ink.library.smu.edu.sg/sis_research/1411
http://dx.doi.org10.1007/978-3-642-23091-2_13
_version_ 1770571112616296448