个人数据空间介绍
数字技术和web的发展使人们每天面临处理的信息量剧增,个人数据信息管理日益成为一个重要的研究问题。一方面计算和通讯会越来越普及,以至于数据量以难以想象的速度急剧膨胀;另一方面,在数据管理中却有一样东西是基本维持不变的--那就是人的注意力和人能够用在数据管理上的时间。也就是说目前计算技术的发展是使人更加应接不暇加速到来的信息,而没有丝毫减轻人们的负担,因此个人数据空间管理日益成为一个重要的研究方向。与传统的数据管理技术不同,个人数据有独特的性质。多样性、共存性、演化性、分布性是其主要的几个特性, 决定了在个人数据集成与管理中需要采用不同的方法与策略。
[Top]         
研究动机

大家都知道计算机领域中的摩尔定律,它的一个广义的解读是这样的:计算机的性能随着时间指数增长;同时,计算的成本则会随时间呈指数下降。这一定律随着计算机领域的飞速发展得到了越来越确凿的证明:CPU的速度、内外存的容量在迅速增长,相对的是它们的价格却一路下跌。这样一个发展趋势的必然结果,就是计算和通讯会越来越普及,以至于数据量以难以想象的速度急剧膨胀。另一方面,在数据管理中却有一样东西是基本维持不变的--那就是人的注意力和人能够用在数据管理上的时间。也就是说目前计算技术的发展是使人更加应接不暇加速到来的信息,而没有丝毫减轻人们的负担。个人数据空间管理旨在通过研究个人数据特点,探索与其特点相适应的数据模型以及存储、查询、索引、安全机制,实现能够提高个人数据管理效率的应用系统。

[Top]         
现有研究工作
  • 个人数据空间
  • 个人数据空间框架与模型:
    数据模型是数据管理的基础,基于个人数据空间的特点,提出了用户为中心的个人核心数据空间框架:CoreSpace. 该框架突出了用户特性在个人数据空间管理中的作用,对个人数据空间集成、查询、索引、演化等技术研究都会带来影响。

    个人数据空间查询:
    建立个人数据空间的一个重要目的就是为了提高个人数据对象的访问效率。因此对个人数据空间查询技术的研究是一个重要的问题,也是我们正在进行的一项工作。

    个人数据空间演化:
    Pay-As-You-Go的演化机制是数据空间区别于其他数据管理工具的主要特性之一。该特性描述了系统能够随着用户使用的积累而不断提高服务质量的一种能力。演化能力的强弱很大程度上决定了该数据空间系统的服务能力。

    作为国内最早开始关注数据空间研究的研究组之一,我们一直在关注数据演化的问题。我们的关注点集中在如何以自动的方法为基础,通过结合用户行为和反馈来不断提高系统服务能力。系统服务能力的不断提高会给用户的查询等请求带来不断提升的服务质量,达到系统演化的目的。这是一个逐步的、渐进的过程,而且在这个过程中可能需要借助各种各样的用户行为,是一个符合Pay-As-You-Go原则的过程。

  • 近似查询与匹配技术
  • 文本数据无处不在,而管理这些存储在数据库或信息系统中的数据在以数据为主要驱动力的今天显得极为重要。近似查询与匹配是其中一项关键技术。它与许多数据分析任务息息相关,能够从字符串的层面解决数据源之间的数据质量问题,弥补精确匹配在实际应用中的不足。因此高效的近似查询与匹配技术是一个重要的研究课题。

    近似查询与匹配在很多重要的应用中都会涉及到,例如从网页上抽取实体(人名、地址、产品名称等),从医学文献中识别一些生物学的概念,进行数据清洗任务以及用户查询等。在这些场景下,精确匹配往往会丢失掉大量我们需要的结果,因为无论是数据库记录还是网页上的信息或者是用户提交的查询,都有可能包含各种错误。此外,由于数据规模较大,这些应用在响应时间上提出了更高的要求,尤其对于一些基于Web的应用。目前已经有了一部分这方面的研究,但远不能满足实际应用的需要。由此,近似查询与匹配技术无论是在研究还是应用上都是具有重要意义的。

    [Top]         
    系统介绍
  • OrientSpace
  • 基于我们对数据空间的理解和成果,我们开发了一个个人数据空间原型系统 OrientSpace。该系统以Java为开发平台,目前实现了个人数据管理的基本功能,其中包括以下几个具有特色的方面:

    可自由编辑的数据模式:

    在OrientSpace中我们允许用户根据自己的意愿自由建立、修改和删除模式,并可以在各个模式下自由地添加实例。这里体现的是数据空间所提倡的“从数据到模式”的思想:用户一开始可能无法得知某种数据的具体模式,因而只能建立一个初步的模式,但是已经可以向这个不完整的模式里面添加数据;随着用户对模式的不断了解,系统中的模式可能会被不断修改,逐渐趋近最终完整的模式。在这个过程中模式下的数据可能也在不断发生变化。
    由于我们在底层采用RDF作为存储支持,OrientSpace允许在模式变化的整个过程中随时轻量式地修改数据。我们认为这种方式更适合目前形势下的数据发展趋势,这种趋势也正是数据空间提出时所针对要解决的问题。

    基于资源内容的关联建立和利用:

    数据空间的重要特性之一就是利用关联信息来帮助用户找到更多相关的信息。在OrientSpace中我们通过分析系统中用户资源的内容信息(包括文本内容和元信息)来建立多种关联,并利用这些关联信息支持我们基于图的资源查询和浏览.

    选择性的内容索引:

    在对文本内容进行索引时,没有采用传统的全文索引的方式,而是用选择性索引的方式进行索引。不使用全文索引的主要理由如下:

    • 全文索引占用空间过大。

    • 使用过各种桌面搜索引擎工具的用户都会发现这个问题:全文索引逐渐会占据很大,多的时候会占到几个GB的级别,这是一种明显的浪费。


    • 桌面用户与Web用户存在差异。

    • 在网络搜索中,用户常常不知道自己所要寻找的东西具体是哪个,知道的可能只是什么样的结果会使自己满意。那么任何符合用户输入条件的都可能是最终使用户满意的结果。这就要求搜索引擎必须将文档中几乎所有的内容全部进行索引,否则就可能漏掉最终使用户满意的资源。而在桌面应用中,用户大多数情况下是知道自己要找的资源是什么的,未知的常常只是这些资源的存放位置。那么用户用来查询这些资源的关键字一般来说也是这些资源中比较“重要”的词汇,那么我们有理由认为,只要将这些比较重要的关键词汇索引起来就可以回答用户绝大多数的查询,而同时避免了将一些用户不关心的但是包含了该关键字的资源纳入到查询结果中(也就是在各种网络搜索引擎中被排到前几页之外的那些部分)。

    • 全文索引速度慢。

    • 在各种应用程序中,数据的处理时间大部分常常都花在了IO上,索引也是这样一个过程。而我们采用的选择性索引通过一定的选择策略缩小了索引文件的大小,从而减少了IO时间,同时,选择索引内容的过程的时间花销是很小的。

    Pay-As-You-Go式系统演化:

    作为数据空间系统的重要特性之一,系统演化是衡量一个数据空间系统能力的重要标准。我们的系统采用了一种基于query-bridge的方法在个人数据空间的资源之间建立关联信息,并借助用户反馈对关联信息进行不断更新和筛选,以此不断推动系统不断演化。

    [Top]         
    获资助课题
    • 2007.7-2009.12 海量数据空间模型、查询与索引技术研究
      国家高技术研究发展计划(863), 编号:2007AA01Z155
    • 2003 语义网格的基础理论、模型与方法研究
      国家重点基础研究发展计划(973), 编号:2003CB317000
    [Top]         
    专利
    • Efficient Merging and Filtering Algorithms for Approximate String
      美国专利(61/043,325)
    [Top]        
    论文著作
    • Alex Behm, SHenyue Ji, Chen Li, Jiaheng Lu: Space-Constrained Gram-Based Indexing for Efficient Approximate String Search, IEEE International Conference on Data Engineering (ICDE) 2009 (full paper)
    • 李玉坤,孟小峰,张相於: 数据空间技术研究,软件学报, 2008,19(8):2018-2031. 10.3724/SP.J.1001.2008.02018.
    • 李玉坤,孟小峰: Research on Personal Dataspace Management, The Second SIGMOD PhD Workshop on Innovative Dataspace Research (IDAR2008), Vancouver, BC, Canada, June 10-12, 2008.
    • 张相於,陈继东,李玉坤,孟小峰:TEXEM : 一种基于实体的邮件任务提取策略。计算机研究与发展,卷45(增刊)。(第二十五届中国数据库学术会议2008 桂林)
    • Chen Li, Jiaheng Lu ,Yiming Lu: Efficient Merging and Filtering Algorithms for Approximate String Searches, IEEE International Conference on Data Engineering (ICDE) 2008 (full paper)
    [Top]         
    Reference
    • Dong X, Halevey A: Data Integration with Uncertainty. VLDB 2007 687-698.
    • Dong X, Halevey A: Indexing Dataspace. SIGMOD 2007: 43-54.
    • Blunschi L, Dittrich J-P, Girard OR, Karakashian S.K and Salles MAV. A Dataspace Odyssey: The iMeMex Personal Dataspace Management System. CIDR 2007: 114-119
    • Salles MAV, Dittrich J-P, Karakashian S.K, Girard OR, Blunschi L. iTrails: Pay-as-you-go Information Integration in Dataspaces, VLDB 2007: 663-674
    • Halevy A , Franklin M. Maier D: Principles of dataspace systems, PODS 2006: 1-9.
    • Dittrich J-P and Salles MAV. iDM: A Unified and Versatile Data Model for Personal Dataspace Management. VLDB 2006: 367-378.
    • Dittrich J-P iMeMex: A Platform for Personal Dataspace Management. In SIGIR PIM Workshop, 2006.
    • A. Arasu, V. Ganti, and R. Kaushik. Ecient exact set-similarity joins. In VLDB, pages 918-929, 2006.
    • K. Chakrabarti, V. Ganti, J. Han, and D. Xin: Ranking objects based on relationships. In SIGMOD Conference, pages 371-382, 2006.
    • 2008-10-29
    • A. Chandel, P. C. Nagesh, and S. Sarawagi: Effcient batch top-k search for dictionary-based entity recognition. In ICDE, page 28, 2006.
    • S. Chaudhuri, V. Ganti, and R. Kaushik: A primitive operator for similarity joins in data cleaning. In ICDE, page 5, 2006.
    • X. Zhou, X. Zhang, and X. Hu. Maxmatcher: Biological concept extraction using approximate dictionary lookup. In PRICAI, pages 1145-1149, 2006.
    • Jones W and Bruce H: A Report on the NSF-Sponsored Workshop on Personal Information Management, Seattle, WA, 2005.
    • Franklin M, Halevy A, and Maier D. From databases to dataspaces: A New Abstraction for Information Management. SIGMOD Record, 34(4):27-33, 2005.
    • Dong X and Halevy A: A Platform for Personal Information Management and Integration. CIDR 2005:119-130.
    • Zhuge H: Resource space model, its design method and applications. The Journal of Systems and Software 72 (2004) 71-81.
    • M. Narayanan and R. M. Karp: Gapped local similarity search with provable guarantees. In WABI, pages 74-86, 2004.
    • S. Sarawagi and A. Kirpal: Effcient set joins on similarity predicates. In SIGMOD Conference, pages 743-754, 2004.
    • R. Fagin, A. Lotem, and M. Naor: Optimal aggregation algorithms for middleware. In PODS, 2001.
    • L. Gravano, P. G. Ipeirotis, H. V. Jagadish, N. Koudas, S. Muthukrishnan, and D. Srivastava: Approximate string joins in a database (almost) for free. In VLDB, pages 491-500, 2001.
    • A. Singhal. Modern information retrieval: A brief overview. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 24(4):35-43, 2001.
    • A. Amir, D. Keselman, G. M. Landau, M. Lewenstein, N. Lewenstein, and M. Rodeh: Text indexing and dictionary matching with one error. J. Algorithms, 37(2):309-325, 2000.
    • E. Cohen, M. Datar, S. Fujiwara, A. Gionis, P. Indyk, R. Motwani, J. D. Ullman, and C. Yang: Finding interesting associations without support pruning. In ICDE, pages 489-499, 2000.
    • T. H. Haveliwala, A. Gionis, and P. Indyk: Scalable techniques for clustering the web. In WebDB (Informal Proceedings), pages 129-134, 2000.
    • A. Gionis, P. Indyk, and R: Motwani. Similarity search in high dimensions via hashing. In VLDB, pages 518-529, 1999.
    • I. H. Witten, A. Moffat, and T. C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann, 1999.
    • Ricardo Baeza-Yates and Gonzalo Navarro: Fast Approximate String Matching in a Dictionary. Proc. SPIRE'98.
    • Freeman E and Gelernter D. Lifestreams: A Storage Model for Personal Data. In SIGMOD Record . 25(1):80-86, 1996.
    • G. S. Brodal and L: Gasieniec. Approximate dictionary queries. In CPM, pages 65-74, 1996.
    • A. C.-C. Yao and F. F. Yao: Dictionary loop-up with small errors. In CPM, pages 387-394, 1995.
    • U. Manber and S. Wu: An algorithm for approximate membership checking with application to password security. Inf. Process. Lett., 50(4):191-197, 1994.
    • R. Baeza-Yates, W. Cunto, U. Manber, and S. Wu. Proximity matching using fixed queries trees: In M. Crochemore and D. Gusfield, editors, 5th Combinatorial Pattern Matching, LNCS 807, pages 198-212, Asilomar, CA, June 1994.
    • A. V. Aho and M. J. Corasick: Effcient string matching: An aid to bibliographic search. Commun. ACM, 18(6):333-340, 1975.
    • W. Burkhard and R. Keller: Some approaches to best-match file searching, CACM, 1973.
    • B. H. Bloom: Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13(7):422-426, 1970.
    [Top]         
    Maintained by Zhongyuan Wang( ) Copyright © 2007-2008 WAMDM, All rights reserved