流数据复杂聚类查询处理算法概论.pdf

第4 1 卷第6 期 南　京　航　空　航　天　大　学　学　报 V o l. 4 1N o. 6 　　　　 2009 年 12 月 Jou rn a l o f N anj in g U n iver sity o f A eron au t ics A st ron au t ics　　　　　D ec. 2009 流数据复杂聚类查询处理算法 刘宇雷　秦小麟　储网林　黄　瑛 (南京航空航天大学信息科学与技术学院, 南京, 2 100 16) 摘要: 流数据上的连续查询, 尤其连续聚类查询是流数据处理研究的难点。草图算法能够计算流数据上等值连接 大小的高精度近似值, 而直方图算法能够较精确地统计流数据的分布。本文结合这两种算法的优势, 提出了一种 能够高效处理流数据上复杂聚类查询的算法。理论和实验结果表明, 该算法具有较高的精度和较小的空间复杂 度。 关键词: 流数据; 连续查询; 聚类查询 中图分类号: T P 30 1　　　文献标识码: A 　　　文章编号: 100526 15 (2009) Com plex D a ta Stream A ggrega t ion Query Proce ss in g A lgor ithm s L iu Y u le i, Q in X iaolin , Ch u W ang lin , H uang Y ing (Co llege o f In fo rm at ion Scien ce an d T echno logy, N anj ing U n iver sity o f A eron au t ics A st ron au t ics, N anj ing, 2 100 16, Ch in a) A bstract: Con t inuou s qu er ie s over data st ream s, e sp ecia lly agg regat ion qu er ie s are on e o f th e d iff icu lt p rob lem s in data st ream p ro ce ssin g. T h e a lgo r ithm b a sed on th e sk etch e st im ate s th e equ a l jo in size o f data st ream w ith h igh p recision an d g ive s th e d ist r ibu t ion o f data st ream accu rately. A n eff icien t data st ream agg regat ion qu ery p ro ce ssin g a lgo r ithm is p rop o sed b a sed on sk etch in g an d h isto g ram s tech . . n iqu e s T h e a lgo r ithm can p rov ide app rox im ate an sw er s to a cer ta in k in d o f com p lex agg regate qu er ie s T h e th eo ry an d exp er im en ta l re su lt s show th at th e a lgo r ithm h a s h igh p reci