Efficient Metric All-k-Nearest-Neighbor Search on Datasets Without Any Index

An all-k-nearest-neighbor （AkNN） query finds k nearest neighbors for each query object. This problem arises naturally in many areas, such as GIS （geographic information system）, multimedia retrieval, and recommender systems. To support various data types and flexible distance metrics involved in real applications, we study AkNN retrieval in metric spaces, namely, metric AkNN （MAkNN） search. Consider that the underlying indexes on the query set and the object set may not exist, which is natural in many scenarios. For example, the query set and the object set could be the results of other queries, and thus, the underlying indexes cannot be built in advance. To support MAkNN search on datasets without any underlying index, we propose an efficient disk-based algorithm, termed as Partition-Based MAkNN Algorithm （PMA）, which follows a partition-search framework and employs a series of pruning rules for accelerating the search. In addition, we extend our techniques to tackle an interesting variant of MAkNN queries, i.e., metric self-AkNN （MSAkNN） search, where the query set is identical to the object set. Extensive experiments using both real and synthetic datasets demonstrate the effectiveness of our pruning rules and the efficiency of the proposed algorithms, compared with state-of-the-art MAkNN and MSAkNN algorithms.

Answering Non-Answer Questions on Reverse Top-k Geo-Social Keyword Queries

Due to the wide-spread use of geo-positioning technologies and geo-social networks,the reverse top-k geo-social keyword query has attracted considerable attention from both industry and research communities.A reverse top-k geo-social keyword(RkGSK)query finds the users who are spatially near,textually similar,and socially relevant to a specified point of interest.RkGSK queries are useful in many real-life applications.For example,they can help the query issuer identify potential customers in marketing decisions.However,the query constraints could be too strict sometimes,making it hard to find any result for the RkGSK query.The query issuers may wonder how to modify their original queries to get a certain number of query results.In this paper,we study non-answer questions on reverse top-k geo-social keyword queries(NARGSK).Given an RkGSK query and the required number M of query results,NARGSK aim to find the refined RkGSK query having M users in its result set.To efficiently answer NARGSK,we propose two algorithms(ERQ and NRG)based on query relaxation.As this is the first work to address NARGSK to the best of our knowledge,ERQ is the baseline extended from the state-of-the-art method,while NRG further improves the efficiency of ERQ.Extensive experiments using real-life datasets demonstrate the efficiency of our proposed algorithms,and the performance of NRG is improved by a factor of 1–2 on average compared with ERQ.

PRISMO: predictive skyline query processing over moving objects

Skyline query is important in the circumstances that require the support of decision making. The existing work on skyline queries is based mainly on the assumption that the datasets are static. Querying skylines over moving objects, however, is also important and requires more attention. In this paper, we propose a framework, namely PRISMO, for processing predictive skyline queries over moving objects that not only contain spatio-temporal information, but also include non-spatial dimensions, such as other dynamic and static attributes. We present two schemes, RBBS （branch-and-bound skyline with rescanning and repacking） and TPBBS （time-parameterized branch- and-bound skyline）, each with two alternative methods, to handle predictive skyline computation. The basic TPRBS is further extended to TPBBSE （TPBBS with expansion） to enhance the performance of memory space consumption and CPU time. Our schemes are flexible and thus can process point, range, and subspace predictive skyline queries. Extensive experiments show that our proposed schemes can handle predictive skyline queries effectively, and that TPBBS significantly outperforms RBBS.