不确定数据的世系管理和相似性查询
|
摘要
不确定性数据在很多应用中广泛出现,例如经济、军事、物流、金融、电信等,其表现形式多种多样,包括关系型数据、半结构化数据、图数据、流数据、移动对象数据以及无结构化的Web数据等。目前,根据应用的特点与数据形式的多样性,已经出现了多种不确定数据模型,这些模型的核心思想都源自可能世界模型。该模型从一个不确定的数据源演化出诸多确定性的可能世界实例,所有实例的概率之和等于1。尽管可以针对各个实例单独进行查询处理,合并中间结果并获取最终结果,但是可能世界实例的数量远大于不确定数据库的规模,从而导致可能世界模型在实践应用中并不可行。因此必须采用排序、剪枝等启发式技术进行优化处理以提高查询处理效率。
针对不确定数据管理的挑战,本文主要考察不确定数据查询处理的优化。主要工作分为两部分：不确定数据世系管理和相似性查询。具体的,针对数据的不确定性,研究如何通过不确定数据的世系追踪数据不确定性的来源和大小,以及对不确定性集合数据进行相似度评价,最后提出了不确定数据流上ER-topk查询的精确算法。本文的主要贡献如下：
●首先研究了如何利用数据世系追踪数据不确定性的来源和大小。基于PHP-tree数据结构,近似描述不确定数据的How世系,避免了追踪数据演化的中间结果,同时也避免了运用可能世界模型对不确定性数据进行建模；基于PHP-tree,可以追踪日标数据的不确定性来源,以及对目标数据的不确定性大小进行评价。
·针对不确定集合,定义了不确定性集合的期望相似度算子,提出了不确定集合期望相似度的精确和近似算法。具体的,运用动态规划方法在多项式时间内给出不确定集合期望相似度的精确算法,而不必扩展可能世界实例；考虑到精确算法需要耗费大量的时间和空间,为克服可扩展性差的缺点,我们运用Monte-Carlo方法在线性时间内近似计算不确定集合的期望相似度。
●考虑到不确定集合相似度的多样性,又评价了不确定性集合的概率阈值相似度。给出了不确定集合的概率阈值相似度算子的定义,以及精确和近似算法。运用动态规划方法在多项式时间内给出不确定集合概率阈值相似度的精确计算过程；同时考虑到概率阈值相似度的计算结果是一个概率值,当用户给定相似度的阈值,利用尾概率不等式提出了一个线性时间内的剪枝规则,大大加快了精确解的计算过程；考虑到没有被剪枝的不确定集合的精确算法需要耗费大量的时间和空间,我们运用Monte-Carlo方法近似计算不确定集合的概率阈值相似度。
●基于界标模型提出了不确定数据流响应ER-topk查询的精确算法,该方案将所有不断到来的元组分成两组,一组包含ER-topk查询的候选结果,剩下的元组包含在另外一组中,我们分别用数据结构domGraph和probTree来维护这两类元组；基于期望的线性性,我们避免了扩展所有可能世界实例,在次线性时间内给出查询的结果。
本文研究了不确定数据的查询处理,主要工作包括不确定数据世系管理和不确定数据的相似性查询,通过大量的实验验证了提出算法的效率和可扩展性等。
Appearing widely in various fields, inclusive of economy, military, logistic, fi-nance and telecommunication, et al., uncertain data has many different styles, such as relational data, semi-structure data, streaming data, and moving objects. accord-ing to scenarios and data characteristics. tens of data models have been developed. stemming from the core possible world model that contains a huge number of the possible world instances with the sum of probabilities equal to 1. However, the num-ber of the possible world instances is far greater than the volume of the uncertain database, making it infeasible to combine intermediate results generated from all of possible world instances for the final query results. Thus, some heuristic techniques, such as ordering, pruning, must be used to reduce the computation cost for the high efficiency.
In this thesis, a comprehensive survey on the techniques for data management in uncertainty, and data provenance. However, traditional techniques cannot be adopted in uncertain data management because of some challenges in uncertain data management. Focusing on the challenges of uncertain data management and weak point of traditional techniques for it, we track the origin and value of uncertainty of data, evaluate the similarity of uncertain set for un-structured data, and study expected ranking top-k (shorted in ER-topk) query over uncertain data stream. The contributions of this thesis are summarized as follows:
●Focusing on the uncertainty of data, we track the origin and value of uncer-tainty of data by how provenance at first. We propose an approach, named PHP-tree, to approximately model how-provenance upon probabilistic databases. we also show how to evaluate probability based on a PHP-tree. Compared with Trio style lineage, our approach is independent of intermediate results and can calculate the probability both cases of restricted and complete propagation of data provenance.
●Based on uncertain set, we propose the expected set similarity operator based on the possible worlds model, over several mainstream similarity metrics, in-cluding Jaccard, Dice and Cosine. Our first work is to define the expected set similarity over probabilistic sets. Then we design exact and approximate algo-rithms for calculating them. In detail, we employ the dynamic programming to exactly calculate the expected set similarity in polynomial time and space consumption. Due to large cost both in time and space of exact algorithms, we also provide approximate solutions that are both time-and space-efficient with high approximate precision by Monte-Carlo.
●Since diversity of set similarity of probabilistic sets, based on the possible worlds model, we propose the probability threshold set similarity operator, over several mainstream similarity metrics, including Jaccard, Dice and Cosine, to evaluate similarity of probabilistic sets. We also design exact algorithms for calculating them. In detail, we employ the dynamic programming to calculate the probability threshold set similarity in polynomial time and space consump-tion exactly. Furthermore, we propose probabilistic threshold similarity query algorithm. We provide a pruning rule in linear time and space for Jaccard, Dice, and Cosine. Due to large cost both in time and space of exact algo-rithms, we also provide approximate solutions that are both time-and space-efficient with high approximate precision by Monte-Carlo.
●Based on the landmark model, we give an exact solution for ER-topk query over uncertain data stream. In our solution, all arriving tuples in the data stream are divided into two groups. One group contains candidate top-k tu-ples, i.e, the tuples having chance to belong to the query result, and the other contains the rest. We construct and maintain two structures, namely domGraph and probTree, to describe the two groups for efficiency. Since the linearity of expectation, our solution can provide answer of query in sub-linear time.
In this thesis, our work focus on the query processing over uncertain data. Mainly work consist of data provenance management and similarity query over un-certain data. Finally, we verify the efficiency and scalability of our proposed algo-rithms by lot of experiments.
针对不确定数据管理的挑战,本文主要考察不确定数据查询处理的优化。主要工作分为两部分：不确定数据世系管理和相似性查询。具体的,针对数据的不确定性,研究如何通过不确定数据的世系追踪数据不确定性的来源和大小,以及对不确定性集合数据进行相似度评价,最后提出了不确定数据流上ER-topk查询的精确算法。本文的主要贡献如下：
●首先研究了如何利用数据世系追踪数据不确定性的来源和大小。基于PHP-tree数据结构,近似描述不确定数据的How世系,避免了追踪数据演化的中间结果,同时也避免了运用可能世界模型对不确定性数据进行建模；基于PHP-tree,可以追踪日标数据的不确定性来源,以及对目标数据的不确定性大小进行评价。
·针对不确定集合,定义了不确定性集合的期望相似度算子,提出了不确定集合期望相似度的精确和近似算法。具体的,运用动态规划方法在多项式时间内给出不确定集合期望相似度的精确算法,而不必扩展可能世界实例；考虑到精确算法需要耗费大量的时间和空间,为克服可扩展性差的缺点,我们运用Monte-Carlo方法在线性时间内近似计算不确定集合的期望相似度。
●考虑到不确定集合相似度的多样性,又评价了不确定性集合的概率阈值相似度。给出了不确定集合的概率阈值相似度算子的定义,以及精确和近似算法。运用动态规划方法在多项式时间内给出不确定集合概率阈值相似度的精确计算过程；同时考虑到概率阈值相似度的计算结果是一个概率值,当用户给定相似度的阈值,利用尾概率不等式提出了一个线性时间内的剪枝规则,大大加快了精确解的计算过程；考虑到没有被剪枝的不确定集合的精确算法需要耗费大量的时间和空间,我们运用Monte-Carlo方法近似计算不确定集合的概率阈值相似度。
●基于界标模型提出了不确定数据流响应ER-topk查询的精确算法,该方案将所有不断到来的元组分成两组,一组包含ER-topk查询的候选结果,剩下的元组包含在另外一组中,我们分别用数据结构domGraph和probTree来维护这两类元组；基于期望的线性性,我们避免了扩展所有可能世界实例,在次线性时间内给出查询的结果。
本文研究了不确定数据的查询处理,主要工作包括不确定数据世系管理和不确定数据的相似性查询,通过大量的实验验证了提出算法的效率和可扩展性等。
Appearing widely in various fields, inclusive of economy, military, logistic, fi-nance and telecommunication, et al., uncertain data has many different styles, such as relational data, semi-structure data, streaming data, and moving objects. accord-ing to scenarios and data characteristics. tens of data models have been developed. stemming from the core possible world model that contains a huge number of the possible world instances with the sum of probabilities equal to 1. However, the num-ber of the possible world instances is far greater than the volume of the uncertain database, making it infeasible to combine intermediate results generated from all of possible world instances for the final query results. Thus, some heuristic techniques, such as ordering, pruning, must be used to reduce the computation cost for the high efficiency.
In this thesis, a comprehensive survey on the techniques for data management in uncertainty, and data provenance. However, traditional techniques cannot be adopted in uncertain data management because of some challenges in uncertain data management. Focusing on the challenges of uncertain data management and weak point of traditional techniques for it, we track the origin and value of uncertainty of data, evaluate the similarity of uncertain set for un-structured data, and study expected ranking top-k (shorted in ER-topk) query over uncertain data stream. The contributions of this thesis are summarized as follows:
●Focusing on the uncertainty of data, we track the origin and value of uncer-tainty of data by how provenance at first. We propose an approach, named PHP-tree, to approximately model how-provenance upon probabilistic databases. we also show how to evaluate probability based on a PHP-tree. Compared with Trio style lineage, our approach is independent of intermediate results and can calculate the probability both cases of restricted and complete propagation of data provenance.
●Based on uncertain set, we propose the expected set similarity operator based on the possible worlds model, over several mainstream similarity metrics, in-cluding Jaccard, Dice and Cosine. Our first work is to define the expected set similarity over probabilistic sets. Then we design exact and approximate algo-rithms for calculating them. In detail, we employ the dynamic programming to exactly calculate the expected set similarity in polynomial time and space consumption. Due to large cost both in time and space of exact algorithms, we also provide approximate solutions that are both time-and space-efficient with high approximate precision by Monte-Carlo.
●Since diversity of set similarity of probabilistic sets, based on the possible worlds model, we propose the probability threshold set similarity operator, over several mainstream similarity metrics, including Jaccard, Dice and Cosine, to evaluate similarity of probabilistic sets. We also design exact algorithms for calculating them. In detail, we employ the dynamic programming to calculate the probability threshold set similarity in polynomial time and space consump-tion exactly. Furthermore, we propose probabilistic threshold similarity query algorithm. We provide a pruning rule in linear time and space for Jaccard, Dice, and Cosine. Due to large cost both in time and space of exact algo-rithms, we also provide approximate solutions that are both time-and space-efficient with high approximate precision by Monte-Carlo.
●Based on the landmark model, we give an exact solution for ER-topk query over uncertain data stream. In our solution, all arriving tuples in the data stream are divided into two groups. One group contains candidate top-k tu-ples, i.e, the tuples having chance to belong to the query result, and the other contains the rest. We construct and maintain two structures, namely domGraph and probTree, to describe the two groups for efficiency. Since the linearity of expectation, our solution can provide answer of query in sub-linear time.
In this thesis, our work focus on the query processing over uncertain data. Mainly work consist of data provenance management and similarity query over un-certain data. Finally, we verify the efficiency and scalability of our proposed algo-rithms by lot of experiments.
引文
[1]周傲英,金澈清,王国仁,李建中.不确定性数据管理技术研究综述.计算机学报,2009,31(1)：1-16.
[2]Evan Welbourne, Magdalena Balazinska, Gaetano Borriello, and Waylon Brunette. Challenges for pervasive rfid-based infrastructures. In In Proc. of PERTEC, pages 388-394,2007.
[3]http://www.seo371.cn/wlqy/wlqyn_684.html.
[4]A. Deshpande, C. Guestrin. S. Madden, J. M. Hellerstein. and W. Hong. Model-driven data acquisition in sensor networks. In In Proc. of VLDB, page 588-599,2004.
[5]谷峪,于戈,张天成RFID复杂事件处理技术.计算机科学与探索.2007.1(3)：255-267.
[6]徐琳.在前沿科学问题上开展国际合作提升我国射频识别数据管理科研水平.计算机科学与探索,2007,1(3)：347-350.
[7]Babcock B, Babu S, Datar M, Motwani R, and Widom J. Models and issues in data stream systems. In Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 1-16, 2006.
[8]金澈清,钱卫宁,周傲英.流数据分析与管理综述.软件学报.2004,15(8)：1172-1181.
[9]E. Gradel, Y. Gurevich, and C. Hirsch. The complexity of query reliability. In Proc. of SIGMOD, pages 227-234,1998.
[10]N. Dalvi and D. Suciu. The dichotomy of conjunctive queries on probabilistic structures. In Proc. of SIGMOD, pages 293-302,2007.
[11]高明,金澈清,王晓玲,田秀霞,周傲英.数据世系管理技术研究综述.计算机学报,2010,33(3)：373-389.
[12]S. Abiteboul, P. Kanellakis, and G. Grahne. On the representation and query-ing of sets of possible worlds. Proc. of SIGMOD,16(3):34-48,1987.
[13]Todd J. Green and Val Tannen. Models for incomplete and probabilistic in-formation. IEEE Date Engineering Bulletin,29(1):17-24,2006.
[14]R. Cavallo and M. Pittarelli. The theory of probabilistic databases. In Proc. of VLDB, pages 71-81,1987.
[15]D. Barbara. H. Garcia-Molina, and D. Porter. The management of probabilistic data. IEEE Transactions on Knowledge and Data Engineering,4(5):487-502, 1992.
[16]N. Fuhr and T. Rolleke. A probabilistic relational algebra for the integration of information retrieval and database systems. ACM Transactions on Infor-mation Systems,15(1):32-66,1997.
[17]E. Zim'anyi. Query evaluation in probabilistic relational databases. In TCS, pages 1-2,1997.
[18]L. V. S Lakshmanan, N. Leone, R. Ross. and V. S. Subrahmanian. Probview:A flexible database system. ACM Transactions on Database Systems.22(3):419-469,1997.
[19]A. Nierman and H. V. Jagadish. Protdb:Probabilistic data in xml. In Proc. of VLDB, pages 421-432,2002.
[20]S. Abiteboul and P. Senellart. Querying and updating probabilistic informa-tion in xml. In Proceedings of the 9th international conference on Extending database technology:Advances in database technology, pages 1059-1068,2006.
[21]P. Senellart and S. Abiteboul. On the complexity of managing probabilistic xml data. In Proc. of PODS, pages 217-228,2007.
[22]Sara Cohen, Benny Kimelfeld, and Yehoshua Sagiv. Incorporating constraints in probabilistic xml. In Proc. of PODS, pages 61-73,2008.
[23]E. Hung, L. Getoor, and V. S. Subrahmanian. Pxml:A probabilistic semistruc-tured data model and algebra. In Proc. of ICDE, pages 126-137,2003.
[24]E. Hung, L. Getoor, and V.S. Subrahmanian. Probabilistic interval xml. ACM Transactions on Computational Logic,8(4):24,2007.
[25]Benny Kimelfeld, Yuri Kosharovsky, and Yehoshua Sagiv. Query efficiency in probabilistic xml models. In Proc. of PODS, pages 436-447,2008.
[26]P. Hintsanen. The most reliable subgraph problem. In Proceedings of the 11th European conference on principles and practice of knowledge discovery in databases, pages 471-478,2007.
[27]P. Hintsanen and H. Toivonen. Finding reliable subgraphs from large proba-bilistic graphs. Data Min Knowl Disc,17(3):3-23,2008.
[28]Eytan Adar and Christopher Re. Managing uncertainty in social networks. IEEE Data Eng. Bull,30(2):15-22,2006.
[29]T. S. Jayram, S. Kale, and E. Vee. Efficient aggregation algorithms for prob-abilistic data. In Proc. of SIAM, pages 346-355,2007.
[30]G. Cormode and M. Garofalakis. Sketching probabilistic data streams. In Proc. of SIGMOD, pages 346-357,2007.
[31]Cheqing Jin, Ke Yi, Lei Chen 0002, Jeffrey Xu Yu, and Xuemin Lin. Sliding-window top-k queries on uncertain streams. PVLDB, 1(1):301-312,2008.
[32]Christopher Re, Julie Letchner, Magdalena Balazinska, and Dan Suciu. Event queries on correlated probabilistic streams. In Proc. of SIGMOD, pages 469-480,2008.
[33]P. Andritsos, A. Fuxman, and R. J. Miller. Clean answers over dirty databases: A probabilistic approach. In Proc. of ICDE, page 30,2006.
[34]P. Sen and A. Deshpande. Representing and querying correlated tuples in probabilistic databases. In Proc. of ICDE, pages 596-605,2007.
[35]B. Kimelfeld and Y. Sagiv. Matching twigs in probabilistic xml. In Proc. of VLDB, pages 69-80,2007.
[36]L. G. Viliant. The complexity of enumeration and reliability prblems. SIAM JL of Computing,8(3):124-156,1979.
[37]J. S. Provan and M. O. Ball. The complexity of counting cuts and of computing the probability that a graph is connented. SIAM JL of Computing,12(4):241-263,1983.
[38]邹兆年、李建中、高宏、张硕,从不确定图中挖掘频繁子图模式,软件学报,2009,20(11)：2965-2976.
[39]Hongrae Lee, Raymond T. Ng, and Kyuseok Shim. Power-law based estimation of set similarity join size. Proc. of PVLDB,2(1):658-669,2009.
[40]Sunita Sarawagi and Alok Kirpal. Efficient set joins on similarity predicates. In proc. of ACM SIGMOD, pages 743-754,2004.
[41]Ashwin R. Bharambe, Mukesh Agrawal, and Srinivasan Seshan. Mercury:sup-porting scalable multi-attribute range queries. In proc. of ACM SIGCOMM, pages 353-366,2004.
[42]Ihab F. Ilyas, Walid G. Aref, and Ahmed K. Elmagarmid. Supporting top-k join queries in relational databases. VLDB J.,13(3):207-221,2004.
[43]Stephan Borzsonyi. Donald Kossmann, and Konrad Stocker. The skyline op-erator. In proc. of ICDE, pages 421-430,2001.
[44]Thomas Brinkhoff, Hans-Peter Kriegel, and Bernhard Seeger. Efficient pro-cessing of spatial joins using r-trees. In proc. of ACM SIGMOD, pages 237-246, 1993.
[45]Chuan Xiao, Wei Wang, and Xuemin Lin. Ed-join:an efficient algorithm for similarity joins with edit distance constraints. Proc. of PVLDB, 1(1):933-944, 2008.
[46]Arvind Arasu, Venkatesh Ganti, and Raghav Kaushik. Efficient exact set-similarity joins. In proc. of VLDB, pages 918-929,2006.
[47]Vebjorn Ljosa and Ambuj K. Singh. Top-k spatial joins of probabilistic objects In proc. of ICDE, pages 566-575.2008.
[48]Hans-Peter Kriegel, Peter Kunath. Martin Pfeifle, and Matthias Renz. Proba-bilistic similarity join on uncertain data. In Proc. of DASFAA, pages 295-309. 2006.
[49]Jeffrey Jestes, Feifei Li, Zhepeng Yan, and Ke Yi. Probabilistic string similarity joins. In Proc. of ACM SIGMOD, pages 327-338,2010.
[50]Xiang Lian and Lei Chen. Set similarity join on probabilistic data. Proc. of PVLDB,3(1):650-659,2010.
[51]M. A. Soliman, I. F. Ilyas, and K. C. Chang. Top-k query processing in uncer-tain databases. In Proc. of ICDE, pages 896-905,2007.
[52]Graham Cormode, Feifei Li, and Ke Yi. Semantics of ranking queries for probabilistic data and expected ranks. In Proc. of ICDE,2009.
[53]M. Hua, Jian Pei, Wenjie Zhang, and Xuemin Lin. Efficiently answering prob-abilistic threshold top-k queries on uncertain data. In Proc. of ICDE, pages 1403-1405,2008.
[54]J. Chen and K. Yi. Dynamic structures for top-k queries on uncertain data. In Proceedings of the 18th International Symposium on Algorithms and Com-putation, pages 427-438,2007.
[55]Ming Hua, Jian Pei, Wenjie Zhang, and Xuemin Lin. Ranking queries on uncertain data:A probabilistic threshold approach. In Proc. of SIGMOD, pages 673-686,2008.
[56]Cheqing Jin, Ke Yi, Lei Chen, Jeffrey Xu Yu. and Xuemin Lin. Sliding-window top-k queries on uncertain streams. In Proc. of VLDB. pages 293-302,2008.
[57]Christopher Re. Nilesh Dalvi, and Dan Suciu. Efficient top-k query evaluation on probabilistic data. In Proc. of ICDE. pages 886-895.2007.
[58]J. Pei, B. Jiang. X. Lin, and Y. Yuan. Probabilistic skylines on uncertain data. In Proc. of VLDB, pages 15-26.2007.
[59]Ke Yi, Xiang Lian, Feifei Li, and Lei Chen. A concise representation of range queries. In proc. of ICDE, pages 1179-1182,2009.
[60]Jia Xu, Zhenjie Zhang, Anthony K. H. Tung, and Ge Yu. Efficient and effec-tive similarity search over probabilistic data based on earth mover's distance. PVLDB,3(1):758-769.2010.
[61]Jian Li, Barna Saha. and Amol Deshpande. A unified approach to ranking in probabilistic databases. PVLDB,2(1):502-513.2009.
[62]Jian Li and Amol Deshpande. Ranking continuous probabilistic datasets. PVLDB,3(1):638-649.2010.
[63]R. Cheng. Xia Y, S. Prabhakar, R. Shah, and J. S. Vitter. Efficient indexing methods for probabilistic threshold queries over uncertain data. In Proc. of VLDB, pages 876-887,2004.
[64]Y. Tao, X. Xiao, and R. Cheng. Range search on multidimensional uncertain data. ACM Transactions on Database Systems,32(3):15,2007.
[65]Y. Ishikawa, Y. Iijima, and Jeffrey Xu Yu. Spatial range querying for gaussian-based imprecise query objects. In Proc. of ICDE, pages 676-687,2009.
[66]X. Lian and L. Chen. Probabilistic ranked queries in uncertain databases. In Proc. of EDBT, pages 511-522,2008.
[67]Xiang Lian and Lei Chen. Probabilistic group nearest neighbor queries in uncertain databases. TKDE,20(6):809-824,2008.
[68]Vebjorn Ljosa and Ambuj K. Singh. Apla:Indexing arbitrary probability distributions. In Proc. of ICDE, pages 946-955,2007.
[69]G. Beskales, M. A. Soliman, and I. F. Ilyas. Efficient search for the top-k probable nearest neighbors in uncertain databases. Proc. of PVLDB,1(1):326-339,2008.
[70]Muhammad Aamir Cheema, Xuemin Lin, Wei Wang, Wenjie Zhang, and Jian Pei. Probabilistic reverse nearest neighbor queries on uncertain data. IEEE Trans. Knowl. Data Eng.,22(4):550-564,2010.
[71]Ying Zhang, Xuemin Lin. Gaoping Zhu, Wenjie Zhang, and Qianlu Lin. Ef-ficient rank based knn query processing over uncertain data. In ICDE, pages 28-39,2010.
[72]X. Lian and L. Chen. Monochromatic and bichromatic reverse skyline search over uncertain databases. In Proc. of SIGMOD, pages 213-226,2008.
[73]K. Deng, X. Zhou, and H. T. Shen. Multi-source skyline query processing in road networks. In Proc. of ICDE, pages 796-805,2007.
[74]Dimitris Sacharidis, Anastasios Arvanitis, and Timos K. Sellis. Probabilistic contextual skylines. In ICDE, pages 273-284,2010.
[75]Y. Richard Wang and Stuart E. Madnick. A polygen model for heterogeneous database systems:the source tagging perspective. In Proc. of VLDB, pages 519-538.1990.
[76]Y. Cui, J. Widom, and J. L. Wiener. Tracing the lineage of view data in a warehousing environment. The ACM Transactions on Database Systems, 25(2):179-227,2000.
[77]P. Buneman, S. Khanna, and W. C. Tan. Why and where:a characterization of data provenance. In Proc. of ICDE, pages 316-330,2001.
[78]Boris Glavic and Klaus Dittrich. Data provenance:A categorization of existing approaches. In Proceeding of the 6th MMC Workshop of BTW 2007, pages 227-241,2007.
[79]Todd J. Green, Gregory Karvounarakis, Nicholas E. Taylor, Olivier Biton, Zachary G. Ives, and Val Tannen. Orchestra:facilitating collaborative data sharing. In Proc. of SIGMOD, pages 1131-1133,2007.
[80]Todd J. Green, Grigoris Karvounarakis, Zachary G. Ives, and Val Tannen. Update exchange with mappings and provenance. In Proc. of VLDB, pages 675-686,2007.
[81]Todd J. Green, Gregory Karvounarakis, and Val Tannen. Provenance semir-ings. In PODS, pages 31-40,2007.
[82]N. Fuhr and T. R'olleke. Incomplete information in relational databases. JACM,31(4):761-791,1984.
[83]T. J.Green. G. Karvounarakis, and V. Tannen. Provenance semirings. In Proc. of SIGMOD. pages 31-40,2007.
[84]Rajendra Bose and James Frew. Lineage retrieval for scientific data processing: a survey. ACM Computer Surveys,37(1):1-28.2005.
[85]Laura Chiticariu. Wang-Chiew Tan, and Gaurav Vijayvargiya. Dbnotes:a post-it system for relational databases based on provenance. In Proc. of SIG-MOD. pages 942-944.2005.
[86]Marion Blount, John Davis, Archan Misra. Daby Sow, and Min Wang. A time-and-value centric provenance model and architecture for medical event streams. In Proceeding of the 1st International Workshop on Systems and Networking Support for Healthcare and Assisted Living Environments, pages 95-100,2007.
[87]Bhargav Kanagal and Amol Deshpande. Lineage processing over correlated probabilistic databases. In SIGMOD Conference, pages 675-686,2010.
[88]Omar Benjelloun. Anish Das Sarma. Alon Y. Halevy, and Jennifer Widom. Uldbs:Databases with uncertainty and lineage. In Proc. of VLDB, pages 953-964,2006.
[89]Todd J. Green and Val Tannen. Models for incomplete and probabilistic in-formation. IEEE Date Engineering Bulletin,29(1):17-24,2006.
[90]O. Benjelloun, A. Das Sarma, A. Halevy, and J. Widom. Uldbs:Databases with uncertainty and lineage. In Proc. of VLDB, pages 953-964,2006.
[91]Michi Mutsuzaki, Martin Theobald, Ander de Keijzer, Jennifer Widom, Parag Agrawal, Omar Benjelloun, Anish Das Sarma, Raghotham Murthy, and Tomoe Sugihara. Trioone:Layering uncertainty and lineage on a conventional dbms. In Proceeding of the 3rd Biennial Conference on Innovative Data Systems Research, pages 269-274,2007.
[92]O. Benjelloun, A. Das Sarma, A. Halevy, M. Theobald, and J. Widom. Databases with uncertainty and lineage. VLDB Journal,17(2):243-264,2008.
[93]A. Das Sarma, J.D. Ullman, and J. Widom. Schema design for uncertain databases. In proceedings of the 3rd Alberto Mendelzon Internatinal workshop on Foundation of Data Management, pages 223-247,2009.
[94]A. Das Sarma, S.U. Nabar, and J. Widom. Representing uncertain data: uniqueness, equivalence, minimization, and approximation. Technical Report, 2005.
[95]A. Das Sarma. P. Agrawal, S. Nabar, and J. Widom. Towards special-purpose indexes and statistics for uncertain data. In Proceeding of the Workshop on Management of Uncertain Data, pages 57-72,2008.
[96]N. N. Dalvi and D. Suciu. Efficient query evaluation on probabilistic databases. In Proc. of VLDB. pages 864-875,2004.
[97]A. Das Sarma, M. Theobald, and J. Widom. Exploiting lineage for confidence computation in uncertain and probabilistic databases. In Proc. of ICDE, pages 1023-1032.2008.
[98]R. Murthy and J. Widom. Making aggregation work in uncertain and proba-bilistic databases. In Proceeding of the Workshop on Management of Uncertain Data, pages 76-90,2007.
[99]P. Agrawal and J. Widom. Confidence-aware join algorithms. In Proc. of ICDE. pages 628-639.2009.
[100]Christopher Re and Dan Suciu. Approximate lineage for probabilistic databases. Proceedings of the VLDB Endowment (PVLDB 2008).1(1):797-808,2008.
[101]Christian Halaschek-Wiener, Jennifer Golbeck, Andrew Schain, Bijan Parsia, and Jim Hendler. Annotation and provenance tracking in semantic web photo libraries. In Proc. of IPAW, pages 82-89,2006.
[102]P. Buneman, S. Khanna, and W.-C. Tan. On propagation of deletions and annotations through views. In Proc. of SIGMOD, page 150-158,2002.
[103]http://www.cs.cornell.edu/database/maybms/.
[104]http://www.cs.washington.edu/homes/suciu/project-mystiq.html.
[105]http://www.math.ups.edu/anierman/umich/protdb.
[106]http://www.cs.umd.edu/vs/research.htm#pdb.
[107]http://fimi.ua.ac.be/data/.
[108]http://dblp.uni-trier.de/xml/.
[109]J. Chen and K. Yi. Dynamic structures for top-k queries on uncertain data. In Proceedings of the 18th International Symposium on Algorithms and Com-putation, pages 427-438,2007.
[110]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. the MIT Press, pages 265-268,2001.
[2]Evan Welbourne, Magdalena Balazinska, Gaetano Borriello, and Waylon Brunette. Challenges for pervasive rfid-based infrastructures. In In Proc. of PERTEC, pages 388-394,2007.
[3]http://www.seo371.cn/wlqy/wlqyn_684.html.
[4]A. Deshpande, C. Guestrin. S. Madden, J. M. Hellerstein. and W. Hong. Model-driven data acquisition in sensor networks. In In Proc. of VLDB, page 588-599,2004.
[5]谷峪,于戈,张天成RFID复杂事件处理技术.计算机科学与探索.2007.1(3)：255-267.
[6]徐琳.在前沿科学问题上开展国际合作提升我国射频识别数据管理科研水平.计算机科学与探索,2007,1(3)：347-350.
[7]Babcock B, Babu S, Datar M, Motwani R, and Widom J. Models and issues in data stream systems. In Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 1-16, 2006.
[8]金澈清,钱卫宁,周傲英.流数据分析与管理综述.软件学报.2004,15(8)：1172-1181.
[9]E. Gradel, Y. Gurevich, and C. Hirsch. The complexity of query reliability. In Proc. of SIGMOD, pages 227-234,1998.
[10]N. Dalvi and D. Suciu. The dichotomy of conjunctive queries on probabilistic structures. In Proc. of SIGMOD, pages 293-302,2007.
[11]高明,金澈清,王晓玲,田秀霞,周傲英.数据世系管理技术研究综述.计算机学报,2010,33(3)：373-389.
[12]S. Abiteboul, P. Kanellakis, and G. Grahne. On the representation and query-ing of sets of possible worlds. Proc. of SIGMOD,16(3):34-48,1987.
[13]Todd J. Green and Val Tannen. Models for incomplete and probabilistic in-formation. IEEE Date Engineering Bulletin,29(1):17-24,2006.
[14]R. Cavallo and M. Pittarelli. The theory of probabilistic databases. In Proc. of VLDB, pages 71-81,1987.
[15]D. Barbara. H. Garcia-Molina, and D. Porter. The management of probabilistic data. IEEE Transactions on Knowledge and Data Engineering,4(5):487-502, 1992.
[16]N. Fuhr and T. Rolleke. A probabilistic relational algebra for the integration of information retrieval and database systems. ACM Transactions on Infor-mation Systems,15(1):32-66,1997.
[17]E. Zim'anyi. Query evaluation in probabilistic relational databases. In TCS, pages 1-2,1997.
[18]L. V. S Lakshmanan, N. Leone, R. Ross. and V. S. Subrahmanian. Probview:A flexible database system. ACM Transactions on Database Systems.22(3):419-469,1997.
[19]A. Nierman and H. V. Jagadish. Protdb:Probabilistic data in xml. In Proc. of VLDB, pages 421-432,2002.
[20]S. Abiteboul and P. Senellart. Querying and updating probabilistic informa-tion in xml. In Proceedings of the 9th international conference on Extending database technology:Advances in database technology, pages 1059-1068,2006.
[21]P. Senellart and S. Abiteboul. On the complexity of managing probabilistic xml data. In Proc. of PODS, pages 217-228,2007.
[22]Sara Cohen, Benny Kimelfeld, and Yehoshua Sagiv. Incorporating constraints in probabilistic xml. In Proc. of PODS, pages 61-73,2008.
[23]E. Hung, L. Getoor, and V. S. Subrahmanian. Pxml:A probabilistic semistruc-tured data model and algebra. In Proc. of ICDE, pages 126-137,2003.
[24]E. Hung, L. Getoor, and V.S. Subrahmanian. Probabilistic interval xml. ACM Transactions on Computational Logic,8(4):24,2007.
[25]Benny Kimelfeld, Yuri Kosharovsky, and Yehoshua Sagiv. Query efficiency in probabilistic xml models. In Proc. of PODS, pages 436-447,2008.
[26]P. Hintsanen. The most reliable subgraph problem. In Proceedings of the 11th European conference on principles and practice of knowledge discovery in databases, pages 471-478,2007.
[27]P. Hintsanen and H. Toivonen. Finding reliable subgraphs from large proba-bilistic graphs. Data Min Knowl Disc,17(3):3-23,2008.
[28]Eytan Adar and Christopher Re. Managing uncertainty in social networks. IEEE Data Eng. Bull,30(2):15-22,2006.
[29]T. S. Jayram, S. Kale, and E. Vee. Efficient aggregation algorithms for prob-abilistic data. In Proc. of SIAM, pages 346-355,2007.
[30]G. Cormode and M. Garofalakis. Sketching probabilistic data streams. In Proc. of SIGMOD, pages 346-357,2007.
[31]Cheqing Jin, Ke Yi, Lei Chen 0002, Jeffrey Xu Yu, and Xuemin Lin. Sliding-window top-k queries on uncertain streams. PVLDB, 1(1):301-312,2008.
[32]Christopher Re, Julie Letchner, Magdalena Balazinska, and Dan Suciu. Event queries on correlated probabilistic streams. In Proc. of SIGMOD, pages 469-480,2008.
[33]P. Andritsos, A. Fuxman, and R. J. Miller. Clean answers over dirty databases: A probabilistic approach. In Proc. of ICDE, page 30,2006.
[34]P. Sen and A. Deshpande. Representing and querying correlated tuples in probabilistic databases. In Proc. of ICDE, pages 596-605,2007.
[35]B. Kimelfeld and Y. Sagiv. Matching twigs in probabilistic xml. In Proc. of VLDB, pages 69-80,2007.
[36]L. G. Viliant. The complexity of enumeration and reliability prblems. SIAM JL of Computing,8(3):124-156,1979.
[37]J. S. Provan and M. O. Ball. The complexity of counting cuts and of computing the probability that a graph is connented. SIAM JL of Computing,12(4):241-263,1983.
[38]邹兆年、李建中、高宏、张硕,从不确定图中挖掘频繁子图模式,软件学报,2009,20(11)：2965-2976.
[39]Hongrae Lee, Raymond T. Ng, and Kyuseok Shim. Power-law based estimation of set similarity join size. Proc. of PVLDB,2(1):658-669,2009.
[40]Sunita Sarawagi and Alok Kirpal. Efficient set joins on similarity predicates. In proc. of ACM SIGMOD, pages 743-754,2004.
[41]Ashwin R. Bharambe, Mukesh Agrawal, and Srinivasan Seshan. Mercury:sup-porting scalable multi-attribute range queries. In proc. of ACM SIGCOMM, pages 353-366,2004.
[42]Ihab F. Ilyas, Walid G. Aref, and Ahmed K. Elmagarmid. Supporting top-k join queries in relational databases. VLDB J.,13(3):207-221,2004.
[43]Stephan Borzsonyi. Donald Kossmann, and Konrad Stocker. The skyline op-erator. In proc. of ICDE, pages 421-430,2001.
[44]Thomas Brinkhoff, Hans-Peter Kriegel, and Bernhard Seeger. Efficient pro-cessing of spatial joins using r-trees. In proc. of ACM SIGMOD, pages 237-246, 1993.
[45]Chuan Xiao, Wei Wang, and Xuemin Lin. Ed-join:an efficient algorithm for similarity joins with edit distance constraints. Proc. of PVLDB, 1(1):933-944, 2008.
[46]Arvind Arasu, Venkatesh Ganti, and Raghav Kaushik. Efficient exact set-similarity joins. In proc. of VLDB, pages 918-929,2006.
[47]Vebjorn Ljosa and Ambuj K. Singh. Top-k spatial joins of probabilistic objects In proc. of ICDE, pages 566-575.2008.
[48]Hans-Peter Kriegel, Peter Kunath. Martin Pfeifle, and Matthias Renz. Proba-bilistic similarity join on uncertain data. In Proc. of DASFAA, pages 295-309. 2006.
[49]Jeffrey Jestes, Feifei Li, Zhepeng Yan, and Ke Yi. Probabilistic string similarity joins. In Proc. of ACM SIGMOD, pages 327-338,2010.
[50]Xiang Lian and Lei Chen. Set similarity join on probabilistic data. Proc. of PVLDB,3(1):650-659,2010.
[51]M. A. Soliman, I. F. Ilyas, and K. C. Chang. Top-k query processing in uncer-tain databases. In Proc. of ICDE, pages 896-905,2007.
[52]Graham Cormode, Feifei Li, and Ke Yi. Semantics of ranking queries for probabilistic data and expected ranks. In Proc. of ICDE,2009.
[53]M. Hua, Jian Pei, Wenjie Zhang, and Xuemin Lin. Efficiently answering prob-abilistic threshold top-k queries on uncertain data. In Proc. of ICDE, pages 1403-1405,2008.
[54]J. Chen and K. Yi. Dynamic structures for top-k queries on uncertain data. In Proceedings of the 18th International Symposium on Algorithms and Com-putation, pages 427-438,2007.
[55]Ming Hua, Jian Pei, Wenjie Zhang, and Xuemin Lin. Ranking queries on uncertain data:A probabilistic threshold approach. In Proc. of SIGMOD, pages 673-686,2008.
[56]Cheqing Jin, Ke Yi, Lei Chen, Jeffrey Xu Yu. and Xuemin Lin. Sliding-window top-k queries on uncertain streams. In Proc. of VLDB. pages 293-302,2008.
[57]Christopher Re. Nilesh Dalvi, and Dan Suciu. Efficient top-k query evaluation on probabilistic data. In Proc. of ICDE. pages 886-895.2007.
[58]J. Pei, B. Jiang. X. Lin, and Y. Yuan. Probabilistic skylines on uncertain data. In Proc. of VLDB, pages 15-26.2007.
[59]Ke Yi, Xiang Lian, Feifei Li, and Lei Chen. A concise representation of range queries. In proc. of ICDE, pages 1179-1182,2009.
[60]Jia Xu, Zhenjie Zhang, Anthony K. H. Tung, and Ge Yu. Efficient and effec-tive similarity search over probabilistic data based on earth mover's distance. PVLDB,3(1):758-769.2010.
[61]Jian Li, Barna Saha. and Amol Deshpande. A unified approach to ranking in probabilistic databases. PVLDB,2(1):502-513.2009.
[62]Jian Li and Amol Deshpande. Ranking continuous probabilistic datasets. PVLDB,3(1):638-649.2010.
[63]R. Cheng. Xia Y, S. Prabhakar, R. Shah, and J. S. Vitter. Efficient indexing methods for probabilistic threshold queries over uncertain data. In Proc. of VLDB, pages 876-887,2004.
[64]Y. Tao, X. Xiao, and R. Cheng. Range search on multidimensional uncertain data. ACM Transactions on Database Systems,32(3):15,2007.
[65]Y. Ishikawa, Y. Iijima, and Jeffrey Xu Yu. Spatial range querying for gaussian-based imprecise query objects. In Proc. of ICDE, pages 676-687,2009.
[66]X. Lian and L. Chen. Probabilistic ranked queries in uncertain databases. In Proc. of EDBT, pages 511-522,2008.
[67]Xiang Lian and Lei Chen. Probabilistic group nearest neighbor queries in uncertain databases. TKDE,20(6):809-824,2008.
[68]Vebjorn Ljosa and Ambuj K. Singh. Apla:Indexing arbitrary probability distributions. In Proc. of ICDE, pages 946-955,2007.
[69]G. Beskales, M. A. Soliman, and I. F. Ilyas. Efficient search for the top-k probable nearest neighbors in uncertain databases. Proc. of PVLDB,1(1):326-339,2008.
[70]Muhammad Aamir Cheema, Xuemin Lin, Wei Wang, Wenjie Zhang, and Jian Pei. Probabilistic reverse nearest neighbor queries on uncertain data. IEEE Trans. Knowl. Data Eng.,22(4):550-564,2010.
[71]Ying Zhang, Xuemin Lin. Gaoping Zhu, Wenjie Zhang, and Qianlu Lin. Ef-ficient rank based knn query processing over uncertain data. In ICDE, pages 28-39,2010.
[72]X. Lian and L. Chen. Monochromatic and bichromatic reverse skyline search over uncertain databases. In Proc. of SIGMOD, pages 213-226,2008.
[73]K. Deng, X. Zhou, and H. T. Shen. Multi-source skyline query processing in road networks. In Proc. of ICDE, pages 796-805,2007.
[74]Dimitris Sacharidis, Anastasios Arvanitis, and Timos K. Sellis. Probabilistic contextual skylines. In ICDE, pages 273-284,2010.
[75]Y. Richard Wang and Stuart E. Madnick. A polygen model for heterogeneous database systems:the source tagging perspective. In Proc. of VLDB, pages 519-538.1990.
[76]Y. Cui, J. Widom, and J. L. Wiener. Tracing the lineage of view data in a warehousing environment. The ACM Transactions on Database Systems, 25(2):179-227,2000.
[77]P. Buneman, S. Khanna, and W. C. Tan. Why and where:a characterization of data provenance. In Proc. of ICDE, pages 316-330,2001.
[78]Boris Glavic and Klaus Dittrich. Data provenance:A categorization of existing approaches. In Proceeding of the 6th MMC Workshop of BTW 2007, pages 227-241,2007.
[79]Todd J. Green, Gregory Karvounarakis, Nicholas E. Taylor, Olivier Biton, Zachary G. Ives, and Val Tannen. Orchestra:facilitating collaborative data sharing. In Proc. of SIGMOD, pages 1131-1133,2007.
[80]Todd J. Green, Grigoris Karvounarakis, Zachary G. Ives, and Val Tannen. Update exchange with mappings and provenance. In Proc. of VLDB, pages 675-686,2007.
[81]Todd J. Green, Gregory Karvounarakis, and Val Tannen. Provenance semir-ings. In PODS, pages 31-40,2007.
[82]N. Fuhr and T. R'olleke. Incomplete information in relational databases. JACM,31(4):761-791,1984.
[83]T. J.Green. G. Karvounarakis, and V. Tannen. Provenance semirings. In Proc. of SIGMOD. pages 31-40,2007.
[84]Rajendra Bose and James Frew. Lineage retrieval for scientific data processing: a survey. ACM Computer Surveys,37(1):1-28.2005.
[85]Laura Chiticariu. Wang-Chiew Tan, and Gaurav Vijayvargiya. Dbnotes:a post-it system for relational databases based on provenance. In Proc. of SIG-MOD. pages 942-944.2005.
[86]Marion Blount, John Davis, Archan Misra. Daby Sow, and Min Wang. A time-and-value centric provenance model and architecture for medical event streams. In Proceeding of the 1st International Workshop on Systems and Networking Support for Healthcare and Assisted Living Environments, pages 95-100,2007.
[87]Bhargav Kanagal and Amol Deshpande. Lineage processing over correlated probabilistic databases. In SIGMOD Conference, pages 675-686,2010.
[88]Omar Benjelloun. Anish Das Sarma. Alon Y. Halevy, and Jennifer Widom. Uldbs:Databases with uncertainty and lineage. In Proc. of VLDB, pages 953-964,2006.
[89]Todd J. Green and Val Tannen. Models for incomplete and probabilistic in-formation. IEEE Date Engineering Bulletin,29(1):17-24,2006.
[90]O. Benjelloun, A. Das Sarma, A. Halevy, and J. Widom. Uldbs:Databases with uncertainty and lineage. In Proc. of VLDB, pages 953-964,2006.
[91]Michi Mutsuzaki, Martin Theobald, Ander de Keijzer, Jennifer Widom, Parag Agrawal, Omar Benjelloun, Anish Das Sarma, Raghotham Murthy, and Tomoe Sugihara. Trioone:Layering uncertainty and lineage on a conventional dbms. In Proceeding of the 3rd Biennial Conference on Innovative Data Systems Research, pages 269-274,2007.
[92]O. Benjelloun, A. Das Sarma, A. Halevy, M. Theobald, and J. Widom. Databases with uncertainty and lineage. VLDB Journal,17(2):243-264,2008.
[93]A. Das Sarma, J.D. Ullman, and J. Widom. Schema design for uncertain databases. In proceedings of the 3rd Alberto Mendelzon Internatinal workshop on Foundation of Data Management, pages 223-247,2009.
[94]A. Das Sarma, S.U. Nabar, and J. Widom. Representing uncertain data: uniqueness, equivalence, minimization, and approximation. Technical Report, 2005.
[95]A. Das Sarma. P. Agrawal, S. Nabar, and J. Widom. Towards special-purpose indexes and statistics for uncertain data. In Proceeding of the Workshop on Management of Uncertain Data, pages 57-72,2008.
[96]N. N. Dalvi and D. Suciu. Efficient query evaluation on probabilistic databases. In Proc. of VLDB. pages 864-875,2004.
[97]A. Das Sarma, M. Theobald, and J. Widom. Exploiting lineage for confidence computation in uncertain and probabilistic databases. In Proc. of ICDE, pages 1023-1032.2008.
[98]R. Murthy and J. Widom. Making aggregation work in uncertain and proba-bilistic databases. In Proceeding of the Workshop on Management of Uncertain Data, pages 76-90,2007.
[99]P. Agrawal and J. Widom. Confidence-aware join algorithms. In Proc. of ICDE. pages 628-639.2009.
[100]Christopher Re and Dan Suciu. Approximate lineage for probabilistic databases. Proceedings of the VLDB Endowment (PVLDB 2008).1(1):797-808,2008.
[101]Christian Halaschek-Wiener, Jennifer Golbeck, Andrew Schain, Bijan Parsia, and Jim Hendler. Annotation and provenance tracking in semantic web photo libraries. In Proc. of IPAW, pages 82-89,2006.
[102]P. Buneman, S. Khanna, and W.-C. Tan. On propagation of deletions and annotations through views. In Proc. of SIGMOD, page 150-158,2002.
[103]http://www.cs.cornell.edu/database/maybms/.
[104]http://www.cs.washington.edu/homes/suciu/project-mystiq.html.
[105]http://www.math.ups.edu/anierman/umich/protdb.
[106]http://www.cs.umd.edu/vs/research.htm#pdb.
[107]http://fimi.ua.ac.be/data/.
[108]http://dblp.uni-trier.de/xml/.
[109]J. Chen and K. Yi. Dynamic structures for top-k queries on uncertain data. In Proceedings of the 18th International Symposium on Algorithms and Com-putation, pages 427-438,2007.
[110]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. the MIT Press, pages 265-268,2001.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |