@article {13351,
	title = {A unified approach to ranking in probabilistic databases},
	journal = {The VLDB Journal},
	volume = {20},
	year = {2011},
	month = {2011/04//},
	pages = {249 - 275},
	abstract = {Ranking is a fundamental operation in data analysis and decision support and plays an even more crucial role if the dataset being explored exhibits uncertainty. This has led to much work in understanding how to rank the tuples in a probabilistic dataset in recent years. In this article, we present a unified approach to ranking and top-k query processing in probabilistic databases by viewing it as a multi-criterion optimization problem and by deriving a set of features that capture the key properties of a probabilistic dataset that dictate the ranked result. We contend that a single, specific ranking function may not suffice for probabilistic databases, and we instead propose two parameterized ranking functions, called PRF                           {\textquestiondown}              and PRF             e, that generalize or can approximate many of the previously proposed ranking functions. We present novel generating functions-based algorithms for efficiently ranking large datasets according to these ranking functions, even if the datasets exhibit complex correlations modeled using probabilistic and/xor trees or Markov networks. We further propose that the parameters of the ranking function be learned from user preferences, and we develop an approach to learn those parameters. Finally, we present a comprehensive experimental study that illustrates the effectiveness of our parameterized ranking functions, especially PRF             e, at approximating other ranking functions and the scalability of our proposed algorithms for exact or approximate ranking.},
	keywords = {Approximation techniques, Graphical models, Learning to rank, Probabilistic databases, Ranking},
	isbn = {1066-8888},
	doi = {10.1007/s00778-011-0220-3},
	url = {http://dx.doi.org/10.1007/s00778-011-0220-3},
	author = {Li,Jian and Saha,Barna and Deshpande, Amol}
}
@conference {12402,
	title = {Connections between the lines: augmenting social networks with text},
	booktitle = {Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining},
	series = {KDD {\textquoteright}09},
	year = {2009},
	month = {2009///},
	pages = {169 - 178},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {Network data is ubiquitous, encoding collections of relationships between entities such as people, places, genes, or corporations. While many resources for networks of interesting entities are emerging, most of these can only annotate connections in a limited fashion. Although relationships between entities are rich, it is impractical to manually devise complete characterizations of these relationships for every pair of entities on large, real-world corpora. In this paper we present a novel probabilistic topic model to analyze text corpora and infer descriptions of its entities and of relationships between those entities. We develop variational methods for performing approximate inference on our model and demonstrate that our model can be practically deployed on large corpora such as Wikipedia. We show qualitatively and quantitatively that our model can construct and annotate graphs of relationships and make useful predictions.},
	keywords = {Graphical models, social network learning, statistical topic models},
	isbn = {978-1-60558-495-9},
	doi = {10.1145/1557019.1557044},
	url = {http://doi.acm.org/10.1145/1557019.1557044},
	author = {Chang,Jonathan and Jordan Boyd-Graber and Blei,David M.}
}
@conference {13364,
	title = {Ef?cient Query Evaluation over Temporally Correlated Probabilistic Streams},
	booktitle = {IEEE 25th International Conference on Data Engineering, 2009. ICDE {\textquoteright}09},
	year = {2009},
	month = {2009/04/29/March},
	pages = {1315 - 1318},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {In this paper, we address the problem of efficient query evaluation over highly correlated probabilistic streams. We observe that although probabilistic streams tend to be strongly correlated in space and time, the correlations are usually quite structured (i.e., the same set of dependencies and independences repeat across time) and Markovian (i.e., the state at time "t+1" is independent of the states at previous times given the state at time "t"). We exploit this observation to compactly encode probabilistic streams by decoupling the correlation structure (the set of dependencies) from the actual probability values. We develop novel stream processing operators that can efficiently and incrementally process new data items; our operators are based on the previously proposed framework of viewing probabilistic query evaluation as inference over probabilistic graphical models (PGMs) [P. Sen and A. Deshpande, 2007]. We develop a query planning algorithm that constructs efficient query plans that are executable in polynomial-time whenever possible, and we characterize queries for which such plans are not possible. Finally we conduct an extensive experimental evaluation that illustrates the advantages of exploiting the structured nature of correlations in probabilistic streams.},
	keywords = {Birds, Computerized monitoring, correlated probabilistic streams, correlation structure, Data engineering, data mining, Databases, Event detection, Graphical models, inference mechanisms, Markov processes, polynomial time, probabilistic database, probabilistic graphical model, probabilistic query evaluation, query evaluation, query planning algorithm, query plans, Query processing, Random variables, stream processing operator, Streaming media},
	isbn = {978-1-4244-3422-0},
	doi = {10.1109/ICDE.2009.229},
	author = {Kanagal,B. and Deshpande, Amol}
}
