Two new Top-k queries in uncertain database

doi:10.3969/j.issn.1000-5641.2017.01.007

Abstract

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

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.

References

[ 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.