Title | ||
---|---|---|
On processing continuous frequent K-N-match queries for dynamic data over networked data sources |
Abstract | ||
---|---|---|
Similarity search is one of the critical issues in many applications. When using all attributes of objects to determine their similarity, most prior similarity search algorithms are easily influenced by a few attributes with high dissimilarity. The frequent k-n-match query is proposed to overcome the above problem. However, the prior algorithm to process frequent k-n-match queries is designed for static data, whose attributes are fixed, and is not suitable for dynamic data. Thus, we propose in this paper two schemes to process continuous frequent k-n-match queries over dynamic data. First, the concept of safe region is proposed and four formulae are devised to compute safe regions. Then, scheme CFKNMatchAD-C is developed to speed up the process of continuous frequent k-n-match queries by utilizing safe regions to avoid unnecessary query re-evaluations. To reduce the amount of data transmitted by networked data sources, scheme CFKNMatchAD-C also uses safe regions to eliminate transmissions of unnecessary data updates which will not affect the results of queries. Moreover, for large-scale environments, we further propose scheme CFKNMatchAD-D by extending scheme CFKMatchAD-C to employ multiple servers to process continuous frequent k-n-match queries. Experimental results show that scheme CFKNMatchAD-C and scheme CFKNMatchAD-D outperform the prior algorithm in terms of average response time and the amount of produced network traffic. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/s10115-011-0413-5 | Knowl. Inf. Syst. |
Keywords | Field | DocType |
frequent k-n-match query,safe region,scheme cfkmatchad-c,continuous frequent k-n-match query,dynamic data,static data,scheme cfknmatchad-d,prior algorithm,networked data source,scheme cfknmatchad-c,similarity search | Data mining,Static data,Computer science,Server,Response time,Theoretical computer science,Dynamic data,Nearest neighbor search,Speedup | Journal |
Volume | Issue | ISSN |
31 | 3 | 0219-3116 |
Citations | PageRank | References |
2 | 0.37 | 30 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Shih-chuan Chiu | 1 | 43 | 4.82 |
Jiun-Long Huang | 2 | 592 | 47.09 |
Jen-He Huang | 3 | 3 | 0.73 |