两种新的非确定数据库上的Top-k查询

doi:10.3969/j.issn.1000-5641.2017.01.007

华东师范大学学报(自然科学版)

两种新的非确定数据库上的Top-k查询

邱鑫, 林欣

上海市多维度信息处理重点实验室华东师范大学, 上海 200241

收稿日期:2015-11-27 出版日期:2017-01-25 发布日期:2017-01-13
通讯作者: 林欣, 男, 副教授, 研究方向为新型数据处理. E-mail: xlin@cs.ecnu.edu.cn.
基金资助:
国家自然科学基金(61572193);
上海张江国家自主创新示范区专项发展基金(201411-JA-B108-002);
上海市科学技术委员会项目(14DZ2260800)

Two new Top-k queries in uncertain database

QIU Xin, LIN Xin

Shanghai Key Laboratory of Multidimensional Information Processing, East China Normal University, Shanghai 200241, China

Received:2015-11-27 Online:2017-01-25 Published:2017-01-13

摘要/Abstract

摘要：

由于当前已有的在非确定数据库上的 Top-k 查询普遍基于元组层面, 使得应用受限. 为了让查询结果更符合直觉, 提出了两种新的非确定数据库上的基于 x-元组层面的 Top-k 查询及其执行算法. 这两种新的查询综合 x-元组中各元组的评分和置信度, 获得在返回结果中最具实际意义的位置. 查询的执行算法经过优化,执行效率明显改善.

关键词: 非确定数据库, Top-k 查询

Abstract:

Since the pre-existing Top-k queries in uncertain databases almost are based on tuple level rather than x-tuple level restricts its application. The paper proposes two new instance-level Top-k queries and executive algorithm in uncertain databases in order to get intuitive query results. These two new queries take both rank and confidence of each x-tuple’s tuple, figuring out the most meaningful position in the returned results. After the optimization of the executive algorithm, its executive efficiency has been improved significantly.

Key words: uncertain database, Top-k query

邱鑫, 林欣. 两种新的非确定数据库上的Top-k查询[J]. 华东师范大学学报(自然科学版), doi: 10.3969/j.issn.1000-5641.2017.01.007.

QIU Xin, LIN Xin. Two new Top-k queries in uncertain database[J]. Journal of East China Normal University(Natural Sc, doi: 10.3969/j.issn.1000-5641.2017.01.007.

参考文献

[ 1 ] AGGARWAL C C, REDDY C K. Data Clustering: Algorithms and Applications[M]. Boca Raton, FL, USA:CRC Press, 2013.
[ 2 ] Z¨ UFLE A, EMRICH T, SCHMID K A, et al. Representative clustering of uncertain data [C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2014: 243-252.
[ 3 ] LI L, ZHANG X, YU Z, et al. USOM: Mining and visualizing uncertain data based on self-organizing maps [C]//Machine Learning and Cybernetics (ICMLC), 2011 International Conference on. IEEE, 2011, 2: 804-809.
[ 4 ] CONINX A, BONNEAU G P, DROULEZ J, et al. Visualization of uncertain scalar data fields using color scales and perceptually adapted noise [C]//Proceedings of the ACM SIGGRAPH Symposium on Applied Perception in Graphics and Visualization. ACM, 2011: 59-66.
[ 5 ] AGGARWAL C C. Trio a system for data uncertainty and lineage [M]//Managing and Mining Uncertain Data.New York: Springer, 2009: 113-147.
[ 6 ] FUXMAN A, FAZLI E, MILLER R J. ConQuer: Efficient management of inconsistentdatabases[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD’05). ACM, 2005: 155-166.
[ 7 ] SINGH S, MAYFIELD C, MITTAL S, et al. Orion 2.0: Native support for uncertain data [C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. ACM, 2008: 1239-1242.
[ 8 ] BENJELLOUN O, SARMA A D, HAYWORTH C, et al. An introduction to ULDBs and the Trio system [J]. IEEE Data Engineering Bulletin Special Issue on Probabilistic Databases, 2006, 29(1): 2006.
[ 9 ] ABITEBOUL S, KANELLAKIS P C, GRAHNE G. On the representation and querying of sets of possible worlds [C]//Association for Computing Machinery Special Interest Group on Management of Data 1987 Conference. ACM, 1987: 34-48.
[10] BENJELLOUN O, SARMA A D, HALEVY A, et al. Databases with uncertainty and lineage [J]. The VLDB Journal, 2008, 17(2): 243-264.
[11] SISTLA A P, WOLFSON O, CHAMBERLAIN S, et al. Querying the uncertain position of moving objects [M]//Temporal Databases: Research and Practice. Berlin: Springer, 1998: 310-337.
[12] CHENG R, KALASHNIKOV D V, PRABHAKAR S. Querying imprecise data in moving object environments [J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(9): 1112-1127.
[13] DE ALMEIDA V T, G¨ UTING R H. Supporting uncertainty in moving objects in network databases [C]//Proceedings of the 13th Annual ACM International Workshop on Geographic Information Systems. ACM, 2005: 31-40.
[14] SILBERSTEIN A S, BRAYNARD R, ELLIS C, et al. A sampling-based approach to optimizing top-k queries in sensor networks [C]//Proceedings of the 22nd International Conference on Data Engineering. IEEE, 2006: 68-68.
[15] CONSIDINE J, LI F, KOLLIOS G, et al. Approximate aggregation techniques for sensor databases [C]//Proceedings of the 20th International Conference on Data Engineering. IEEE, 2004: 449-460.
[16] JAYRAM T S, KRISHNAMURTHY R, RAGHAVAN S, et al. Avatar Information Extraction System [J]. IEEE Data Eng Bull, 2006, 29(1): 40-48.
[17] GUPTA R, SARAWAGI S. Creating probabilistic databases from information extraction models [C]//Proceedings of the 32nd International Conference on Very Large Databases. 2006: 965-976.
[18] ILYAS I F, BESKALES G, SOLIMAN M A. A survey of Top-k query processing techniques in relational database systems [J]. ACM Computing Surveys (CSUR), 2008, 40(4): 11-11.
[19] GETOOR L, DIEHL C P. Link mining: A survey [J]. ACM SIGKDD Explorations Newsletter, 2005, 7(2): 3-12.
[20] HRISTIDIS V, KOUDAS N, PAPAKONSTANTINOU Y. PREFER: A system for the efficient execution of multiparametric ranked queries [J]. ACM SIGMOD Record, 2001, 30(2): 259-270.
[21] NATSEV A, CHANG Y C, SMITH J R, et al. Supporting incremental join queries on ranked inputs [C]//Proceedings of the 27th VLDB Conference. 2001: 281-290.
[22] ILYAS I F, SHAH R, AREF W G, et al. Rank-aware query optimization [C]//Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. ACM, 2004: 203-214.
[23] LI C, CHANG K C C, ILYAS I F, et al. RankSQL: Query algebra and optimization for relational top-k queries [C]//Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. ACM, 2005: 131-142.
[24] HUA M, PEI J, ZHANG W, et al. Ranking queries on uncertain data: a probabilistic threshold approach[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. ACM, 2008: 673-686.
[25] ZHANG X, CHOMICKI J. Semantics and evaluation of Top-k queries in probabilistic databases[J]. Distributed and Parallel Databases, 2009, 26(1): 67-126.

两种新的非确定数据库上的Top-k查询

Two new Top-k queries in uncertain database

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价