（计算机软件与理论专业论文）xml非完全结构查询处理中若干关键技术的研究.pdf

东北大学博士学位论文 摘要 摘要 随着i n t e r n e t 的发展和异构信息源集成技术以及存储技术的进步，网络中涌 现出大量半结构化数据资源。x m l 由于其所具有的自描述性、灵活的数据结构 以及丰富的数据表示能力等特点，逐渐成为数据表示、存储和交换标准之一。近 年来，x m l 非完全结构查询处理技术作为有效管理x m l 文档的关键技术之一， 引起越来越多研究人员的关注。 x m l 非完全结构查询( n o n f u l l ys t r u c t u r e dq u e r y , n f sq u e r y ) 是指满足用 户在缺乏完整的x m l 文档结构信息情况下的查询需求。n f s 查询是近两年出现 的x m l 查询技术，其主要面向缺少完整的结构信息说明以及异构环境下的查询 需求。在实际中，特别是在i n t e m e t 和i n t r a n e t 上，大部分x m l 文档缺少结构说 明或存在异构现象，这使得n f s 查询有着广泛的应用前景。本文就x m l 非完全 结构查询处理技术中的有意义的n f s 查询结果判断技术和基于内容的查询结果 聚类技术进行了深入研究。 有意义的n f s 查询结果判断是n f s 查询处理中非常重要的一环，现有的判 断方法，如x s e a r c h 中的i n t e r c o n n e c t i o nr e l a t i o n s h i p 和t i m b e r 中m l c a ，都是 从一个特定的角度来设计判断标准，缺乏一个准确和全面的定义，这使得它们只 能适用于特定的x m l 文档。另外，现有方法无法适应于大规模x m l 文档，如 x s e a r c h 的索引建立时间和t i m b e r 的查询时间在大规模x m l 文档下远远超出用 户的容忍程度。 本文提出了一种基于模式和实体概念的有意义的n f s 查询结果判断模型一 p e 模型。p e 模型从系统角度出发定义了一种用户普遍接受的判断方法，与具体 的等价模式和等价查询项的判断方法无关，具有可扩展性。基于p e 判断模型， 提出一种具体的基于结构相似性的等价模式判断方法，并给出了一个判断规则。 为了提高n f s 查询的执行效率，设计了模式索引p e 和增强的倒排索引1 2 p ，提 出一种高效的n f s 查询算法，它们不仅可以支持高效的路径查询和关键字查询， 而且可以有效地支持本文提出p e 模型，并有效地利用了现有x m l 数据库系统 中的索引资源，适用于大部分x m l 编码方案。实验表明，本文方法的效率和准 确率要远远高于x s e a r c h 和t i m b e r 系统，适用于大规模x m l 文档。 n f s 查询为非精确查询，在x m l 文档规模较大的情况下，n f s 查询往往返 回大量结果。而以文档为中心的x m l 文档节点包含了大量的文本信息，为了方 便用户快速定位所需信息，通常需要对结果按照内容进行聚类。文档聚类是实现 这一目的的有效技术之一。基于概率模型的聚类方法具有高维数据适用性和簇可 东北大学博士学位论文摘要 解释性特点，被广泛用于文档聚类。但当数据特征超过1 0 0 维时，基于模型的聚 类极容易产生聚类偏斜。目前的研究主要通过设定平衡约束条件，并将聚类问题 看作约束优化问题来防止聚类偏斜。这种解决方法的局限性是：它们均假设数据 分布是均衡的，并且通过直接设定各个簇在数据集合中的比例来改进分配阶段的 数据分配策略，仅适用于可以事先获得平衡约束条件的应用中。在实际应用中， 这种假设在大多数情况下是无法成立的，而且很难事先设定约束条件。 本文认为聚类偏斜产生原因主要有以下三点：簇模型的初始值选择、簇模型 对文档特性的拟合性以及估计样本分散化与簇模型估计泛化的互作用。基于此分 析，提出一种克服聚类偏斜的文档聚类方法m m p c u s t ，它采用基于内容特性的 混合模型作为簇模型，以期更准确地反映各簇基于内容的分布特征，提高分配阶 段的准确率，防止分配阶段样本分散化。在模型重估计阶段，m m p c i u s t 自动选 取模型估计样本，降低估计样本的分散化，有效地防止在估计阶段的模型泛化。 同基于约束的方法相比，m m p c i u s i 不需要事先设定各个簇所占的比例作为约束 条件，因而具有更好的应用性。另外，为了适应不同的应用环境，本文提出了两 种具体的聚类算法m m p c i u s t i 和m m p c i u s t i i ，m m p c l u s t i 算法着重于聚类 质量，而m m p c i u s t i i 算法是m m p c i u s t i 算法的简化，其聚类质量略有降低， 但聚类效率大大高于前者。实验结果显示，m m p c i u s t 在很大程度上抑制了聚类 偏斜的产生，其m a c r o f 1 评价指标优于现有的模型聚类算法。 基于概念的文档特征降维是有效提高文档聚类质量的手段之一。然而现有的 基于概念的特征降维技术没有全面地反映词、概念、文档与主题之间的关系，并 存在如何选取概念的问题。通过潜在概念变量和主题变量的引入，以及词、潜在 概念、文档和主题之间关系的概率表示，本文的模型更全面地反映了词与潜在概 念、文档与主题和潜在概念与主题之间的模糊关系。根据信息论中熵压缩编码理 论，定义了求解潜在概念和文档聚类的全局目标函数，并给出一个类似于确定性 退火算法的求解算法e c t c ，用以获得概念层次树以及在不同层次的概念上文档 题聚类结果，是一种双向软聚类方法。提出一种基于最短描述长度原则的概念选 择方法，用以最终确定概念数目以及对应的文档聚类结果。尽管该方法只是得到 m d l 的局部最优解，但实验表明更为泛化的概念可以取得很好的聚类结果，并 且可以获得更低维的概念空间。 总之，本文提出的基于模式和实体概念的有意义的n f s 查询结果判断模型， 及其实现方法大大提高了n f s 查询处理的质量和效率，而两种文档聚类方法不 仅提高了聚类质量，而且拓宽了文档聚类的应用范围。 关键词x m l 文档数据库，x m l 查询，x m l 非完全结构查询，文档聚类，聚 类偏斜，特征降维，信息论 东北大学博士学位论文 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft e c h n i q u eo fi n t e m e t i n t r a n e t ，a n dt h et e c h n i q u e o fh e t e r o g e n e o u si n f o r m a t i o ni n t e g r a t i o na n ds t o r a g e ，t h e r ea r eh u g ea m o u n t so f s e m i s t r u c t u r a ld a t as u c ha sx m ld o c u m e n te m e r g i n gi nt h en e t w o r k d u et ot h e p r o p e r t i e so fs e l f - d e s c r i p t i o na n df l e x i b l ed a t as t r u c t u r e ，i ti sb e c o m i n go n eo ft h e s t a n d a r d so fd a t ad e f i n i t i o n ，s t o r a g ea n de x c h a n g e a sak e yt e c h n i q u eo fe f f e c t i v e m a n a g e m e n to fx m ld o c u m e n t s ，n o n - f u l l ys t r u c t u r e dx m lq u e r yp r o c e s s i n gh a s b e e nf o c u s e do nb ym o r ea n dm o r er e s e a r c h e r sr e c e n t l y n o n - f u l l ys t r u c t u r a lx m lq u e r yf n f s ) i sat e c h n i q u eo fq u e r y i n gx m l d o c u m e n t sl a c ko ff u l l ys t r u c t u r a li n f o r m a t i o n n f sq u e r yf a c e st h es i t u a t i o n st h a t u s e rd o e s n tk n o wf u l l yt h es t r u c t u r a lk n o w l e d g eo fa nx m ld o c u m e n t ，o ra d o c u m e n td o e s n tp r o v i d ea n ys t r u c t u r a li n f o r m a t i o n ，o rd o c u m e n t sa r eh e t e r o g e n e o u s u n d e re a c hs i t u a t i o n ，au s e rc a n tw r i t ear e g u l a rq u e r yt oe x p r e s sh i si n t e n t i o n a c c u r a t e l y i np r a c t i c e s ，e s p e c i a l l yi ni n t e r n e t i n t r a n e t ，m o s to fx m ld o c u m e n t sa r e l a c ko fs t r u c t u r a li n f o r m a t i o no rh e t e r o g e n e o u s ，s on f sq a e r yb e c o m e sm o r ea n d m o r ep o p u l a ri nr e c e n ty e a r s t h i sd i s s e r t a t i o nd e e p l ys t u d i e st w ok e yt e c h n i q u e so f n o n f u l l ys t r u c t u r e dx m lq u e r yp r o c e s s i n g ：t h ed e t e r m i n a t i o no fm e a n i n g f u lq u e r y r e s u l ta n dt h ec o n t e n tb a s e dr e s u l tc l u s t e r i n g t h ed e t e r m i n a t i o no fm e a n i n g f u lq u e r yr e s u l ti sav e r yi m p o r t a n ts t e pf o rn f s q u e r y m o s to ft h ed e t e r m i n a t i o n s i n p r e v i o u sw o r k s ，s u c h a si n t e r c o r m e c t i o n r e l a t i o n s h i pi nx s e a r c hs y s t e ma n dm l c a i nt i m b e rs y s t e m ，a r ep r o p o s e df r o ma s p e c i a lv i e w , s ot h e ya r ea p p l i e dt os o m ek i n d so fx m ld o c u m e n t so n l y m o r e o v e r , t h e yb e c a m ei n f e a s i b l ef o rl a r g es c a l ed o c u m e n t s ，s u c ha sb o t ht h et i m eo f e s t a b l i s h i n gt h ei n d e xi nx s e a r c ha n dt h et i m eo fq u e r y i n gi nt i m b e ri sf a rb e y o n d u s e r st o l e r a n c e t h i sd i s s e r t a t i o np r o p o s e sag e n e r a ld e t e r m i n a t i o nm o d e lb a s e do nt h ec o n c e p to f p a t t e r na n di n s t a n c e ，c a l l e da sp em o d e l t h ep em o d e li sas y s t e m - o r i e n t e dm o d e l a n dc a nb ea c c e p t e dw i d e l yb yu s e r s i nf a c t ，t h ep em o d e li s j u s t as c a l a b l e f r a m e w o r ka n di n d e p e n d e n to ft h ed e f i n i t i o no fe q u i v a l e n tp a t t e r na n de q u i v a l e n t q u e r yt e r m u n d e rt h ef r a m e w o r ko ft h ep em o d e l ，t h i sd i s s e r t a t i o np r o p o s e sa s t r u c t u r es i m i l a r i t yb a s e dm e t h o dt oc o m p u t ee q u i v a l e n tp a t t e r n ，a n dp u tf o r w a r d sa d e t e r m i n a t i o nr u l e ，t oi m p r o v et h e e f f i c i e n c yo fn f sq u e r y i n g ，t h i sd i s s e r t a t i o n 东北大学博士学位论文 a b s t r a c t d e s i g n sap a t t e r ni n d e x ( p e i n d e x ) ，a ne n h a n c e di n v e r t e di n d e x ( 1 2 p ) ，a n daq u e r y i n g a l g o r i t h m w i t ht h e s et e c h n i q u e s ，t h es y s t e mi nt h i sd i s s e r t a t i o ns u p p o r t sn o to n l y p a t hq u e r y i n ga n dk e y w o r db a s e dq u e r y i n g ，b u ta l s ot h ep em o d e le f f e c t i v e l ya n d e f f i c i e n t l ym o r e o v e r , t h ee x i s t i n gi n d e x i n gt e c h n i q u e s ，s u c ha ss t r u c t u r a li n d e xa n d i n v e r t e df i l ei n d e xi nc u r r e n tx m ld a t a b a s e s ，c a nb eu t i l i z e d ，a n dm o s tx m l e n c o d i n g s c a l lb e a p p l i e d t h e e x t e n s i v ee x p e r i m e n t ss h o wt h a tt h es y s t e m o u t p e r f o r m sx s e a r c ha n dt i m b e ro nb o t hp r e c i s i o n a n de f f i c i e n c y , e s p e c i a l l yf o r l a r g es c a l ex m l d o c u m e n t s a sak i n do fa m b i g u o u sq u e r i e s ，a nn f sq u e r ya l w a y sr e t u r n sm a n yr e s u l t sf o ra l a r g e - s c a l ex m l d o c u m e n t t oh e l pu s e rs e a r c ht h ei n f o r m a t i o ni nah u g ea m o u n to f t e x ti n f o r m a t i o nc o n t a i n e di nt h en o d eo fad o c u m e n t - c e n t r i cx m ld o c u m e n t ，t h e c o n t e n tb a s e dr e s u l tc l u s t e r i n gi sr e q u i r e da b s o l u t e l y d o c u m e n tc l u s t e r i n gi so n eo f t e c h n i q u e ss a t i s f y i n g t h i s r e q u i r e m e n t 。a s o n eo fp r i m a r yc l u s t e r i n gm e t h o d s ， p r o b a b i l i s t i cm o d e l b a s e dc l u s t e r i n g i ss u i t a b l ef o rh i g h d i m e n s i o n a ld a t al i k e d o c u m e n t s f u r t h e r m o r e ，b e c a u s eo ft h ei n t e r p r e t a b i l i t yo fc l u s t e r i n gr e s u l t s ，i th a s b e e nu s e dw i d e l yi nd o c u m e n tc l u s t e r i n g i th a sb e e np r o v e dt h a tw h e nd a t ai si nh j i 曲 d i m e n s i o n a ls p a c e ( 1 0 0 ) ，m o d e l - b a s e dc l u s t e r i n gq u i t eo f t e ng e n e r a t e ss o m es k e w e d c l u s t e r st h a ta r ee m p t yo re x t r e m e l ys m a l l ，w h i c hi n f l u e n c e st h ec l u s t e r i n gq u a l i t y s e r i o u s l y t op r e v e n tt h es k e w e dc l u s t e r s ，t h eb a l a n c e dc l u s t e r i n gm e t h o d sw e r e p r o p o s e di nt h ep a s t ，t h e i ri d e ai st os e tt h ep r o p o r t i o no fe a c hc l u s t e rt ot h ew h o l e d a t aa st h ea l g o r i t h m sc o n s t r a i n t ，a n dt h e ya r ea p p l i e dm o s t l yi n t ot h es i t u a t i o n s w h e r et h ec l u s t e r sh a v et h ec o m p a r a b l es i z e a c t u a l l yi t i sd i f f i c u l tt os e tt h i s c o n s t r a i n ti nm o s te a s e s ，a n dt h ep r e v i o u sw o r k sj l i s tc o n s i d e ri t a st h e c o n s t r a i n t b a s e do p t i m i z a t i o np r o b l e m ，w h i l en of l l r t h e rs t u d i e so nw h yt h es k e w e d c l u s t e r sg e n e r a t ew e r ed o n e t h eb a s i ci d e ai st od e s i g nac l u s t e r i n ga l g o r i t h mt h a tc a l lg r o u pt h ed o c u m e n t s i n t ot h ec l u s t e r so fi n h e r e n ts i z ew i t h o u ta n yb a l a n c i n gc o n s t r a i n t t h i sd i s s e r t a t i o n a n a l y z e st h a tt h e r ea r et h r e ef a c t o r sc a u s i n gt h es k e w ：t h ei n a p p r o p r i a t ei n i t i a lm o d e l ， t h eu n f i t n e s so fc l u s t e rm o d e la n dt h ei n t e r a e t i o nb e t w e e nt h ed e c e n t r a l i z a t i o no f e s t i m a t i o ns a m p l e sa n dt h eo v e r g e n e r a l i z e dc l u s t e rm o d e l t h es o l u t i o nf o c u s e so n t h el a s tt w o f a c t o r sa n d p r o p o s e s ac o n t e n t - b a s e d p a r t i a lr e - e s t i m a t i n g d o c u m e n t c l u s t e r i n ga l g o r i t h m ( m m p c i u s i ) ，w h i c hh a st w of e a t u r e s ：f i r s t l y ，t os o l v e t h eu n f i t n e s sp r o b l e m ，m m p c i u s ta p p l i e sat w o c o m p o n e n t m i x t u r em o d e l ( t o p i c b a s e dm o d e la n dg e n e r a lm o d e l ) ，w h i c hc a nm o d e ld o c u m e n tc o n t e n tm o r e a c c u r a t e l ya n ds h o w sag o o d n e s so ff i t s e c o n d l y ，t os o l v et h eo v e r g e n e r a t i o n v 东北大学博士学位论文 a b s t r a c t p r o b l e m ，f o re a c hc l u s t e r ，i ns t e a do fa l lt h ed o c m n e n t s ，b u tap a r to fd o c u m e n t st h a t m o s tr e l e v a n tt ot h ec o r r e s p o n d i n gc l a s s ，a r es e l e c t e da u t o m a t i c a l l ya st h es a m p l e st o r e e s t i m a t et h ec l u s t e rm o d e l i tr e d u c e st h ed e c e n t r a l i z a t i o no fe s t i m a t i o ns a m p l e s ， a n dt h e np r e v e n t st h em o d e lt ob ee s t i m a t e do v e r - g e n e r a l l y c o m p a r e dw i t ht h e b a l a n c e b a s e dw o r k s ，m m p c i u s td o e s n tn e e dt h ep r i o rk n o w l e d g ea b o u tt h e p r o p o r t i o no fe a c hc l u s t e r ，a n di s m o r ef e a s i b l ei n t h ep r a c t i c a la p p l i c a t i o n s i n a d d i t i o n ，t h i sd i s s e r t a t i o np r o p o s e st w oa l g o r i t h m s ：m m p c i u s t - ia n dm m p c i u s t 一1 1 m m p c i u s t im o r ef o c u s e so nt h eq u a l i t yo fc l u s t e r i n gt h a nt h ee f f i c i e n c y , w h i l e m m p c i u s t - l ii sav e r s i o no fi m p r o v i n gt h ee f f i c i e n c yg r e a t l ya tt h ec o s to fs u b t l e r e d u c t i o no fq u a l i t y t h ee x p e r i m e n t ss h o wt h a tm m p c i u s tp r e v e n t st h es k e w e d c l u s t e r si nag r e a td e g r e e ，a n di t sm a c r o f 1m e a s u r eo u t ! ：i e r f o r m st h ep r e v i o u s m e t h o d s t h et e c h n i q u eo fc o n c e p tb a s e df e a t u r er e d u c t i o ni so n eo ft e c h n i q u e st h a t i m p r o v i n gt h ec l u s t e r i n gq u a l i t y h o w e v e r , m o s to fc o n c e p tb a s e dt e c h n i q u e sd on o t m o d e lt h er e l a t i o n s h i pa m o n gw o r d s ，c o n c e p t s ，d o c u m e n t sa n dt o p i c s ，a n dd on o t s t u d yo nt h ec o n c e p ts e l e c t i o n t h i sd i s s e r t a t i o ni n t r o d u c e st h el a t e n tc o n c e p tv a r i a b l e a n dt h el a t e n tt o p i cv a r i a b l e ，a n dm o d e l st h ea m b i g u o u sr e l a t i o n s h i pa m o n gw o r d s ， l a t e n tc o n c e p t s ，d o c u m e n t sa n dl a t e n tt o p i c si nt h ef o r mo fp r o b a b i l i t y ag l o b a l o b j e c t i v ef u n c t i o ni sg i v e nt of i n dt h el a t e n tc o n c e p t sa n dd o c u m e n t c l u s t e r sa c c o r d i n g t ot h er a t e - - d i s t o r t i o nt h e o r y , a n da na n n e a l - l i k ea l g o r i t h me c t ci sd e s i g n e dt oe x t r a c t t h eh i e r a r c h i c a lt r e eo fl a t e n tc o n c e p t sa n dt og r o u pt h et e x t su n d e rc o r r e s p o n d i n g c o n c e p th i e r a r c h y ac o n c e p ts e l e c t i o n m e t h o di s p r o p o s e d b a s e do nm i n i m a l d e s c r i p t i o nl e n g t hc r i t e r i a a l t h o u g hi tg e t st h el o c a lo p t i m i z a t i o no fm d l ，t h e e x p e r i m e n ts h o w st h a tw i t ht h em o r eg e n e r a lc o n c e p t ，t h eb e t t e rc l u s t e r i n gq u a l i t ya n d t h el o w e rd i m e n s i o no f c o n c e p ti sa r c h i v e d i ns u m m a r y , a st h ek e yt e c h n i q u e so fx m ld o c u m e n td a t a b a s e s ，n o n f u l l y s t r u c t u r e dx m lq u e r yh a sap r o m i s i n gf u t u r e t h ep em o d e lb a s e do nt h ec o n c e p to f p a t t e r na n de n t i t y , a n di t si m p l e m e n t i n ga p p r o a c hi m p r o v eg r e a t l yt h eq u a l i t ya n d e f f i c i e n c yo fn f sq u e r y i n g m o r e o v e r , t w ok i n d so fd o c u m e n tc l u s t e r i n gp r o p o s e di n t h i sd i s s e r t a t i o na c h i e v em u c hb e t t e rq u a l i t yo fc l u s t e r i n ga n dc a nb eu s e dt om o r e a p p l i c a t i o n s k e y w o r d sx m ld o c u m e n td a t a b a s e s ，x m lq u e r nn o n f u l l ys t r u c t u r e dx m lq u e r y d o c u m e n tc l u s t e r i n g ，c l u s t e r i n gs k e w , f e a t u r er e d u c t i o n ，i n f o r m a t i o nt h e o r y v 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 学位论文作者签名：办甍缸 日期：1 h 彳、1 ，。li 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论 文的全部或部分内容编入有关数据库进行检索、交流。 寸j - 学位论文作者签名：细兄轧 口 别：w 矶2 。认 另外，如作者和导师不同意网上交流，请在下方签名；否则视为 同意。 学位论文作者签名： 签字日期： 导师签名： 签字日期： 东北大学博士学位论文 i 1 研究背景 第一章绪论 从6 0 年代末开始，数据库技术经历了层次数据库、网状数据库和关系数据 库而进入数据库管理系统( d b m s ) 阶段至今，数据库技术的研究不断取得进展。 8 0 年代，关系数据库成为发展的主流，几乎所有新推出的d b m s 产品都是关系 型的。然而，随着网络技术和软件技术的飞速发展，特别是i n t e m e t 和i n t i 锄e t 技术的发展，使得非结构化数据的应用日趋扩大。x m l 由于其所具有的自描述 性、灵活的数据结构以及丰富的数据表示能力等特点，逐渐成为数据表示、存储 和交换标准之一。作为有效管理x m l 文档的有效技术之一，x m l 文档数据库 引起越来越多的研究人员的关注。 x m l 文档数据库系统中通常将x m l 文档分为两种：富含值信息的x m l 文 档( d a t a r i c h ) 和富含文本信息的x m l 文档( t e x t r i c h ) 。富含值信息的x m l 文 档，又称以数据为中心的x m 文档( d a t a - c e n t r i c ) ，其中包含的大部分信息为值 信息，如数值、字符串、日期、逻辑值等，结构信息用来组织信息。这类x m l 文档通常用于应用程序间的数据交换，如e d i 以及由传统数据库( 如关系数据 库) 中转换生成的x m l 文档。富含文本信息的x m l 文档，又称以文档为中心 的x m l 文档( d o c u m e n t c e n t r i c ) ，其中的节点包含大量的文档信息，其常见于 i n t e m e t 上的网页、商业文档、数字图书馆，如d b l p 、s i v i o d r e c o r d 、x m a r k 等都大量包含了文档信息。 目前大多数的x m l 文档数据库系统研究主要面向富含值信息的x m l 文档， 主要研究方向为x m l 文档的存储、索引、查询模型和执行等方面。通常，富含 值信息的x m l 文档特点是结构规整、说明完善，并且x m l 文档的查询模型都 是建立在用户完全了解x m l 文档结构的基础上的。然而实际的x m l 文档、尤 其是在i n t e m e t 上的x m l 文档大多是富含文档信息的x m l 文档，这类文档通常 缺少结构说明或存在异构现象，例如d b l p 、s i g m o d r e c o r d 、c i t e s e e r 等， 尽管都是描述科技文章的x m l 文档，但是它们的组织结构各不相同。用户为了 满足一个查询需求，不得不事先了解x m l 文档的结构信息、或者分别为每一个 异构的x m l 文档编写不同的查询表达式，这往往使得用户感到非常不方便。而 x m l 非完全结构查询( n o n f u l l ys t r u c t u r e dq u e r y , n f s q u e r y ) 处理技术正是为 解决这一问题提出的。 东北大学博士学位论文 绪论 除了传统x m l 查询处理所涉及的技术外，n f s 查询处理关键技术还主要包 括： ( 1 )查询模型。为了满足用户不了解文档结构情况下的查询需求，n f s 查询模型不仅仅需要满足类似于r 中的关键字检索需求，还需要 满足带有部分结构、甚至完全结构的查询需求。 ( 2 )查询结果粒度的确定。n f s 查询返回的结果为节点，不是整个x m l 文档。然而节点可以是x m l 文档中的任意一个层次，如果层次较 低，则返回结果过于泛化，所以n f s 查询需要确定查询结果粒度。 ( 3 )有意义的查询结果判断。由于n f s 查询允许用户用不完整的结构 信息来书写查询表达式，查询结果中通常包含大量没有意义的结 果，所以n f s 查询首先要解决的问题就是如何判断查询结果是否 有意义。对于大规模的x m l 文档来说，这种非精确的查询结果的 数量非常惊人，如何过滤无意义的查询结果是n f s 查询重要研究 方向之一。 ( 4 )基于内容的查询结果聚类。以文档为中心的x m l 文档中的节点包 含了大量的文本信息。对于大规模的x m l 文档来说，n f s 查询往 往返回大量的结果，而且返回结果是关于多个主题的。为了方便用 户快速定位所需信息，通常需要对结果按照内容进行聚类。 ( 5 ，查询结果排序，即根据与查询表达式的相关程度排序查询结果。 1 2 本文工作 本文主要就x m l 非完全结构查询处理中的有意义的n f s 查询结果判断方法 和基于内容的查询结果聚类方法进行了深入的研究。 1 2 1 研究动机 目前，有意义的n f s 查询结果判断方法有两类：一是基于先验知识韵判断， 其主要是由专家事先给出的判断知识，然后根据这些知识来过滤查询结果。另一 类是无先验知识的判断，主要是利用节点的最近公共祖先以及标签信息来判断节 点问是否有意义。同基于先验知识的判断相比，显然无先验知识的判断方法的应 用价值更高。本文着重研究无先验知识的判断方法。现有的无先验知识判断方法 存在如下问题： 现有的解决方案均从某一个角度来得出判断标准，没有一个准确和全面 的定义。例如x s e a r c h 中的i n t e r c o n n e c t i o nr e l a t i o n s h i p 适用于标签名称 不存在歧异的情况，查询结果过于宽松，导致大量无意义的查询结果。 2 东北大学博士学位论文 绪论 t i m b e r 中的m l c a 适用于x m l 文档完整的情况，查询结果过于严格， 导致大量有意义的结果被过滤。 扩展性。现有的研究往往无法适应于大规模x m l 文档，如x s e a r c h 在 建立离线索引时，其时间复杂度为o ( i r 2 1 ) ，为文档节点个数，其只适 用于小规模的x m l 文档查询。t i m b e r 要求无论查询表达式如何，必须 首先将所有同一标签名的节点返回，有意义的n f s 查询结果判断须在其 它谓词操作之前，不利于优化查询计划，降低了执行效率。 以文档为中心的x m l 文档中的节点包含了大量的文本信息，由于用户不完 全了解文档结构，n f s 查询往往返回大量的结果，而且查询结果是关于多个主题 的。为了方便用户快速定位所需信息，通常需要对结果按照内容进行聚类。文档 聚类是实现基于内容的n f s 查询结果聚类的有效手段之一，然而现有的方法存 在以下问题： -在高维数据中，聚类偏斜现象普遍存在。现有的研究都是从基于约束的 平衡聚类的角度来展开的，很少从聚类偏斜产生的本质出发来展开研究。 而且基于约束的平衡聚类由于需要约束条件的先验知识，因而无法适用 于实际应用。 由于文档属于高维数据，在对文档聚类前，通常需要特征降维。同特征 选取相比，基于概念的特征降维可以有效解决高维和语义相关问题。然 而现有的