Publications-Proceedings
Article View/Open
Publication Export
Google ScholarTM
NCCU Library
Citation Infomation
Related Publications in TAIR
| Title | On continuous top-k similarity joins |
| Creator | Li, D.J.;Wang, E.T.;Tsai, Y.-C.;Chen, Arbee L. P. 陳良弼 |
| Contributor | 資科系 |
| Key Words | Continuous data; Continuous queries; Data integration; Data sets; Data stream; Duplicate detection; Dynamic environments; Fundamental operations; Processing time; Similarity functions; Similarity join; Sliding Window; Static environment; Top-k query; Algorithms; Data communication systems; Data structures; Experiments; Pattern recognition; Data processing |
| Date | 2012 |
| Date Issued | 10-Apr-2015 17:26:26 (UTC+8) |
| Summary | Given a similarity function and a threshold σ within a range of [0, 1], a similarity join query between two sets of records returns pairs of records from the two sets, which have similarity values exceeding or equaling σ. Similarity joins have received much research attention since it is a fundamental operation used in a wide range of applications such as duplicate detection, data integration, and pattern recognition. Recently, a variant of similarity joins is proposed to avoid the need to set the threshold σ, i.e. top-k similarity joins. Since data in many applications are generated as a form of continuous data streams, in this paper, we make the first attempt to solve the problem of top-k similarity joins considering a dynamic environment involving a data stream, named continuous top-k similarity joins. Given a set of records as the query, we continuously output the top-k pairs of records, ranked by their similarity values, for the query and the most recent data, i.e. the data contained in the sliding window of a monitored data stream. Two algorithms are proposed to solve this problem. The first one extends an existing approach for static datasets to find the top-k pairs regarding the query and the newly arrived data and then keep the obtained pairs in a candidate result set. As a result, the top-k pairs can be found from the candidate result set. In the other algorithm, the records in the query are preprocessed to be indexed using a novel data structure. By this structure, the data in the monitored stream can be compared with all records in the query at one time, substantially reducing the processing time of finding the top-k results. A series of experiments are performed to evaluate the two proposed algorithms and the experiment results demonstrate that the algorithm with preprocessing outperforms the other algorithm extended from an existing approach for a static environment. |
| Relation | DATA 2012 - Proceedings of the International Conference on Data Technologies and Applications |
| Type | conference |
| dc.contributor | 資科系 | |
| dc.creator (作者) | Li, D.J.;Wang, E.T.;Tsai, Y.-C.;Chen, Arbee L. P. | |
| dc.creator (作者) | 陳良弼 | zh_TW |
| dc.date (日期) | 2012 | |
| dc.date.accessioned | 10-Apr-2015 17:26:26 (UTC+8) | - |
| dc.date.available | 10-Apr-2015 17:26:26 (UTC+8) | - |
| dc.date.issued (上傳時間) | 10-Apr-2015 17:26:26 (UTC+8) | - |
| dc.identifier.uri (URI) | http://nccur.lib.nccu.edu.tw/handle/140.119/74493 | - |
| dc.description.abstract (摘要) | Given a similarity function and a threshold σ within a range of [0, 1], a similarity join query between two sets of records returns pairs of records from the two sets, which have similarity values exceeding or equaling σ. Similarity joins have received much research attention since it is a fundamental operation used in a wide range of applications such as duplicate detection, data integration, and pattern recognition. Recently, a variant of similarity joins is proposed to avoid the need to set the threshold σ, i.e. top-k similarity joins. Since data in many applications are generated as a form of continuous data streams, in this paper, we make the first attempt to solve the problem of top-k similarity joins considering a dynamic environment involving a data stream, named continuous top-k similarity joins. Given a set of records as the query, we continuously output the top-k pairs of records, ranked by their similarity values, for the query and the most recent data, i.e. the data contained in the sliding window of a monitored data stream. Two algorithms are proposed to solve this problem. The first one extends an existing approach for static datasets to find the top-k pairs regarding the query and the newly arrived data and then keep the obtained pairs in a candidate result set. As a result, the top-k pairs can be found from the candidate result set. In the other algorithm, the records in the query are preprocessed to be indexed using a novel data structure. By this structure, the data in the monitored stream can be compared with all records in the query at one time, substantially reducing the processing time of finding the top-k results. A series of experiments are performed to evaluate the two proposed algorithms and the experiment results demonstrate that the algorithm with preprocessing outperforms the other algorithm extended from an existing approach for a static environment. | |
| dc.format.extent | 176 bytes | - |
| dc.format.mimetype | text/html | - |
| dc.relation (關聯) | DATA 2012 - Proceedings of the International Conference on Data Technologies and Applications | |
| dc.subject (關鍵詞) | Continuous data; Continuous queries; Data integration; Data sets; Data stream; Duplicate detection; Dynamic environments; Fundamental operations; Processing time; Similarity functions; Similarity join; Sliding Window; Static environment; Top-k query; Algorithms; Data communication systems; Data structures; Experiments; Pattern recognition; Data processing | |
| dc.title (題名) | On continuous top-k similarity joins | |
| dc.type (資料類型) | conference | en |