Analysis and evaluation of the top-k most influential location selection query

Abstract

In this paper, we propose a newtype of queries to retrieve the top-kmost influential locations from a candidate set C given sets of customers M and existing facilities F. The influence models the popularity of a facility. Such queries have wide applications in decision support systems. A naive solution sequentially scans (SS) all data sets, which is expensive, and hence, we investigate two branch-and-bound algorithms for the query, namely Estimate Expanding Pruning (EEP) and Bounding Influence Pruning (BIP). Both algorithms followthe best first traverse. On determining the traversal order, while EEP leverages distance metrics between nodes, BIP relies on half plane pruning which avoids the repetitive estimations in EEP. As our experiments shown, BIP is much faster than SS which outperforms EEP, while theworst-case complexity of EEP and BIP isworse than that of SS. To improve the efficiency, we further propose aNearest Facility Circle Join (NFCJ) algorithm. NFCJ builds an influence R-tree on the influence relationship between customers and existing facilities and joins the candidate R-tree with the influence R-tree to obtain the results. We compare all algorithms and conclude that NFCJ is the best solution, which outperforms SS, EEP, and BIP by orders of magnitude. Show more