Rtecently a lot of works have been investigating to find the tenuous groups,i.e.,groups with few social interactions and weak relationships among members,for reviewer selection and psycho-educational group formation.H...Rtecently a lot of works have been investigating to find the tenuous groups,i.e.,groups with few social interactions and weak relationships among members,for reviewer selection and psycho-educational group formation.However,the metrics(e.g.,k-triangle,k-line,and k-tenuity)used to measure the tenuity,require a suitable k value to be specified which is difficult for users without background knowledge.Thus,in this paper we formulate the most tenuous group(MTG)query in terms of the group distance and average group distance of a group measuring the tenuity to eliminate the influence of parameter k on the tenuity of the group.To address the MTG problem,we first propose an exact algorithm,namely MTGVDIS,which takes priority to selecting those vertices whose vertex distance is large,to generate the result group,and also utilizes effective filtering and pruning strategies.Since MTGVDIS is not fast enough,we design an efficient exact algorithm,called MTG-VDGE,which exploits the degree metric to sort the vertexes and proposes a new combination order,namely degree and reverse based branch and bound(DRBB).MTG-VDGE gives priority to those vertices with small degree.For a large p,we further develop an approximation algorithm,namely MTG-VDLT,which discards candidate attendees with high degree to reduce the number of vertices to be considered.The experimental results on real datasets manifest that the proposed algorithms outperform existing approaches on both efficiency and group tenuity.展开更多
In this paper, we study the skyline group problem over a data stream. An object can dominate another object if it is not worse than the other object on all attributes and is better than the other object on at least on...In this paper, we study the skyline group problem over a data stream. An object can dominate another object if it is not worse than the other object on all attributes and is better than the other object on at least one attribute. If an object cannot be dominated by any other object, it is a skyline object. The skyline group problem involves finding k-item groups that cannot be dominated by any other k-item group. Existing algorithms designed to find skyline groups can only process static data. However, data changes as a stream with time in many applications,and algorithms should be designed to support skyline group queries on dynamic data. In this paper, we propose new algorithms to find skyline groups over a data stream. We use data structures, namely a hash table, dominance graph, and matrix, to store dominance information and update results incrementally. We conduct experiments on synthetic datasets to evaluate the performance of the proposed algorithms. The experimental results show that our algorithms can efficiently find skyline groups over a data stream.展开更多
基金supported by the Key-Area Research and Development Program of Guangdong Province(2020B0101100001)Guangdong Basic and Applied Basic Research Foundation(2019B1515130001)+2 种基金the National Natural Science Foundation of China(Grant Nos.61902438 and 61902439)Natural Science Foundation of Guangdong Province(2019A1515011704 and 2019A1515011159)Jianliang Xu's work is supported by HK-RGC(12201018).
文摘Rtecently a lot of works have been investigating to find the tenuous groups,i.e.,groups with few social interactions and weak relationships among members,for reviewer selection and psycho-educational group formation.However,the metrics(e.g.,k-triangle,k-line,and k-tenuity)used to measure the tenuity,require a suitable k value to be specified which is difficult for users without background knowledge.Thus,in this paper we formulate the most tenuous group(MTG)query in terms of the group distance and average group distance of a group measuring the tenuity to eliminate the influence of parameter k on the tenuity of the group.To address the MTG problem,we first propose an exact algorithm,namely MTGVDIS,which takes priority to selecting those vertices whose vertex distance is large,to generate the result group,and also utilizes effective filtering and pruning strategies.Since MTGVDIS is not fast enough,we design an efficient exact algorithm,called MTG-VDGE,which exploits the degree metric to sort the vertexes and proposes a new combination order,namely degree and reverse based branch and bound(DRBB).MTG-VDGE gives priority to those vertices with small degree.For a large p,we further develop an approximation algorithm,namely MTG-VDLT,which discards candidate attendees with high degree to reduce the number of vertices to be considered.The experimental results on real datasets manifest that the proposed algorithms outperform existing approaches on both efficiency and group tenuity.
基金supported by the Fundamental Research Funds for the Central Universities (Nos. FRF-TP-14025A1 and FRF-TP-15-025A2)supported by the Key Technologies Research and Development Program of 12th Five-Year Plan of China (No.2013BAI13B06)
文摘In this paper, we study the skyline group problem over a data stream. An object can dominate another object if it is not worse than the other object on all attributes and is better than the other object on at least one attribute. If an object cannot be dominated by any other object, it is a skyline object. The skyline group problem involves finding k-item groups that cannot be dominated by any other k-item group. Existing algorithms designed to find skyline groups can only process static data. However, data changes as a stream with time in many applications,and algorithms should be designed to support skyline group queries on dynamic data. In this paper, we propose new algorithms to find skyline groups over a data stream. We use data structures, namely a hash table, dominance graph, and matrix, to store dominance information and update results incrementally. We conduct experiments on synthetic datasets to evaluate the performance of the proposed algorithms. The experimental results show that our algorithms can efficiently find skyline groups over a data stream.
