一种支持多目标的数据流操作语言

随着数据流在各个应用领域的涌现和广泛应用，数据流相关的研究已经成为数据库技术中一个新的研究方向，并得到了越来越多的关注．数据流的操作语言作为用户与数据流管理系统之问进行语义交换的桥梁，从很大程度上体现出了数据流处理的特点．提出了一种数据流管理系统中支持多目标的数据流操作语言．它可以同时完成对数据流和关系表的操作．此外针对数据流的特性，语言中还引入了时间戳，时间粒度，连续查询，近似查询等相关概念，并以丰富灵活的语法支持了各种相关技术．     

基于查询片段松弛的XML小枝近似查询方法

为了解决普通用户对XML文档的近似查询问题,提出一种基于查询片段松弛的XML小枝近似查询方法.该方法利用查询历史推测用户偏好,进而根据用户偏好为原始小枝查询中的每个查询片段分配重要程度,然后基于查询片段重要程度对原始小枝查询条件进行松弛处理,最不重要的查询片段最先松弛,从而确保获取最为相关的查询结果;最后,根据对原始查询和用户偏好的满足程度,将得到的满足松弛查询条件的结果进行排序.实验结果表明,本文提出的查询松弛和结果排序方法能够获得较高的查全率和准确率,并且能较好地满足用户需求和偏好.     

多用户偏好的 Top-k 查询处理算法研究磁

传统的 Top-k 查询处理都是利用单用户偏好来计算评分函数,这种方法有极大的局限性。针对基于多用户偏好的 Top-k 查询处理问题进行研究,为了提高查询效率,首先提出了预处理算法 PA 与 PVA ,生成一些具有代表性的系统用户偏好,并据此将初始数据集进行全排序,保存在物化视图中,以便利用它们进行 Top-k 查询。然后,提出了处理 Top-k 查询的 VBA 算法且进行了正确性与完备性论证。最后,实验结果表明,该算法比直接在原数据集中查询的效率有极大的提高。     

CP-nets上的正则化路径查询

从表示偏好知识的条件偏好网(CP-nets)模型出发,研究该模型上的正则化路径查询问题.首先从数据库的观点给出偏好数据库的两类查询(顶点查询和路径查询),并证明偏好数据库的表达能力强于关系数据库.其次,通过构造正则表达式的语法解析二叉树,求出各自原子表达式诱导的可达关系,从而利用动态规划法求解出CP-nets上正则表达式所诱导的可达关系,并证明算法的正确性,分析其组合复杂度.最后,给出正则化路径查询的可能应用,即可在偏好操作序列的规划中使用.     

数据流上Ad Hoc查询的自适应处理算法

对数据流上的Ad Hoc查询进行自适应处理,需要保证已有查询计划快速在线更新和迁移,但现有方法实现新旧查询计划的更新需要大量的滑动窗口状态转换。为此,提出一种Ad Hoc查询自适应处理算法。该算法基于数据流概要分布特性和自定义评分模型,快速计算出现有查询计划的最佳增量更新,以实现新到达的 Ad Hoc 查询处理,降低新旧查询计划切换时间。在数据流benchmark Linear Road提供的高速公路数据集上进行实验,结果表明,与MS、PT方法相比,该算法可较快完成新旧查询计划的切换。     

保护位置隐私近邻查询中隐私偏好问题研究

近年来,位置服务中的隐私保护问题得到了研究者的持续关注,特别是近邻查询中位置隐私保护问题更是得到了广泛的研究.已有工作缺少对查询者个性化隐私偏好约束的系统研究,位置隐私与查询服务质量的兼顾,在隐私偏好约束下尤为困难:(1)偏好强调个性与隐私模型侧重共性存在矛盾;(2)偏好对查询中间结果动态可控依赖与查询简化中间结果的思想相抵触;(3)连续查询中,支持隐私偏好存在基于候选解集攻击的风险.结合上述问题,提出保护位置隐私近邻查询中的隐私偏好问题,从位置隐藏原理及近邻查询性能与保护位置隐私内在制约机理的角度,对已有的位置隐藏与查询处理方法的性能及其对隐私偏好支持能力进行论述分析.进一步地,对支持隐私偏好与保护位置隐私查询内在制约机理进行了剖析,分析保护位置隐私近邻查询中支持隐私偏好需解决的主要问题,并对所归纳问题的可能解决方法进行了展望.     

基于用户反馈的top-k查询修改算法

top-k查询主要用来从海量的数据中返回用户最为偏好的k个对象.目前已经有大量的研究工作致力于top-k查询中的性能研究,近年来针对top-k查询结果进行解释的研究逐渐得到了广泛的关注.在top-k查询中,由于用户不能精确地指定自己的偏好,因此针对top-k查询的结果用户可能产生这样的质疑:"既然连对象p都出现在top-k结果中,为什么我期望的对象m块没有出现在top-k结果/"针对用户这样的疑问,提出了一种基于用户反馈的top-k查询修改算法,该算法首先定义了用来衡量初始化top-k查询变化的评估模型函数,基于该评估模型函数,使用抽样方法得到候选权重集合,针对每一个候选权重通过渐进式top-k算法来得到新的最优化查询.最后在模拟数据上验证了提出算法的效率.     

基于最小生成树的数据流窗口连接优化算法

与传统关系数据库不同,数据流管理系统主要处理并发的连续查询.由于查询可能随时增删,所以其主要关注适合查询增删的并发连续查询优化,而不是单条查询优化.提出适合频繁增删查询环境下的数据流窗口连接优化算法.对于新注册的查询以类似最小生成树算法写出数据流的探测序列,然后在不更改其他查询探测序列顺序的情况下尽量合并,减少重复计算.注册或删除查询并不影响其他的查询计划,不需要执行繁琐的查询计划迁移.理论分析和实验证明,该算法简单,优化性能在可接受的范围内,尤其适合查询更新频率较高的系统.     

基于小波变换的数据流快速索引的研究

提出了一个新颖的方案来概要和索引分布式数据流,通过采用离散小波变换在线提取数据流特征,并插入到高维索引结构序列中,来减少维护索引结构所需的开销。实验表明该方法在分析模式和相关性检测上改进了查询精度和响应时间。     

空间文本数据流上连续查询评估技术综述

空间文本数据流上连续查询(CQST)在基于位置的服务中应用广泛,其在不断更新的数据流上,持续监控满足空间和文本约束的结果.为了将数据流中的对象尽快匹配给CQST,在CQST上构建高效的过滤技术是关键.CQST查询评估方法——为查询选取恰当的空间文本索引,构建高效的过滤策略提升索引的空间文本过滤性能,为数据流中到来的对象...     

基于Aurora系统的持续型查询语言设计与实现

随着新型数据应用的不断出现,针对流形态数据的数据流管理系统已经成为数据管理领域研究的新热点。针对目前通用数据流管理系统只支持基于操作符流图的查询表达方式这一不足,设计了一种新的持续型数据流查询语言,并在通用数据流处理系统Aurora上进行了实现。为验证新语言的表达能力,该系统使用新语言定义了数据流基准测试Linear Road Benchmark的查询集,在Aurora系统上部署运行。测试结果表明针对Linear Road Benchmark的测试用例,新语言具有较完备的语义和良好的表达能力。     

基于Dandelion编码生成有界树宽CP-nets

针对条件偏好网络（CP-nets）图模型在进行推理运算时的高时间复杂度的问题,提出了一种基于Dandelion编码生成有界树宽的CP-nets（BTW-CP-nets Gen）算法。首先,通过Dandelion编码与树宽为k的树结构（k-tree）之间的双向映射原理推导出Dandelion编码与k-tree之间的解码与编码算法,实现编码与树结构的一对一映射;其次,利用k-tree来约束CP-nets结构的树宽,并利用k-tree的特征树得到了CP-nets的有向无环图结构;最后,利用离散多值函数的双射计算出各CP-nets结构节点的条件偏好表,然后针对生成的有界树宽CP-nets进行占优查询检测。理论分析和实验数据表明,与Pruffer编码生成k-tree（Pruffer code）算法相比,BTW-CP-nets Gen算法的运行时间在生成简单结构和复杂结构时的下降幅度分别为21.1%和30.5%;而BTW-CP-nets Gen算法所生成的图模型在进行占优查询时的节点遍历比在简单结构和复杂结构上分别提高了18.48%和29.03%。BTW-CP-nets Gen算法在更短的时间内,占优查询时遍历的节点率更高。可见,BTW-CP-nets Gen算法在图模型的推理中能够有效提高算法效率。     

基于短序列分组和拼接策略的子序列快速查询算法

子序列查询技术在金融、商业、医疗等领域均有重要应用,但因DTW（dynamic time warping）等相似性比对算法的时间复杂度较高,子序列长度对检索时间影响很大,限制了数据集上长子序列检索的效率。针对这一问题提出一种子序列快速查询算法。首先对数据集中特定长度下所有子序列进行分组并标记出代表性子序列;然后在查询时将查询序列切分成定长的小段序列,并用DTW算法确定与小段序列相似的代表子序列候选集;最后对候选集进行序列拼接,获取到查询结果序列。实验表明新算法效率较典型算法提高约10倍。     

面向路网连通关系的车辆轨迹数据查询技术研究

定位及通信技术的发展使获取和传输移动车辆的轨迹信息成为可能。从车辆轨迹数据中可以提取出大量的交通信息,这些信息是对交通状况的一个直接和全面的反映。但由于轨迹数据固有的网络特性及时空特性,使针对此类数据的查询成为一个难点,其中关键技术包括建立用于车辆轨迹数据的索引结构及其对应的轨迹数据查询语言。在比较现有轨迹数据索引结构的基础上,对轨迹数据查询语言的分类及其与索引结构之间的调用关系进行了初步的探讨,提出了面向连通关系的查询语言（connectivity-oriented query language, CQL）的定义、分类及实现方法,并简要讨论了车辆轨迹数据查询原型系统的结构和实现方法。     

AN INTERACTIVE SEARCH ASSISTANT ARCHITECTURE BASED ON INTRINSIC QUERY STREAM CHARACTERISTICS

Search engine query log mining has evolved over time to more like data stream mining due to the endless and continuous sequence of queries known as query stream. In this paper, we propose an online frequent sequence discovery (OFSD) algorithm to extract frequent phrases from within query streams, based on a new frequency rate metric, which is suitable for query stream mining. OFSD is an online, single pass, and real-time frequent sequence miner appropriate for data streams. The frequent phrases extracted by the OFSD algorithm are used to guide novice Web search engine users to complete their search queries more efficiently. YourEye, our online phrase recommender is then introduced. The advantages of YourEye compared with Google Suggest, a service powered by Google for phrase suggestion, is also described. Various characteristics of two specific Web search engine query logs are analyzed and then the query logs are used to evaluate YourEye. The experimental results confirm the significant benefit of monitoring frequent phrases within the queries instead of the whole queries because none-separable items. The number of the monitored elements substantially decreases, which results in smaller memory consumption as well as better performance. Re-ranking the retrieved pages based on past users clicks for each frequent phrase extracted by OFSD is also introduced. The preliminary results show the advantages of the proposed method compared to the similar work reported in Smyth et al.     

不确定数据流上的并行Skyline查询算法

不确定数据流上的Skyline查询技术逐步引起研究者的关注,传统的集中式流处理算法难以满足海量数据的查询需求,并且云计算所提供的海量计算资源和有效的存储管理模式,为研究并行Skyline查询技术提供了充足的条件。基于上述事实,提出了一种不确定数据流上的并行Skyline查询算法(parallel Skyline over uncertain data streams,PSUDS)。该算法通过交叉划分滑动窗口的方式,将集中式流查询转化为并行处理,以并行执行的方式来解决集中式算法处理性能不足的问题。大量实验结果表明,该算法具有较好的并行可扩展性。     

可视化查询语言CQL的实现

为使得许多非计算机专业的用户，尤其是未接受过数据库编程语言训练的用户，能够独立操纵一个数据库系统，有效地解决工作、生活中的问题，我们研究并提供了一种空间数据库可视化查询语言CQL。借助该语言，用户可以直观、方便地操纵数据库系统或查询数据库信息。本文介绍了CQL语言的语素、语义、语法及语用的定义，同时给出了CQL编辑器、编译器和查询结果可视化的设计方法。     

基于网格索引的数据流子空间概率轮廓查询

在数据流子空间上的连续概率轮廓查询(CPSQS)基础上,提出一种基于网格索引结构的概率轮廓查询算法。采用适合于子空间轮廓计算的网格索引结构,将数据空间划分成若干个格,利用格间的支配关系,减少对象之间的比较次数。同时挖掘全空间与子空间上格的概率上下界关系,设计有效的剪枝策略提高CPSQS算法的性能。理论分析和实验结果表 明,该算法能满足实际应用中用户的个性化查询要求,降低查询响应时间。     

The CQL continuous query language: semantic foundations and query execution

CQL, a continuous query language, is supported by the STREAM prototype data stream management system (DSMS) at Stanford. CQL is an expressive SQL-based declarative language for registering continuous queries against streams and stored relations. We begin by presenting an abstract semantics that relies only on “black-box” mappings among streams and relations. From these mappings we define a precise and general interpretation for continuous queries. CQL is an instantiation of our abstract semantics using SQL to map from relations to relations, window specifications derived from SQL-99 to map from streams to relations, and three new operators to map from relations to streams. Most of the CQL language is operational in the STREAM system. We present the structure of CQL's query execution plans as well as details of the most important components: operators, interoperator queues, synopses, and sharing of components among multiple operators and queries. Examples throughout the paper are drawn from the Linear Road benchmark recently proposed for DSMSs. We also curate a public repository of data stream applications that includes a wide variety of queries expressed in CQL. The relative ease of capturing these applications in CQL is one indicator that the language contains an appropriate set of constructs for data stream processing. Edited by M. Franklin