Abstract
Given a set of spatial points D containing keywordsinformation, a set of query objects Q and m querykeywords, a top-k aggregate nearest keyword (ANK) queryretrieves k objects from Q with the minimum sum of distancesto its nearest points in D such that each nearest point matchesat least one of query keywords. For example, consider thereis a spatial database D which manages facilities (e.g., school,restaurants, hospital, etc.) represented by sets of keywords. Auser may want to rank a set of locations with respect to thesum of distances to nearest interested facilities. For processingthis query, several algorithms are proposed using IR2-Tree asindex structure. Experiments on real data sets indicate that ourapproach is scalable and efficient in reducing query responsetime
Keywords-aggregate nearest neighbor; spatial keywordquery; spatial databases;
I. INTRODUCTION
Most traditional spatial queries on spatial databases suchas nearest neighbor queries [1], [2], range queries [3],and spatial join [4], [5], [6] do not concern non-spatialinformation (e.g., name, description, and type etc.). Due topopularity of keyword search services on the Internet such asGoogle Earth and Yahoo Maps, many of these applicationsallow users to provide a list of keywords besides the spatialinformation of objects. Queries on spatial objects associatedwith textual information represented by sets of keywords,called spatial keyword queries [7], have received significantattention in recent years.In this paper, we study an interesting type of spatialkeyword query called aggregate nearest keyword (ANK)query. Given a set of data points D which contains keywordinformation, a group of query objects Q and m querykeywords, a top-k ANK query retrieves k objects in Q withthe minimum sum of distances to its nearest points in D suchthat each nearest point matches at least one of query keywords.It can be widely utilized in various decision supportsystems and multiple domains like service recommendation,investment planning, etc. For example, consider a spatialdatabase D which manages facilities (or services) such asschools, restaurants and hospitals, represented by sets ofkeywords. A user wants to rank the locations with respect tothe sum of distances to nearest interested facilities. The usermay issue a set of locations and multiple query keywordsrepresenting his interested facilities, the result returns kbest locations that minimize the summed distance to thesefacilities.: Example of top-k ANK queryFig. 1 gives out a more concrete example of an ANKquery. White points are apartments as query objects Qdefined by a local resident. Gray points represent sampledataset of data points D with three keywords i.e., hospital,school and supermarket. The resident may be interested inthe apartment q which minimizes the sum of distances tonearest hospital, school and supermarket. For instance, thedistance between q1 and its nearest neighbor which includeskeyword hospital is 0.5. The distance between q1 and itsnearest school and supermarket is 0.4 and 0.3 respectively.The summed distance of q1 is τ (q1) = 0.5 + 0.4 + 0.3 = 1.2.Similarly, we obtain τ (q2) = 0.3 + 0.3 + 1.0 = 1.6 and τ (q3)= 0.2 + 0.4 + 1.3 = 1.9. τ (q1) is minimum and hence q1 isreturned as the best result to the user. In this example, eachgray point is associated with only one keyword. Actuallya spatial object is associated with a set of keywords ratherthan one keyword in many real applications. Each point inD may be associated with multiple keywords. In this case,the nearest hospital and school of a query point may be thesame point in D.Top-k spatial preference query (SPQ) proposed by Yiu etal. in [8] ranks objects based on the qualities of featuresin their spatial neighborhood. The objects which maximizethe aggregate function on the preference value of nearestneighbors are returned as result. In above example, thevalue in the box is the preference value of the data point.Then, q3 with maximum value of 0.3 + 0.6 + 0.9 = 1.8is returned as the best result for SPQ.


Download full report
http://doi.ieeecomputersociety10.1109/APWeb.2010.25