Practical Preference Relations for Large Data Sets

Kenneth A. Ross; Peter Stuckey; Amelie Marian

Practical Preference Relations for Large Data Sets
Ross, Kenneth A.
Stuckey, Peter
Marian, Amelie
Technical reports
Computer Science
Persistent URL:
Columbia University Computer Science Technical Reports
Part Number:
Department of Computer Science, Columbia University
Publisher Location:
New York
User-defined preferences allow personalized ranking of query results. A user provides a declarative specification of his/her preferences, and the system is expected to use that specification to give more prominence to preferred answers. We study constraint formalisms for expressing user preferences as base facts in a partial order. We consider a language that allows comparison and a limited form of arithmetic, and show that the transitive closure computation required to complete the partial order terminates. We consider various ways of composing partial orders from smaller pieces, and provide results on the size of the resulting transitive closures. We introduce the notion of ``covering composition,'' which solves some semantic problems apparent in previous notions of composition. Finally, we show how preference queries within our language can be supported by suitable index structures for efficient evaluation over large data sets. Our results provide guidance about when complex preferences can be efficiently evaluated, and when they cannot.
Computer science
Item views
text | xml
Suggested Citation:
Kenneth A. Ross, Peter Stuckey, Amelie Marian, 2006, Practical Preference Relations for Large Data Sets, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:29465.

Center for Digital Research and Scholarship at Columbia University Libraries | Terms of Use | Copyright