Processing Constrained K-Closest Pairs Queries in Crime Databases

Abstract

Recently, spatial analysis in crime databases has attracted increased attention. In order to cope with the problem of discovering the closest pairs of objects within a constrained spatial region, as required in crime investigation applications, we propose a query processing algorithm called Growing Window based Constrained k-Closest Pairs (GWCCP). The algorithm incrementally extends the query window without searching the whole workspace for multiple types of spatial objects. We use an optimized R-tree to store the index entities and employ a density-based range estimation approach to approximate the query range. We introduce a distance threshold with regard to the closest pair of objects to prune tree nodes in order to improve query performance. Experiments discuss the effect of three important factors, i.e., the portion of overlapping between the workspaces of two data sets, the value of k, and the buffer size. The results show that GWCCP outperforms the heap-based approach as a baseline in a number of aspects. In addition, GWCCP performs better within the same data set in terms of time and space efficiency.