Cloud-based K-closest pairs discovery in dynamic cyber-physical-social systems

Junwen Lu, Guanfeng Liu*, Xianmei Hua

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)70664-70675
Number of pages12
JournalIEEE Access
Volume8
DOIs
Publication statusPublished - 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

Fingerprint Dive into the research topics of 'Cloud-based K-closest pairs discovery in dynamic cyber-physical-social systems'. Together they form a unique fingerprint.

Cite this