Categorical top-k spatial influence query

详细信息    查看全文

• 作者：Jianye Yang ; Wenjie Zhang ; Ying Zhang ; Xiaoyang Wang ; Xuemin Lin
• 关键词：Influence query ; Functional unit ; Nearest neighbor set
• 刊名：World Wide Web
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：20
• 期：2
• 页码：175-203
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Information Systems Applications (incl.Internet); Database Management; Operating Systems;
• 出版者：Springer US
• ISSN：1573-1413
• 卷排序：20

文摘

The influence of a spatial facility object depicts the importance of the object in the whole data space. In this paper, we present a novel definition of object influence in applications where objects are of different categories. We study the problem of Spatial Influence Query which considers the contribution of an object in forming functional units consisting of a given set of objects with different categories designated by users. We first show that the problem of spatial influence query is NP-hard with respect to the number of object categories in the functional unit. To tackle the computational hardness, we develop an efficient framework following two main steps, possible participants finding and optimal functional unit computation. Based on this framework, for the first step, novel and efficient pruning techniques are developed based on the nearest neighbor set (NNS) approach. To find the optimal functional unit efficiently, we propose two algorithms, an exact algorithm and an efficient approximate algorithm with performance guarantee. Comprehensive experiments on both real and synthetic datasets demonstrate the effectiveness and efficiency of our techniques.