Abstract
Given two object sets P and Q, a k-closest pairs (k-CP) query finds k closest object pairs from P × Q. This operation is common in many real-life applications such as GIS, data mining and recommender systems. However, the k-CP problem has not been well studied in Dynamic Cyber-Physical-Social Systems (D-CPSS), where temporal information and multiple attributes are associated with each edge. In D-CPSS, people would like to specify multiple constraints on these attributes within a time interval to illustrate their requirements. In this paper, we study the temporal multiple constraints k closest pairs (TMC-k-CP) in D-CPSS, which is NP-Complete. We propose a divide-and-conquer cloud-based algorithm (DC) to find TMC-k-CP efficiently and effectively. To the best of our knowledge, DC is the first algorithm supporting the TMC-k-CP query in D-CPSS. The experimental results on eight real D-CPSS datasets demonstrate that our algorithm outperforms the state-of-the-art methods in terms of both efficiency and effectiveness.
Original language | English |
---|---|
Pages (from-to) | 70664-70675 |
Number of pages | 12 |
Journal | IEEE Access |
Volume | 8 |
DOIs | |
Publication status | Published - 2020 |
Bibliographical note
Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.Keywords
- cloud-based
- CPSS
- divide and conquer
- k-closest pairs