Two new Top-<i>k</i> queries in uncertain database

QIU Xin; LIN Xin

doi:10.3969/j.issn.1000-5641.2017.01.007

Issue 1

Jan. 2017

Turn off MathJax

Article Contents

Article Navigation > Journal of East China Normal University (Natural Sciences) > 2017 > (1): 52-63

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

Citation:

QIU Xin, LIN Xin. Two new Top-k queries in uncertain database[J]. Journal of East China Normal University (Natural Sciences), 2017, (1): 52-63. 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 Sciences), 2017, (1): 52-63. doi: 10.3969/j.issn.1000-5641.2017.01.007

Citation:

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

PDF( 477 KB)

Two new Top-k queries in uncertain database

doi: 10.3969/j.issn.1000-5641.2017.01.007

QIU Xin,
LIN Xin^,

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

Received Date: 2015-11-01
Publish Date: 2017-01-25

Abstract

Abstract

Since currently, the pre-existing Top-k queries in uncertain databases almost bases on tuple level rather than xtuple level, which restricts its application, for intuitive query result, the paper proposes two new local-instance level top-k queries and executive algorithm in uncertain databases. 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 manifestly.
- uncertain database,
- Top-k query

FullText(HTML)

References(25)

References

[1]	Data clustering: algorithms and applications[M]. CRC Press, 2013.
[2]	ZÖFLE 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. Springer US, 2009: 1-35.
[6]	FUXMAN, A, FAZLI, E, AND MILLER, R. J. 2005. ConQuer: Efficient management of inconsistentdatabases. In Proceedings of the ACM SIGMOD International Conference on Management ofData (SIGMOD'05). ACM, New York, 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, March 2006, 2006.
[9]	ABITEBOUL S, KANELLAKIS P, GRAHNE G. On the representation and querying of sets of possible worlds [M]. ACM, 1987.
[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. Springer Berlin Heidelberg, 1998: 310-337.
[12]	CHENG R, KALASHNIKOV D V, PRABHAKAR S. Querying imprecise data in moving object environments [J]. Knowledge and Data Engineering, IEEE Transactions on, 2004, 16(9): 1112-1127.
[13]	DE ALMEIDA V T, G\"{U]TING 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]//Data Engineering, 2006. ICDE'06. Proceedings of the 22nd International Conference on. IEEE, 2006: 68-68.
[15]	CONSIDINE J, LI F, KOLLIOS G, et al. Approximate aggregation techniques for sensor databases [C]//Data Engineering, 2004. Proceedings. 20th International Conference on. 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 international conference on Very large data bases. 2006, 32(2): 965.
[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 multi-parametric ranked queries [C]//ACM SIGMOD Record. ACM, 2001, 30(2): 259-270.
[21]	NATSEV A, CHANG Y C, SMITH J R, et al. Supporting incremental join queries on ranked inputs [C]//VLDB. 2001, 1: 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.