text:
# Round-robin tournament

Last updated

A round-robin tournament (or all-play-all tournament) is a competition in which each contestant meets every other participant, usually in turn. [1] [2] A round-robin contrasts with an elimination tournament, in which participants are eliminated after a certain number of losses.

## Terminology

The term round-robin is derived from the French term ruban, meaning "ribbon". Over a long period of time, the term was corrupted and idiomized to robin. [3] [4]

In a single round-robin schedule, each participant plays every other participant once. If each participant plays all others twice, this is frequently called a double round-robin. The term is rarely used when all participants play one another more than twice, [1] and is never used when one participant plays others an unequal number of times (as is the case in almost all of the major United States professional sports leagues – see AFL (1940–41) and All-America Football Conference for exceptions). In the United Kingdom, a round-robin tournament has been called an American tournament in sports such as tennis or billiards which usually have knockout tournaments, although this is now rarely, if ever, done. [5] [6] [7] In Italian it is called girone all'italiana (literally "Italian-style group"). In Serbian it is called the Berger system (Бергеров систем, Bergerov sistem), after chess player Johann Berger. In Brazil it is called (sistema de pontos corridos), referring to the accumulation of accounted points as the determinant of each participant's final performance, once all participants have played their games.

A round-robin tournament with four players is sometimes called "quad" or "foursome". [8]

## Use

In sports with a large number of competitive matches per season, double round-robins are common. Most association football leagues in the world are organized on a double round-robin basis, in which every team plays all others in its league once at home and once away. This system is also used in qualification for major tournaments such as the FIFA World Cup and the continental tournaments (e.g. UEFA European Championship, CONCACAF Gold Cup, AFC Asian Cup, CONMEBOL Copa América and CAF Cup of Nations). There are also round-robin bridge, chess, draughts, go, ice hockey, curling, and Scrabble tournaments. The World Chess Championship decided in 2005 and in 2007 on an eight-player double round-robin tournament where each player faces every other player once as white and once as black.

In a more extreme example, the KBO League of baseball plays a 16-fold round robin, with each of the 10 teams playing each other 16 times for a total of 144 games per team.

Group tournaments rankings usually go by number of matches won and drawn, with any of a variety of tiebreaker criteria.

Frequently, pool stages within a wider tournament are conducted on a round-robin basis. Examples with single round-robin scheduling include the FIFA World Cup, UEFA European Football Championship, and UEFA Cup (2004–2009) in football, Super Rugby (rugby union) in the Southern Hemisphere during its past iterations as Super 12 and Super 14 (but not in its later 15- and 18-team formats), the Cricket World Cup along with Indian Premier League, major Twenty-20 Cricket tournament, and many American Football college conferences, such as the Big 12 (which currently has 10 members). The group phases of the UEFA club competitions and Copa Libertadores are contested as a double round-robin, as are most basketball leagues outside the United States, including the regular season of the EuroLeague (as well as its former Top 16 phase); the United Football League has used a double round-robin for both its 2009 and 2010 seasons.

Season ending tennis tournaments also use a round robin format prior to the semi on stages.

## Evaluation

The champion in a round-robin tournament is the contestant that wins the most games, except when draws are possible.

In theory, a round-robin tournament is the fairest way to determine the champion from among a known and fixed number of contestants. Each contestant, whether player or team, has equal chances against all other opponents because there is no prior seeding of contestants that will preclude a match between any given pair. The element of luck is seen to be reduced as compared to a knockout system since one or two bad performances need not ruin a competitor's chance of ultimate victory. Final records of participants are more accurate, in the sense that they represent the results over a longer period against the same opposition.

The system is also better for ranking all participants, not just determining the winner. This is helpful to determine the final rank of all competitors, from strongest to weakest, for purposes of qualification for another stage or competition as well as for prize money.

In team sport the (round-robin) major league champions are generally regarded as the "best" team in the land, rather than the (elimination) cup winners.

Moreover, in tournaments such as the FIFA or ICC World Cups, a first round stage consisting of a number of mini round robins between groups of 4 teams guards against the possibility of a team travelling possibly thousands of miles only to be eliminated after just one poor performance in a straight knockout system. The top one, two, or occasionally three teams in these groups then proceed to a straight knockout stage for the remainder of the tournament.

In the circle of death (see below), it is possible that no champion emerges from a round-robin tournament, even if there is no draw. However, most sports have tie-breaker systems which resolve this.

Round-robins can suffer from being too long compared to other tournament types, and with later scheduled games potentially not having any substantial meaning. They may also require tiebreaking procedures.

Swiss system tournaments attempt to combine elements of the round-robin and elimination formats, to provide a worthy champion using fewer rounds than a round-robin, while allowing draws and losses.

#### Tournament length

The main disadvantage of a round robin tournament is the time needed to complete it. Unlike a knockout tournament where half of the participants are eliminated after each round, a round robin requires one round less than the number of participants. For instance, a tournament of 16 teams can be completed in just 4 rounds (i.e. 15 matches) in a knockout (single elimination) format; a double elimination tournament format requires 30 (or 31) matches, but a round-robin would require 15 rounds (i.e. 120 matches) to finish if each competitor faces each other once.

Other issues stem from the difference between the theoretical fairness of the round robin format and practice in a real event. Since the victor is gradually arrived at through multiple rounds of play, teams who perform poorly, who might have been quickly eliminated from title contention, are forced to play out their remaining games. Thus games are played late in the competition between competitors with no remaining chance of success. Moreover, some later matches will pair one competitor who has something left to play for against another who does not. It may also be possible for a competitor to play the strongest opponents in a round robin in quick succession while others play them intermittently with weaker opposition. This asymmetry means that playing the same opponents is not necessarily completely equitable.

There is also no scheduled showcase final match unless (by coincidence) two competitors meet in the last match of the tournament, with the result of that match determining the championship. A notable instance of such an event was the 1950 FIFA World Cup match between Uruguay and Brazil.

#### Qualified teams

Further issues arise where a round-robin is used as a qualifying round within a larger tournament. A competitor already qualified for the next stage before its last game may either not try hard (in order to conserve resources for the next phase) or even deliberately lose (if the scheduled next-phase opponent for a lower-placed qualifier is perceived to be easier than for a higher-placed one).

Four pairs in the 2012 Olympics Women's doubles badminton, having qualified for the next round, were ejected from the competition for attempting to lose in the round robin stage to avoid compatriots and better ranked opponents. [9] The round robin stage at the Olympics was a new introduction, and these potential problems were readily known prior to the tournament; changes were made prior to the next Olympics to prevent a repeat of these events.

#### Circle of death

Another disadvantage, especially in smaller round-robins, is the "circle of death", where teams cannot be separated on a head-to-head record. In a three-team round-robin, where A defeats B, B defeats C, and C defeats A, all three competitors will have a record of one win and one loss, and a tiebreaker will need to be used to separate the teams. [10] This famously happened during the 1994 FIFA World Cup Group E, where all four teams finished with a record of one win, one draw, and one loss. This phenomenon is analogous to the Condorcet paradox in voting theory.

## Scheduling algorithm

If ${\displaystyle n}$ is the number of competitors, a pure round robin tournament requires ${\displaystyle {\begin{matrix}{\frac {n}{2}}\end{matrix}}(n-1)}$ games. If ${\displaystyle n}$ is even, then in each of ${\displaystyle (n-1)}$ rounds, ${\displaystyle {\begin{matrix}{\frac {n}{2}}\end{matrix}}}$ games can be run concurrently, provided there exist sufficient resources (e.g. courts for a tennis tournament). If ${\displaystyle n}$ is odd, there will be ${\displaystyle n}$ rounds, each with ${\displaystyle {\begin{matrix}{\frac {n-1}{2}}\end{matrix}}}$ games, and one competitor having no game in that round.

### Circle method

The circle method is the standard algorithm to create a schedule for a round-robin tournament[ citation needed ]. All competitors are assigned to numbers, and then paired in the first round:

 1 2 3 4 5 6 7 14 13 12 11 10 9 8

Next, one of the competitors in the first or last column of the table is fixed (number one in this example) and the others rotated clockwise one position

 1 14 2 3 4 5 6 13 12 11 10 9 8 7
 1 13 14 2 3 4 5 12 11 10 9 8 7 6

This is repeated until you end up almost back at the initial position:

 1 3 4 5 6 7 8 2 14 13 12 11 10 9

To see that - with an even number ${\displaystyle n}$ of competitors - this algorithm realizes every possible combination of them (equivalently, that all pairs realized are pairwise different), we argue as follows.

First, the algorithm obviously realizes every pair of competitors if one of them equals ${\displaystyle 1}$ (the non-moving competitor).

Next, for pairs of non-${\displaystyle 1}$ competitors, let their distance be the number ${\displaystyle k<{\frac {n}{2}}}$ of times the rotation has to be carried out in order that one competitor arrives at the position the other had.

In the example given (${\displaystyle n=14}$), ${\displaystyle 2}$ has distance ${\displaystyle 1}$ to ${\displaystyle 3}$ and to ${\displaystyle 14}$ and it has distance ${\displaystyle 6}$ to ${\displaystyle 8}$ and to ${\displaystyle 9}$.

In a round, a non-leftmost position (not including ${\displaystyle 1}$) can only be taken by competitors of a fixed distance. In round ${\displaystyle 1}$ of the example, in the second position competitor ${\displaystyle 2}$ plays against ${\displaystyle 13}$, their distance is ${\displaystyle 2}$. In round ${\displaystyle 2}$, this position is held by competitors ${\displaystyle 14}$ and ${\displaystyle 12}$, also having distance ${\displaystyle 2}$, etc. Similarly, the next position (${\displaystyle 3}$ against ${\displaystyle 12}$ in round ${\displaystyle 1}$, ${\displaystyle 2}$ against ${\displaystyle 11}$ in round ${\displaystyle 2}$, etc.) can only hold distance-${\displaystyle 4}$ competitors.

For every ${\displaystyle k<{\frac {n}{2}}}$, there are exactly ${\displaystyle n-1}$ pairs of distance ${\displaystyle k}$. There are ${\displaystyle n-1}$ rounds and they all realize one distance-${\displaystyle k}$ pair at the same position. Clearly, these pairs are pairwise different. The conclusion is that every distance-${\displaystyle k}$ pair is realized.

This holds for every ${\displaystyle k}$, hence, every pair is realized.

If there are an odd number of competitors, a dummy competitor can be added, whose scheduled opponent in a given round does not play and has a bye. The schedule can therefore be computed as though the dummy were an ordinary player, either fixed or rotating.

Instead of rotating one position, any number relatively prime to ${\displaystyle (n-1)}$ will generate a complete schedule. The upper and lower rows can indicate home/away in sports, white/black in chess, etc.; to ensure fairness, this must alternate between rounds since competitor 1 is always on the first row. If, say, competitors 3 and 8 were unable to fulfil their fixture in the third round, it would need to be rescheduled outside the other rounds, since both competitors would already be facing other opponents in those rounds. More complex scheduling constraints may require more complex algorithms. [11] This schedule is applied in chess and draughts tournaments of rapid games, where players physically move round a table. In France this is called the Carousel-Berger system (Système Rutch-Berger). [12]

The schedule can also be used for "asynchronous" round-robin tournaments where all games take place at different times (for example, because there is only one venue). The games are played from left to right in each round, and from the first round to the last. When the number of competitors is even, this schedule performs well with respect to quality and fairness measures such as the amount of rest between games. On the other hand, when the number of competitors is odd, it does not perform so well and a different schedule is superior with respect to these measures. [13]

### Berger tables

Alternatively Berger tables, [14] named after the Austrian chess master Johann Berger, are widely used in the planning of tournaments [15] . Berger published the pairing tables in his two Schach-Jahrbücher (Chess Annals), [16] [17] with due reference to its inventor Richard Schurig. [18] [19]

 Round 1 Round 2 Round 3 ... Round 13 1 – 14 2 – 13 3 – 12 4 – 11 5 – 10 6 – 9 7 – 8 14 – 8 9 – 7 10 – 6 11 – 5 12 – 4 13 – 3 1 – 2 2 – 14 3 – 1 4 – 13 5 – 12 6 – 11 7 – 10 8 – 9 ... 7 – 14 8 – 6 9 – 5 10 – 4 11 – 3 12 – 2 13 – 1

This constitutes a schedule where player 14 has a fixed position, and all other players are rotated counterclockwise ${\displaystyle {\frac {n}{2}}}$ positions. This schedule is easily generated manually. To construct the next round, the last player, number 8 in the first round, moves to the head of the table, followed by player 9 against player 7, player 10 against 6, until player 1 against player 2. Arithmetically, this equates to adding ${\displaystyle {\frac {n}{2}}}$ to the previous row, with the exception of player ${\displaystyle n}$. When the result of the addition is greater than ${\displaystyle (n-1)}$, then subtract ${\displaystyle (n-1)}$ from the sum.

This schedule can also be represented as a (n-1, n-1) table, expressing a round in which players meets each other. For example, player 7 plays against player 11 in round 4. If a player meets itself, then this shows a bye or a game against player n. All games in a round constitutes a diagonal in the table.

Diagonal Scheme
×234567891011121312345678910111213
112345678910111213
212345678910111213
312345678910111213
412345678910111213
512345678910111213
612345678910111213
712345678910111213
812345678910111213
912345678910111213
1012345678910111213
1112345678910111213
1212345678910111213
131 2 3 4 5 6 7 8 9 10111213
Round Robin Schedule
×12345678910111213
112345678910111213
223456789101112131
334567891011121312
445678910111213123
556789101112131234
667891011121312345
778910111213123456
889101112131234567
991011121312345678
1010111213123456789
1111121312345678910
1212131234567891011
1313123456789101112

The above schedule can also be represented by a graph, as shown below:

Both the graph and the schedule were reported by Édouard Lucas in [20] as a recreational mathematics puzzle. Lucas, who describes the method as simple and ingenious, attributes the solution to Felix Walecki, a teacher at Lycée Condorcet. Lucas also included an alternative solution by means of a sliding puzzle.

### Original construction of pairing tables by Richard Schurig (1886)

For an even number ${\displaystyle n}$ or an odd number ${\displaystyle n-1}$ of competitors, Schurig [19] builds a table with ${\displaystyle n/2}$ vertical rows and ${\displaystyle n-1}$ horizontal rows. Then he populates it starting from the top left corner by repeating the sequence of numbers from 1 up to ${\displaystyle n-1}$. Here is an example table for 7 or 8 competitors:

 Round 1 Round 2 Round 3 Round 4 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

Then to get the opponents a second table is constructed. Every horizontal row ${\displaystyle x}$ is populated with the same numbers as row ${\displaystyle x+1}$ in the previous table (the last row is populated with numbers from the first row in the original table), but in the reverse order (from right to left).

Round 1 Round 2 Round 3 Round 4 – 1 – 7 – 6 – 5 – 5 – 4 – 3 – 2 – 2 – 1 – 7 – 6 – 6 – 5 – 4 – 3 – 3 – 2 – 1 – 7 – 7 – 6 – 5 – 4 – 4 – 3 – 2 – 1

By merging above tables we arrive at:

Round 1 Round 2 Round 3 Round 4 1 – 1 2 – 7 3 – 6 4 – 5 5 – 5 6 – 4 7 – 3 1 – 2 2 – 2 3 – 1 4 – 7 5 – 6 6 – 6 7 – 5 1 – 4 2 – 3 3 – 3 4 – 2 5 – 1 6 – 7 7 – 7 1 – 6 2 – 5 3 – 4 4 – 4 5 – 3 6 – 2 7 – 1

Then the first column is updated: if the number of competitors is even, player number ${\displaystyle n}$ is alternatingly substituted for the first and second positions, whereas if the number of competitors is odd a bye is used instead.

The pairing tables were published as an annex concerning the arrangements for the holding of master tournaments. Schurig did not provide a proof nor a motivation for his algorithm. For more historical details, see Ahrens. [21]

## Related Research Articles

The Elo rating system is a method for calculating the relative skill levels of players in zero-sum games such as chess. It is named after its creator Arpad Elo, a Hungarian-American physics professor.

A tournament is a competition involving at least three competitors, all participating in a sport or game. More specifically, the term may be used in either of two overlapping senses:

1. One or more competitions held at a single venue and concentrated into a relatively short time interval.
2. A competition involving a number of matches, each involving a subset of the competitors, with the overall tournament winner determined based on the combined results of these individual matches. These are common in those sports and games where each match must involve a small number of competitors: often precisely two, as in most team sports, racket sports and combat sports, many card games and board games, and many forms of competitive debating. Such tournaments allow large numbers to compete against each other in spite of the restriction on numbers in a single match.

A sports league is a group of sports teams or individual athletes that compete against each other and gain points in a specific sport. At its simplest, it may be a local group of amateur athletes who form teams among themselves and compete on weekends; at its most complex, it can be an international professional league making large amounts of money and involving dozens of teams and thousands of players.

A single-elimination, knockout, or sudden death tournament is a type of elimination tournament where the loser of each match-up is immediately eliminated from the tournament. Each winner will play another in the next round, until the final match-up, whose winner becomes the tournament champion. Each match-up may be a single match or several, for example two-legged ties in European sports or best-of series in American pro sports. Defeated competitors may play no further part after losing, or may participate in "consolation" or "classification" matches against other losers to determine the lower final rankings; for example, a third place playoff between losing semi-finalists. In a shootout poker tournament, there are more than two players competing at each table, and sometimes more than one progressing to the next round. Some competitions are held with a pure single-elimination tournament system. Others have many phases, with the last being a single-elimination final stage, often called playoffs.

A double-elimination tournament is a type of elimination tournament competition in which a participant ceases to be eligible to win the tournament's championship upon having lost two games or matches. It stands in contrast to a single-elimination tournament, in which only one defeat results in elimination.

Repechage is a practice in series competitions that allows participants who failed to meet qualifying standards by a small margin to continue to the next round. A well known example is the wild card system.

A Swiss-system tournament is a non-eliminating tournament format that features a fixed number of rounds of competition, but considerably fewer than for a round-robin tournament; thus each competitor does not play all the other competitors. Competitors meet one-on-one in each round and are paired using a set of rules designed to ensure that each competitor plays opponents with a similar running score, but does not play the same opponent more than once. The winner is the competitor with the highest aggregate points earned in all rounds. With an even number of participants, all competitors play in each round.

The Candidates Tournament is a chess tournament organized by FIDE, chess's international governing body, since 1950, as the final contest to determine the challenger for the World Chess Championship. The winner of the Candidates earns the right to a match for the World Championship against the incumbent World Champion.

There are a number of formats used in various levels of competition in sports and games to determine an overall champion. Some of the most common are the single elimination, the best-of- series, the total points series more commonly known as on aggregate, and the round-robin tournament.

The Page playoff system is a playoff format used primarily in softball and curling at the championship level, the Indian Premier League and Pakistan Super League cricket tournaments. Teams are seeded using a round-robin tournament and the top four play a mix of a single-elimination and double-elimination tournament to determine the winner. It is identical to a four-team McIntyre System playoff, first used by the WANFL, SANFL and VFL in Australia in 1931, originally called the Page–McIntyre system, after the VFL delegate, the Richmond Football Club's Secretary, Percy "Pip" Page, who had advocated its use.

In sport, a bye is the preferential status of a player or team that is automatically advanced to the next round of a tournament, without having to play an opponent in an early round.

In a group tournament, unlike a knockout tournament, there is no scheduled decisive final match. Instead, all the competitors are ranked by examining the results of all the matches played in the tournament. Typically, points are awarded for each match, with competitors ranked based either on total number of points or average points per match.

Swiss system tournaments, a type of group tournament common in chess and other boardgames, use various criteria to break ties between players who have the same total number of points after the last round. This is needed when prizes are indivisible, such as titles, trophies, or qualification for another tournament. Otherwise players often share the tied spots, with cash prizes being divided equally among the tied players.

A chess tournament is a series of chess games played competitively to determine a winning individual or team. Since the first international chess tournament in London, 1851, chess tournaments have become the standard form of chess competition among serious players.

A duplicate bridge movement is a scheme used in a duplicate bridge session to arrange which competitors play which opponents when, and which boards they play. The arrangement has to satisfy various constraints which often conflict to some extent, requiring compromises. The resolution of these compromises is to a considerable extent a matter of taste, so players should be consulted as to their preferences if this is practicable.

Norway Chess is an annual closed chess tournament, typically taking place in the May to June time period every year. The first edition took place in the Stavanger area, Norway, from 7 May to 18 May 2013. The 2013 tournament had ten participants, including seven of the ten highest rated players in the world per the May 2013 FIDE World Rankings. It was won by Sergey Karjakin, with Magnus Carlsen and Hikaru Nakamura tied for second place. Norway Chess 2015 took place in mid-June 2015 and was a part of the inaugural Grand Chess Tour. The tournament has since decided to withdraw from the Grand Chess Tour.

The 2020–2021 Candidates Tournament was an eight-player chess double round-robin tournament to decide the challenger for the World Chess Championship 2021, played in Yekaterinburg, Russia. Ian Nepomniachtchi won the tournament with a round to spare and earned the right to challenge the defending world champion, Magnus Carlsen.

The FIDE World Fischer Random Chess Championship 2019 was the first world championship in Fischer Random Chess officially recognized by the international chess federation FIDE. Previous unofficial championships had been held, with the most recent winner being Magnus Carlsen in 2018. The competition started on April 28, 2019, with the first qualifying tournaments, which took place online and were open to all interested participants; and continued with further rounds up to the quarter-finals, which were also online. The semi-finals and final were played over the board between October 27 to November 2, 2019, in the Henie Onstad Kunstsenter in Bærum in Norway. The winner of the final was Wesley So, defeating Magnus Carlsen 13.5–2.5, to become the first FIDE world champion in Fischer Random Chess. Over the course of the competition, various time controls were applied, with longer games being weighted more heavily.

The 2022 Candidates Tournament was an eight-player chess tournament to decide the challenger for the World Chess Championship 2023. The tournament took place at the Palacio de Santoña in Madrid, Spain, from June 16 to July 5, 2022, with the World Championship to follow in early 2023. As with every Candidates tournament since 2013, it was a double round-robin tournament.

The Champions Chess Tour 2022, known for sponsorship reasons as the Meltwater Champions Chess Tour, is a 9-month series of nine online chess tournaments featuring some of the world's top players, who play for a prize money pool of US\$1.6 million. The tour started on February 19, 2022 and will last until November 20, 2022.

## References

1. Webster's Third New International Dictionary of the English Language, Unabridged (1971, G. & C. Merriam Co), p.1980.
2. Orcutt, William Dana (1895). Official Lawn Tennis Bulletin. Vol. 2. New York: The Editors. pp. 1, 3.
3. Strehlov, Richard A; Wright, Sue Ellen, eds. (1993). Standardizing Terminology for Better Communication: Practice, Applied Theory, and Results. Vol. 1166. ASTM. pp. 336–337. ISBN   0-8031-1493-1.
4. Brewer's Dictionary of Phrase & Fable . New York: Harper & Brother Publishers. p. 786.
5. "A Glossary of Terms Used in Connection with Billiards". Billiard Monthly. English Amateur Billiards Association. February 1912. Archived from the original on March 3, 2022. American Tournament: A tournament in which each player must meet in turn every other player.
6. Allied. "American tournament". Chambers 21st Century Dictionary. Allied Publishers. p. 38. ISBN   978-0550106254 . Retrieved August 1, 2012.
7. Mead, Shepherd (1977). How to succeed in tennis without really trying: the easy tennismanship way to do all the things no tennis pro can teach you. McKay. p. 130. ISBN   9780679507499 . Retrieved August 1, 2012.
8. "An Introduction to USCF-Rated Tournaments" (PDF). The United States Chess Federation. February 23, 2006.
9. "Eight Olympic badminton players disqualified for 'throwing games'". The Guardian . August 1, 2012. Retrieved August 1, 2012.
10. "UC Berkeley Quiz Bowl: How To Make Schedules". www.ocf.berkeley.edu.
11. Dinitz, Jeff (November 13, 2004). "Designing Schedules for Leagues and Tournaments" (PDF). Home Page for Jeff Dinitz. Mount Saint Mary College: GRAPH THEORY DAY 48.
12. Le livre de l'arbitre : édition 2008 (PDF) (in French). Fédération Française des Échecs. 2008. p. 56. ISBN   978-2-915853-01-8.
13. Suksompong, Warut (2016). "Scheduling asynchronous round-robin tournaments". Operations Research Letters. 44 (1): 96–100. arXiv:. doi:10.1016/j.orl.2015.12.008. S2CID   4931332.
14. Table de Berger (in French), examples of round robin schedules up to 30 participants.
15. "C. General Rules and Technical Recommendations for Tournaments / 05. General Regulations for Competitions / General Regulations for Competitions. Annex 1: Details of Berger Table /". FIDE Handbook. FIDE. (contents page)
16. Berger, Johann (1893). Schach-Jahrbuch für 1892/93 (in German). Leipzig. pp. 26–31. OCLC   651254787.
17. Berger, Johann (1899). Schach-Jahrbuch für 1899/1900 : Fortsetzung des Schach-Jahrbuches für 1892/93 (in German). Leipzig. pp. 21–27. OCLC   651254792.
18. Richard Schurig (in French)
19. Schurig, Richard (1886). "Die Paarung der Theilnehmer eines Turniers". Deutsche Schachzeitung (in German). 41: 134–137. OCLC   556959107.
20. Lucas, Edouard (1883). "Les jeux de demoiselles". Récréations Mathématiques (in French). Paris: Gauthier-Villars. pp. 161–197.
21. Ahrens, Wilhelm (1901). "Anordnungs Probleme, Aufgabe 2". Mathematische Unterhaltungen und Spiele (in German). Leipzig: B. G. Teubner. ark:/13960/t2w37mv93.


text:
# What Do You Prefer? Using Preferences to Enhance Learning Technology

Philipp Kärger
Daniel Olmedilla
Fabian Abel
Eelco Herder
Wolf Siberski

Pages: pp. 20-33

Abstract—While the growing number of learning resources increases the choice for learners on how, what, and when to learn, it also makes it more and more difficult to find the learning resources that best match the learners' preferences and needs. The same applies to learning systems that aim to adapt or recommend suitable courses and learning resources according to the learner's wishes and requirements. Improved representations for the learner's preferences as well as improved search capabilities that take these preferences into account leverage these issues. In this paper, we propose an approach for selecting optimal learning resources based on preference-enabled queries. A preference-enabled query does not only allow for hard constraints (like "return lectures about Mathematics") but also for soft constraints (such as "I prefer a course on Monday, but Tuesday is also fine") and therefore allows for a more fine-grained representation of the learner's requirements, interests, and wishes. We show how to exploit the representation of the learner's wishes and interests with preferences and how to use preferences in order to find optimal learning resources. We present the Personal Preference Search Service (PPSS), which offers significantly enhanced search capabilities for learning resources by taking the learner's detailed preferences into account.

Index Terms—Preference, learning resource, metadata, personalization.

## Introduction

Personalization of online learning has been a hot issue in the elearning community since the 1990s. By making use of the learners' individual goals, preferences, interests, and knowledge, the interaction with the students can be adapted to their individual needs. Personalization can serve several goals, including tailoring of information presentation and helping learners find information by support for browsing and search [ 1]. In particular, the latter goal has become very relevant, now that learning has become a lifelong activity—in our knowledge-based society, workers need to continuously increase their knowledge and competences to keep up to date [ 2].

The community of lifelong learners is varied, as is the variety of learning activities that are offered—ranging from targeted group-based courses to self-organized home-based learning making use of online material. These courses might target students with specific cognitive abilities and learning styles [ 3]. Moreover, due to other obligations—professional and personal—learners may have specific constraints with respect to study load, location, and the time of course delivery. It is a known fact that learners may have a lot of different preferences of all these kinds [ 4] and it is a challenge to consider all these particularities in the personalization process.

For this reason, we present a technique based on Preference Handling for representing the learner's preferences and exploit this representation for selecting learning resources that best match these preferences. This technique is not only relevant during the process of searching for learning resources but also for the adaptation of course delivery to the goals, preferences, interests, and knowledge that are stated in the form of preferences and stored in the learner model.

Search capabilities in educational repositories and networks have been improved in recent years by the introduction of personalization and semantic-based queries. These techniques are typically realized by extending the query with hard constraints, which are either stored in the learner model or manually specified by the learner during the search process. These hard constraints represent the user's wishes, that is, conditions that should be fulfilled. But, a closer look reveals that in most cases the learner's constraints are not hard constraints. Typically, a user may want to express that she wants "courses that are in English, but otherwise German would also suffice, and that courses preferably should be given on Monday rather than Tuesday or Friday." The words "preferably," "otherwise," and "rather than" indicate soft constraints using which a user specifies what she prefers, in other words her preferences. These preferences represent a list of alternatives that can be used to filter out suboptimal, nonrelevant results, and let the learner concentrate on the most suitable alternatives. For example, if two courses are found, both of them on Monday, and one of the courses is in English and the other is in German, intuitively the latter can be discarded, since given the same (or less preferred) conditions, the user prefers English over German. This way, only the most optimal results according to the user's preferences are returned. This improves the satisfaction of the users and reduces the time they must spend in order to scan large query result sets that also contain nonpreferred (suboptimal) options.

It is important to note that the term user preferences has been extensively used in the field of user modeling [ 5] and adaptive hypermedia [ 3], [ 6]. Typically, these user preferences are a set of properties that specify the learners' goals, interests, and needs (and which are added in the queries as hard constraints or used to compute rankings). By contrast, our method is more expressive: it allows these learner properties to be modeled as soft constraints and allows users to indicate which properties they prefer to another by allowing for a preference order.

This paper describes how preferences can be used to create a fine-grained model of the learner's needs, which represents more accurately their wishes and interests. It shows how preference-based queries can be used in order to improve the selection of learning resources. Further, we show how to efficiently retrieve learning resources that best match the user's preferences, while discarding suboptimal solutions. In [ 7], we provided a first idea on how to use preferences for searching learning resources. In this paper, we base our elaborations on [ 7] and further refine it by allowing for more expressive preference compositions and a more flexible and powerful approach for expressing partial orders. In particular, this paper adds the following contributions to [ 7]

• support for preference compositions in order to be able to combine two types of multidimenional compositions (lexicographic and Pareto);
• support for a more flexible and powerful specification of partial orders in the queries, by including a representation of placeholders in its syntax and evaluation semantics;
• development and integration of the aforementioned extensions in our implementation; and
• provision of more (and more detailed) definitions, descriptions, examples, and so forth.

This paper is organized as follows: In Section 2, we motivate our approach by a running scenario. Details about preferences, theoretical background, and the use of preferences in query processing are presented in Section 3. Section 4 shows how preferences support the selection of learning resources by applying the preference theory to our running scenario. In Section 5, we describe our prototype implementation and a first experimental evaluation. Finally, Section 6 compares our approach with existing initiatives, and Section 7 concludes this paper.

## Motivation Scenario

In the following, we picture a scenario to motivate our approach, which will be used later in this paper to demonstrate how preference-based search works and how preferences support learners in finding suitable courses. We will use this example throughout this paper for illustrating our approach.

Bob has just bought his first digital camera and now he is looking for a course about photography. He is not sure what different kinds of courses are available, but he has certain ideas of his likes and dislikes. Fig. 1 summarizes the preferences mentioned in the scenario.

Figure    Fig. 1. Bob's preferences, represented as Hasse diagrams of the preference relations. Each preference is represented by a directed connected graph. The direction of an edge represents that the node at the beginning is preferred to the node the edge points to. Nonconnected nodes represent indifferent alternative values.

1. For instance, Bob prefers a classroom course, in which he can learn with and get inspired by fellow learners, above a rather solitary distance learning course.
2. Bob is neither a professional in photography nor does he plan to become one, so he does not insist on gaining a certificate. But should there be a course that does provide a certificate at the same or better conditions (price, and so forth), he would prefer to take the one with the certificate.
3. However, he definitely would not like to have to pass an exam in order to get the certificate.
4. Bob believes that he will enjoy doing image processing with his computer. Hence, he also wants a course that comprises some kind of homework.
5. Bob wants a course offered in the evening. He would prefer a course on one of the working days, except on Monday when he has a weekly appointment with a friend for jogging. If needed, he could reschedule this appointment, though. He also likes to keep the Friday evening free for meeting with his chess club. If there are no courses available during the week, he might consider a course on Saturday or Sunday.
6. Bob would like the course to take place once a week. A course with two meetings per week, or one meeting every two weeks, would be fine as well. But, he absolutely dislikes weekend block courses, as he is not willing to stay away from home for a longer time over the weekend.
7. However, since he just got his new camera, he wants the course to start as soon as possible as not to lose any time.
8. As Bob is an avid cyclist, he does not mind riding up to 10 km to the course, provided that he can follow a scenic track with cycle lanes. If the course takes place in the south of the city center, he can take the way through the park; otherwise, he has to struggle through busy traffic.
9. Concerning financial issues, Bob also has some constraints: he is not willing to pay more than 100 euros for the course.

This combination of different interests and likes and dislikes is typical for complex domains such as courses: more often than not, people are not able to exactly specify their wishes in terms of hard constraints. The expressions used in our scenario show that Bob has merely an idea of what he is looking for. These kind of soft constraints are useful for users to define their expectations, in particular when they do not yet know what exactly they are looking for. Although this set of hard and soft constraints is a common way of how a user describes her wishes, it is so far not possible to specify such complex search requests with current search interfaces. Moreover, from a learner modeling point of view, it would be much more accurate to allow for these more vague statements about the user's wishes.

A learning platform that provides extended search capabilities to take into account all the known or explicitly provided hard and soft constraints is desirable. With such a platform, Bob would be able to specify some of his ideas of the desired course: it should deal with digital photography, it does not need to provide a certificate, it should start immediately, and so forth. Additionally, the system exploits its knowledge about Bob, such as his age and which languages he prefers beyond his native language. It also uses Bob's preferences gained from his past interactions, such as his fondness of meeting people, the location where he lives, and his regular meeting on Fridays and Mondays. By taking all these constraints into account, the system would be able to perform a query comprising most of the particularities in Bob's idea of a course. Probably, there will be no course that matches all of the constraints, but the system will provide Bob with a small result set, containing the courses with—according to his preferences—the lowest deviation from the given preferences and therefore from his ideal course.

## Preferences

Preferences are a way to model the user's needs, wishes, and expectations. Beyond the specification of a preferred, single desired value or behavior (such as "I like green."), the notion of preference that we suggest allows for alternatives (such as "If possible, I prefer green. Otherwise, yellow is fine as well."). Therefore, preferences provide means for expressing soft constraints instead of hard constraints. These preference orders, which are built up by assembling several preferred alternatives, comprise precise knowledge about what a user would like to get. But, the term "if possible, $\ldots$ " already suggests that precise and meaningful semantics of these preference orders has to be provided: The soft constraints have to be relaxed step by step until the most preferred object, or rather the most preferred combination of attributes, is found. In this section, we will first outline some properties and different kinds of preferences. Then, we will introduce the theory of preferences and show how their semantics deliver the desired behavior of a constraint relaxation.

### 3.1 Properties of Preferences

In this section, we introduce some basic properties and requirements that a preference model may have. We will revisit these properties throughout this paper.

Total versus partial orders. It may be difficult for Bob to define a total order preference for all the attributes of his desired course. It is a time-consuming process and it may well be the case that he is indifferent for some attribute. Partial order preferences (such as Bob's preference concerning the day of the week) allow for indifferences and are more general than total order preferences (such as the one concerning a course's certificate). In Fig. 1, we depicted the partial orders of Bob's preferences in the form of Hasse diagrams [ 8].

Conditional preferences. A preference may vary depending on some attributes. For example, Bob's preference concerning the location of the course does not only include the length of his bike ride; in addition, it includes preferences on the direction of the ride as well (in this case, whether it is north or south).

Quantitative versus qualitative preferences. In a quantitative (weighted or numerical) model of the user's preferences, the value of to what extent a user prefers one alternative over another is explicitly given. In our scenario, none of the preferences that Bob provided were quantitative. From a usability point of view, it is not desirable that a user has to specify a numerical representation for each attribute and each attribute's value to indicate how much a certain alternative is preferred. Moreover, in most cases, the composition of several attributes (such as Bob's desired location of the course together with the desired price) is an arbitrary numerical function, in which the quantitative preference definitions of the involved attributes need to be normalized. Therefore, we argue that, in general, qualitative (i.e., nonweighted) preferences are more suitable for a user, and in this work, we will concentrate on qualitative preferences.

Prioritized preferences. If the user's preference includes more than one attribute, the user may consider one attribute's preference more important than another. For example, Bob's preference concerning an exam is more important to him than the one about the certificate. Therefore, it is desirable to allow for prioritized preferences.

Default and learned preferences. It is not always needed that users define their preferences manually. Some preferences might be automatically learned from the user's behavior. As an example, if the learner's schedule is already tight on Friday, other days of the week may be more suitable. Or if the student's results in oral exams have not been as good as the results for written courses, courses with written exams may be automatically preferred by the system. Moreover, one could consider default preferences that apply to learners that fit into a certain group profile [ 9] or even general default preferences, such as preference for the cheapest price, courses with certification, the lowest distance, the highest reputation, and so forth.

Hard and soft constraints. As we already pointed out, preferences model constraints that a user may allow to be relaxed, if needed. Although we focus our work on these kinds of soft constraints, we want to point out that hard constraints may still be part of a user profile. For example, Bob's constraint that a course should not be more expensive than 100 euros is a hard constraint. Hard constraints are part of most existing user models; they are complementary to the theory we present and supported in our implementation.

### 3.2 Formal Model of Preferences

In order to model the kinds of hard and soft constraints that Bob is able to specify his preferences with, we will now introduce the notion of Preferences and Preference-based Queries. As we have seen in the scenario, we aim for advanced search for suitable courses. A query model in which users can only specify hard constraints on course characteristics does not support this kind of search. The notion of preference-based querying in the context of databases has been formalized independently by Kießling [ 10] and Chomicki [ 11]. To describe user preferences in a way that is exploitable for querying, we rely on the preference-based query formalization as proposed by Chomicki [ 11]. In this extension to relational algebra, preferences are expressed as binary relations over a set of objects $O$ .

Definition 1 (object-level preference relation).
Let $A$ be the set of available attributes of the elements in $O$ , and $U_{i}$ the respective set of possible values of an attribute $a_{i}$ . Then, any binary relation $\succ$ that is a subset of $(U_{1} \times \cdots \times U_{n}) \times (U_{1} \times \cdots \times U_{n})$ is an object-level preference relation over the object set $O$ .

An object-level preference provides the means to compare two objects and to decide which one is preferred. But, typically, the user's preferences are not directly defined on object level. Therefore, although an object-level preference allows for comparison of objects, it is not the right means to express a preference, as statements about which object is preferred to another are not explicitly given by the user. In our scenario, Bob does not provide an object-level preference: he does not state relationships between whole objects like "I prefer course A, which is held on Monday and costs 72 euros and provides a certificate and so on, to a course B, which is held on Tuesday and costs 44 euros and also provides a certificate and so on." In contrast, Bob's preferences are defined on attribute level: on the attribute values of each object attribute and not on the objects themselves. For example, for the attribute "day of the week," Bob states that he prefers the value Tuesday to the value Monday. Therefore, preferences are rather stated with respect to the attribute values of each single attribute. Consequently, certain values are preferred over others, thus forming a partial order of attribute values.

Definition 2 (attribute-level preference relation).
Let $A$ be the set of available attributes of the elements in $O$ and $S = \{a_{1}, \ldots, a_{n}\} \subset A$ a nonempty set of attributes with $V = \bigcup U_{i}$ as the union of the attribute domains of possible values. The attribute-level relation $\succ_{S}$ , which is a subset of $V \times V$ , is an attribute-level preference relation over the value set of the attributes in $S$ .
If $|S| = 1$ , we call $\succ_{S}$ a single-attribute preference relation. Otherwise, it is called a multiattribute preference relation.
Example 1.

Bob's preference concerning the desired location of the course is a multiattribute preference: it spans over the attributes direction and distance. Multiattribute preferences provide means to model conditional preferences. Bob's preference for a longer bike ride depends on the direction of the ride. This conditional preference can be modeled by specifying a relation spanning over these two attributes.

For a more convenient notation, we introduce an additional relation to denote indifference (or incomparability) between two objects.

Definition 3 (indifference relation).
Given an attribute-level preference relation $\succ_{S}\!$ and two objects $x$ and $y$ , the indifference relation $\sim_{S}$ is defined as $x \sim_{S} y \equiv\!$x \not\succ_{S} y \wedge y \not\succ_{S} x . If x either dominates y (i.e., x \succ_{S} y holds) or both are indifferent (i.e., x \sim_{S} y holds), we write x \succeq_{S} y \equiv\!$x \succ_{S} y \vee x \sim_{S}y$ .

Based on these attribute-level preference relations that are provided by the user, one is not yet able to compare objects: what if an object is better in terms of one attribute but worse in terms of another attribute? If Bob states that Tuesday is preferred to Monday and that cheaper courses are preferred, how can one compare a more expensive course on Tuesday with a cheaper course on Monday? In other words, we need a way to combine all the attribute-level preferences in order to build up an object-level preference relation that allows us to compare objects.

This combination is provided by a so-called composition of attribute-level preferences.

Unidimensional composition applies if preference relations over the same attribute have to be combined. This does not apply to our scenario and we refer the reader to [ 11] for more details.

Multidimensional composition applies if attribute preference relations have to be composed that are stated over different attributes or attribute sets.

Multidimensional composition is needed when the relations are imposed over different sets of attributes, in order to expose a new preference relation over the Cartesian product of the sets of attributes. For a composed preference, the combined preference relations are called dimensions of the composed preference relation. According to [ 11], two multidimensional compositions are common:

• Lexicographic composition combines two dimensions by considering one as more important than the other.
• Pareto composition allows for combining two preference relations without imposing a hierarchy on the dimensions—all dimensions are considered to be equal.

Lexicographic composition. A lexicographic composition of two preference relations is based on the assumption that one relation can be considered more important than the other: there is a total ordering between the two attributes. Thus, objects are generally ordered according to the more important attribute and only in case of ties the less important attribute is considered to decide the order.

Definition 4 (lexicographic composition).
The lexicographic composition $\succ_{L}$ of the preference relations $\succ_{1}, \ldots, \succ_{n}$ is defined as
$x \succ_{L} y \Leftrightarrow \exists k : (y \succ_{k} x \wedge \forall i < k: x \sim_{i}y).$

The comparison of objects according to a lexicographic composition is similar to the definition of the word order in a lexicon: words starting with letters ranked higher in the alphabet are put before the ones starting with lower ranked letters. Only in case both first letters are equal, the second letter is considered for deciding which word is listed first, and so on. Applied to our scenario, we may order Bob's preference concerning the exam and his preference concerning the certificate in a lexicographic manner: any course without an exam is preferred to a course requiring an exam independent of the certificate dimension. Only in case two courses show equal values in terms of the exam (either both require one or none), they are compared according to the certificate dimension.

In most of the cases, a user considers the dimensions of her preferences equally important. For example, in our scenario, most of Bob's preference dimensions play equally important roles for the comparison of courses. Therefore, the fair principle of Pareto domination has been introduced in order to combine several preference dimensions.

Pareto composition. Pareto composition yields a new preference relation following the fair principle of Pareto domination. An object $x$ is said to Pareto dominate an object $y$ iff $x$ is better than $y$ in terms of at least one of the preference relations and equal or better in terms of all other preference relations, or as more formally given in Definition 5.

Definition 5 (Pareto composition).
Given the preference relations $\succ_{1}, \ldots, \succ_{n}$ over the sets of attributes $A_{1}, \ldots, A_{n}$ , the Pareto composition $\succ_{P}$ of $\succ_{1}, \ldots, \succ_{n}$ is defined as $x \succ_{P} y \Leftrightarrow (\forall i: x \succeq_{i} y) \wedge \exists j: x \succ_{j} y$ .
We say an object $x$Pareto dominates another object $y$ , iff $x \succ_{p} y$ .

This definition follows the principle of weak Pareto dominance (as used, for example, in [ 11] and [ 12]), which implies that incomparability in one preference dimension does not yield incomparability on the object level, because $\succeq_{i}$ contains all the incomparable attribute values for preference dimension $i$ . In contrast to the principle of weak Pareto dominance, some approaches follow the strong Pareto dominance (such as, for example, [ 10] and [ 13]), where an incomparability on the attribute level always implies incomparability on the object level: as soon as two objects are incomparable in terms of a single attribute, they are both incomparable. The choice between weak and strong Pareto dominance for the composition of preference relations makes a difference only for partial order attribute-level preferences. For the composition of total order preference relations, there is no difference, as for a total order preference relation $\succ_{i}$ , the corresponding indifference relation $\sim_{i}$ is empty.

Applied to our scenario, the principle of Pareto composition lets a low-cost course $x$ dominate an expensive course $y$ iff in terms of all other preference relations (as imposed on the attributes location, duration, and so forth) $x$ is at least equally good as $y$ . This principle has been exploited in the area of database systems for the so-called skylining [ 14], [ 15], [ 16]. In skyline queries, each single attribute is viewed as an independent, nonweighted query dimension. Best matches for skyline queries are determined according to the principle of Pareto optimality: each object that is not dominated by any other object is considered as optimal and as a best match. All these nondominated objects are called the skyline of the query.

Now, we have to apply the notion of preference, as developed so far, in order to select from the set of all available objects the ones that are optimal according to a given preference. This is catered by the so-called winnow operator, which selects all nondominated (preferred) objects from a set of solutions given an object-level preference relation.

Definition 6 (winnow operator $\omega$ ).
Given a set of objects $O$ and a preference relation $\succ\!$ , the winnow operator $\omega$ is defined as $\omega(O)$ , in the following way:
$\omega(O) = \{x \in O| \neg \exists x^{\prime} \in O:\;x^{\prime} \succ x\}.$

### 3.3 Querying with Preferences

As pointed out earlier in this paper, exact match semantics of traditional databases do not sufficiently fit the queries as formulated by users. On the one hand, this is because too specific query predicates often lead to empty result sets. For example, if Bob had specified only his most preferred attributes as hard constraints (i.e., connected by a logical and), the system would most likely come up with an empty result set, because no learning object fulfills all of Bob's most desired features. We refer to this query as a conjunctive query. On the other hand, too many unspecific hard constraints may yield huge numbers of results. In Bob's case, that would mean that all the properties that he may think of are put into the query and connected with a logical or; in this case, many learning objects (including the most preferred and least preferred) will be provided to Bob. We will refer to this kind of queries as disjunctive queries. Both approaches lead to the fact that, in practice, users have to modify query constraints in a trial-and-error fashion until they get a result set of the right size.

In contrast to the exact match paradigm, the notion of best match semantics fits much better to typical user's search requests. In this case, the goal is to compute a set of results that fulfill the query's constraints as good as possible. These constraints are often referred to as soft constraints. Best match queries automatically adapt the specificity of a search to the available objects. Our proposed solution to achieve best matches is to exploit preference orders for querying. Preference-enabled queries are based on the observation that expressions of the form "I like A more than B" are easily stated by users when asked for their wishes. Therefore, it should be optimal if a query engine can derive best matches directly from such preference expressions instead of aiming only at exact matches. Besides preference-based queries, several other approaches to retrieve best matches have been proposed, such as query relaxation and ${\rm top}\hbox{-}k$ retrieval.

Query relaxation. This family of algorithms does not introduce new query language constructs (except sometimes an operator to distinguish between hard and soft constraints) but continues to loosen and/or remove query constraints until at least some results can be returned to the user [ 17], [ 18]. The advantage of this approach is that the queries themselves stay simple; only the evaluation algorithm is changed. Various relaxation algorithms have been proposed, including [ 19], [ 20], and [ 21]. At the same time, the main advantage of query relaxation is also its main weakness: the user has no control over the relaxation process. In the worst case, the relaxation algorithm will remove the important constraints early, while keeping the less relevant. For example, Bob might end up with a certified course that starts three months later, because the algorithm relaxed on the starting date instead of on the less important certification constraint.

${\rm Top}\hbox{-}k$queries. Inspired by information retrieval algorithms for document search, query techniques that rank results by their relevance for the user have been introduced for databases as well. Instead of expressing constraints on the answers, the query includes a scoring function that assigns a relevance score to each potential answer [ 22]. The scoring function of a query is usually the weighted sum of individual scores for each relevant attribute. A formal extension of relational algebra by a specific ${\rm top}\hbox{-}k$ operator has been proposed in [ 23]. Algorithms and systems for efficient computation of ${\rm top}\hbox{-}k$ queries have been developed [ 24], [ 25], [ 26]. The main disadvantage of the ${\rm top}\hbox{-}k$ paradigm is that in many cases it is very difficult for the user to specify the right scoring function, as this requires the user to put her wishes in a numeric relation to enable something that might be considered comparing apples with oranges. For example, it is virtually impossible for Bob to tell how many additional miles he would be willing to ride for a course starting one week earlier. But, these are exactly the trade-offs that have to be specified as weights within the scoring function.

Preference-enabled queries. In contrast to these two approaches, preference-enabled queries do not require ranking. All objects contained in the result set are optimal according to the given preference orders. Assuming a ranking score function based on user preferences, any object that would be ranked lower (for example, according to some of the measurements in the approaches of ${\rm top}\hbox{-}k$ or query relaxation) would not be optimal anymore: it represents a worse alternative than the objects with a higher ranking. For this reason, any result set of a preference-enabled query is unordered: all results are equally relevant. To provide more effective search capabilities for preferences, query languages like SQL over relational databases [ 27] and SPARQL over RDF graphs [ 28] have been extended to facilitate preference-based retrieval algorithms.

In Section 4, we show how preference expressions together with preference-enabled queries are applied to effectively search for learning resources.

## Preferenceson Learning Resources

There are many ways in which online learning can be personalized to the learner. Preference-based reasoning provides adaptive educational engines with powerful means for selecting suitable learning resources, other learners (e.g., for collaboration), or even a suitable adaptive instructional strategy. In this section, we will show how preference handling can be used to match the complexity and variety of the learner's needs and the plethora of possibilities—be it learning material or learning strategies—offered by current adaptive learning systems.

Adaptive learning is a prominent pedagogical approach where each individual learner is provided with a set of learning activities and resources that fits the individuals' learner preferences including portfolio, background knowledge, educational needs (such as learning styles), and situational circumstances of the learner. Level B of the IMS Learning Design Specification [ 29] provides means for creating alternative routes that address these individual differences. Similarly, popular adaptive hypermedia systems, such as AHA! and MOT provide rules that allow for addressing individual learning styles [ 30]. In contrast to MOT, in which authors explicitly select an adaptive instructional strategy, the AHA! system's adaptations are based on outcomes of the adaptive hypermedia's engine reasoning system.

Learning styles, or rather cognitive styles, have been a driving factor in the design of adaptive educational hypermedia. In particular, the distinction between field-dependent and field-independent learners has received a great deal of attention. Whereas field-dependent learners take a more passive approach and approach the material more holistically, field-independent learners tend to be more serialistic in their approach to learning, reusing strategies, and tools that they have used before. Concretely, this means that field-independent learners prefer free navigation tools—such as site search, rich interlinking and references to background articles, and social filtering, but that field-dependent learners need more structured material, as not to get "lost" [ 31]. Other frequently addressed learning styles include example-oriented versus activity-oriented learners and verbalizers versus visualizers [ 30].

It may be clear that these various kinds of learning styles, as well as individual preferences including background knowledge and situational circumstances can be addressed by a variety of instructional strategies, which eventually result in one or more adaptations. However, there is currently only partial knowledge on which adaptations are useful for which learning style. One could, for instance, say that for field-dependent users a fixed path to follow is preferable to a highly interlinked learning resource. However, should the author of a learning resource have coupled the fixed-path condition with more examples and less hands-on material, this might not be the best choice for the field-dependent learner who is more activity-oriented.

Classical systems, such as AHA!, generate personalized paths that are based on the learner model as well as explicitly indicated preferences. However, if the system has to deal with conflicting preferences, treating these preferences as hard constraints might lead to situations in which no optimal path can be found. A preference-based model would allow for selecting the most appropriate candidate paths among the available ones, which caters as many of the preferences as can possibly be catered.

Preferences provide a framework to model all the specific properties, wishes, interests, and needs of a learner. They allow for a trade-off between several dimensions of the learning style's characteristics, which would solve the problem of the fixed-path condition. However, the motivation of a learner highly depends on the fact that she is provided with a material suiting her needs. As we have shown, representing these needs via preferences rather than via fixed single-value hard constraints allows any educational system to provide a material that may not be the overall best choice for all users but which is at least the best selection (among the available material) for the learner.

In Section 4.1, we will bring together the more informal needs and wishes of Bob presented in the scenario in Section 2 and the formal model of preferences provided in Section 3.

### 4.1 Motivation Scenario Revisited

In this section, we formally specify Bob's hard and soft constraints from our scenario in Section 2. For each attribute that Bob provides a preference upon, an attribute-level preference relation is imposed. Some preference relations can be expressed over a single attribute (such as Bob's preferences concerning the weekday of the course) and are therefore modeled as single-attribute preferences. Bob's preference relation about the venue of the course depends on two attributes: the direction (north or south) and the distance from his home. Therefore, this conditional preference is modeled as a multiattribute preference. Accordingly, we can formally define Bob's preferences. For example, the preference relation over the attribute weekday can be represented as

\eqalign{&\succ_{weekday} \;= \big\{(Tuesday,Monday),\;(Wednesday,Monday),\cr &{\kern65pt}(Thursday,Monday),\ldots\big\}}

and his multiattribute preference over the venue can be defined as follows:

\eqalign{\succ_{venue} \;= &\,\big\{(direction = south \wedge dist. = 10\;{\rm km},\cr&\quad direction = south\wedge dist. < 10\;{\rm km}), \ldots ,\cr&\quad(direction = north \wedge dist. = 10\;{\rm km},\cr&\qquad\qquad direction = north\wedge dist. < 10\;{\rm km})\big\}.}

In a similar way, we can define the other attribute-level preferences $\succ_{type\_of\_learning}\!$ , $\succ_{homework}\!$ , $\succ_{price}\!$ , $\succ_{certificate}\!$ , $\succ_{exam}\!$ , $\succ_{duration}\!$ , and $\succ_{start}\!$ .

See Fig. 1 in the beginning of this paper, in which the Hasse diagrams for the partial orders representing Bob's preference relations are shown. In order to select Bob's preferred courses out of all the available ones, we need an object-level preference that is a composition of all these attribute-level preferences.

From Section 3, we recall that there are two ways of combining attribute-level preferences to a single object-level preference: lexicographic composition and Pareto composition. The former applies to preference relations that are prioritized and the latter to preferences that are considered equally important.

Bob considers his preference for a course with no exam more important than the preference concerning a certificate. In any case, he prefers a course with no exam. Only if two courses bear the same attribute value in terms of exam, he would prefer the one with a certificate to a course without. Therefore, we first build up a lexicographic composition of $\succ_{exam}\!$ and $\succ_{certificate}\!$ . We denote this composed preference relation as $\succ_{L_{ex, cert}}\!$ .

As Bob considers his preferences on the remaining attributes as equally important, we build an object-level preference by Pareto composing the already composed preference $\succ_{L_{ex, cert}}\!$ with $\succ_{type\_of\_learning}\!$ , $\succ_{homework}\!$ , $\succ_{cycle}\!$ , $\succ_{price}\!$ , $\succ_{duration}\!$ , $\succ_{weekday}\!$ , and $\succ_{start}\!$ . These single preferences build a Pareto-composed preference relation $\succ_{Bob}\!$ . Given two courses $C_{1}$ and $C_{2}$ , $C_{1} \succ_{Bob} C_{2}$ holds if all attributes of $C_{1}$ are equal or better than $C_{2}$ according to the attribute's preference relations and if at least one attribute $C_{1}$ is better than (and not equal to) $C_{2}$ (see Definition 5 of the Pareto Composition).

Considering the relation $\succ_{Bob}\!$ , the optimal course would be the one that fulfills all the top values of Bob's preferences, since all others would be dominated by this relation. And obviously, he would be really happy with a regular three-month course happening once a week on Tuesday, Wednesday, or Thursday without an exam but with a certificate and all the other desired features. Unfortunately, in most of the cases, this course does not exist. However, the semantics of the two composition paradigms cater the desired soft constraint behavior: they provide the courses with an optimal trade-off between the desired and the actual features. This selection is provided by the winnow operator $\omega_{Bob}$ defined for $\succ_{Bob}$ and applied to the set $O$ containing all courses that are possibly available to Bob.

We will now show on the basis of the data set depicted in Fig. 2 that the Pareto composition $\succ_{Bob}$ provides exactly the intended best match result: the courses in the skyline or, more precisely, the courses that are not dominated by any other course. For the sake of simplicity, we omit some of the dimensions from the scenario. As delivered by the winnow operator $\omega_{Bob}$ , a course C is considered a best match according to Bob preferences, if there is no other course $C^{\prime}$ such that $C^{\prime} \succ_{Bob}$ C: there is no other course that dominates C. Given this, we can conclude that course B in Fig. 2 is not preferred and therefore irrelevant, since it is dominated by A: A is equal to B according to the dimensions price, distance, and direction. However, A is better than B according to $\succ_{weekday}\!$ (Bob prefers a course on Tuesday to a course on Monday), which lets A dominate B. Therefore, Bob will not be interested in B, as A is a better alternative. Let us have a look at A and C: A is better than C concerning $\succ_{weekday}\!$ , but in contrast, C $\succ_{venue}\!$ A holds. Given the Pareto composition of $\succ_{weekday}\!$ and $\succ_{venue}\!$ , A and C are not comparable, as none of them dominates one another. Hence, Bob is probably interested in receiving both as answers, since they are orthogonal alternatives. For attending course D, Bob has to ride to the north of the city, which he really dislikes. On the other hand, D is for free, so in exchange for accepting to ride to the north he will save money. $\succ_{Bob}\!$ ensures that this alternative will be included into the result set as well, since it is not dominated (even though it is Bob's last option in terms of $\succ_{venue}\!$ ).

Figure    Fig. 2. Some available courses for Bob. B and E are suboptimal: B for weekday and E for cost. A, C, and D are nondominated.

From the courses depicted in Fig. 2, the preference-based search with Bob's constraints, as described in the scenario, presents the courses A, C, and D. The search prunes the courses B and E. B is dominated by A, because on Monday Bob prefers not to reschedule his jogging appointment with his friend, and A is equally good as B in all other dimensions. E is dominated by D, because it is more expensive and not better in any other dimension.

In this section, we elaborated how preferences and their composition are applied to rule out suboptimal, nonpreferred objects. For a learner, this information filtering is of particular importance, as it guides a way through the growing space of possibilities of where and what to learn. In Section 5, we will show our implementation, in which we applied the preference principle to support students with the selection of courses at a university.

## Implementation

To show that preference-based search is a promising approach for managing huge data sets of learning resources, we implemented a Web service for preference-based queries over the whole database for lectures held at the University of Hannover, Hannover, Germany. The data set comprises about 10,000 lectures each with about 10 attributes. This yields an RDF graph of over 100,000 triples. In order to realize the preference-enhanced search facilities, we implemented a Web service called Personal Preference Search Service (PPSS), which is integrated into the Personal Reader Framework [ 32]. We further provide a prototypical user interface 1 to this service that allows students to specify their preferences in order to find a manageable set of learning resources. In this section, we will first provide some insights in a preference-enabled query language for RDF data. Then, we will give a short description of the Personal Reader Framework and describe the architecture of our service and its integration into the framework. Finally, we provide an experiment that shows the percentage of objects ruled out for given queries.

### 5.1 A Preference-Enabled Query Language

Querying with preferences in the context of the Semantic Web is a relatively new field. In [ 28], we made a first contribution by establishing an extension for the RDF query language SPARQL empowered with an implementation based on the ARQ SPARQL Processor [ 33], which is part of the Jena Semantic Web Framework [ 34].

To specify soft constraints in the form of preferences, the SPARQL language has been extended by the PREFERRING-construct. Fig. 3 shows the query for our scenario (for the sake of readability, we left out some of the preference dimensions). Beyond the initial hard constraint construct FILTER (see line 11 in Fig. 3), it is now possible to define soft constraints in an SPARQL query. The extension of SPARQL comprises two atomic preference expressions and two facilities for combining preference dimensions. For atomic preferences, the following expression types are offered:

Figure    Fig. 3. Preference-extended SPARQL query for Bob's desired course.

• Boolean preferences (lines 14, 22, 24, and 28 in Fig. 3) are specified by a Boolean condition. Results that satisfy this condition are preferred over results that do not satisfy it.
• Scoring preferences are specified by the term HIGHEST (respectively LOWEST), followed by a numeric expression. Results for which this expression leads to a higher value are preferred over results with a lower value (and vice versa). Two types of scoring preferences are provided: either they are defined over an SPARQL domain with a total ordering (lines 26 and 30) or they are defined over a partial order (given by the user in form of a set of pairs; lines 16 to 20). As the definition of a partial order over many values may be cumbersome, a placeholder, denoted by an asterisk, can be used to represent any other possible value. As an example, see line 16, in which instead of defining all the equally preferred optimal days of the week, an asterisk is introduced. This feature is particularly helpful if an attribute has a lot of possible values: omitting some values in the definition of a partial order yields an indifference for these omitted values with respect to any other value of that attribute.

These atomic preference expressions can be composed of two types of multidimensional composition (cf. Section 3):

• A Pareto-composed preference consists of two preference expressions connected by an AND. Both expressions are evaluated independently. An object is preferred if it is better in one of both preferences and at least equally good in the second one.
• In a cascading (lexicographic) preference, two preference expressions are connected by a CASCADE (lines 22 to 24): the first preference is evaluated first. Only for objects that are equally good with respect to the first preference, the second preference is considered.

### 5.2 The Personal Reader Framework

Figure    Fig. 4. The architecture of the Personal Reader Framework comprising the PPSS.

Given this setting, on the one hand, our PPSS is able to benefit from the shared user model, while, on the other hand, other services of the Personal Reader Framework will benefit from the functionality of the PPSS for their purposes. For example, the Personalization Service for Curriculum Planning [ 36] and the MyEar Music Recommender [ 35] can utilize the PPSS to offer an improved search for adequate courses and music files, respectively. The Personal Publication Reader [ 37], which allows users to browse publications within an embedded context, would be able to provide suggestions on publications that suit the user's preferences by integrating the PPSS.

### 5.3 The Personal Preference Search Services

As shown in Fig. 4, the PPSS acts as a personalization service in the Personal Reader Architecture. It comprises an AJAX-based GUI (see Fig. 5) and the PPSS Syndication Service. It also wraps the extended ARQ engine. If a query is submitted, the following steps are performed:

Figure    Fig. 5. The prototypical user interface of the PPSS allowing for the specification of preference orders.

1. An RDF description of the preferences is created out of the user's input.
2. This RDF description is passed to the PPSS connected via the connector service. The PPSS creates an SPARQL query out of the RDF description.
3. The extended ARQ engine processes the query.
4. The PPSS generates an RDF description of the result set and passes it to the user interface.
5. The results are formatted and presented to the user.

These functionalities of the PPSS are separated. This fact, together with the architecture of the Personal Reader and the flexibility of the user interface, enables the system to query any RDF-based data set of learning resources with arbitrary attributes of the objects in the data set.

The prototypical user interface (shown in Fig. 5) allows the user to specify her preferences for each attribute. By clicking on the more button, additional alternative values can be provided. For each attribute, the asterisk placeholder can be introduced by selecting, for example, the entry "any other time." This user interface offers the definition of total-order, Pareto-composed, single-attribute preferences (cf. Section 3). Due to the complexity of a user interface that allows for definition of partial orders, prioritized and dependent dimensions, we currently do not allow for these kinds of preference structure, although our implementation is able to handle them.

A definition of a preference order with only one element (such as the course topic keyword in Fig. 5) is considered a hard constraint and is added to the SPARQL query as part of the FILTER-construct. This allows the user not only to specify soft constraints in a form of a preference order but also to specify hard constraints, for example that the course should have a topic containing "Mathematics."

### 5.4 Experiment

We have performed a number of experiments with the lecture database of the learning management system of the University of Hannover. This system currently comprises 9,829 lectures. In the following example, we provide a preference-enabled query and show how preference-enabled queries optimize the result set and provides the desired learning resources, without pruning relevant results or returning nonrelevant objects:

Return courses about mathematics. I am interested in readings rather than in tutorials or seminars. If possible, I would like to attend a 90 minutes lecture. Sixty minutes are also fine, but 120 minutes lectures are too long. I like to have the lecture in the morning rather than in the afternoon. Due to the lunch break, noon is not possible for me. I don't want to have a lecture on Friday. Thursday would be my first choice, followed by Tuesday. Wednesday would also be acceptable, and would actually be better than Monday, as often I am still at my parents until Monday afternoon.

Fig. 5 shows how this query is specified in the user interface. The SPARQL query created to search for the desired course is shown in Fig. 6. For each attribute, a preference relation is imposed (lines 22, 26, 32, and 41) and all the relations are Pareto composed via the AND keyword. Issuing this query to the database of the University of Hannover yields four results, as shown in the table in Fig. 7. Obviously, none of the returned courses matches all of the desired attributes. The first lecture is held too late during the day, takes place on Tuesday, and it is not a reading either; the second lecture is too long, and so on. Mind that the order in the table does not correspond to a ranking: all six results are equally relevant. However, concerning all the 64 courses about Mathematics that are contained in the database, these four results are optimal: the remaining 58 courses are worse in terms of at least one preference relation.

Figure    Fig. 6. Preference-extended SPARQL query for preferred courses at the University of Hannover.

Figure    Fig. 7. The four optimal courses at the University of Hannover retrieved via a preference-enabled query to the course repository.

In Section 3.3, we already pointed out that it is difficult to express soft constraints in a best match search approach that does not allow for preferences. In this section, we show by means of the given search request that the two alternative approaches, conjunctive and disjunctive queries, do not provide a satisfactory search result.

Conjunctive. For this approximation to preferences, the user would need to conjunctively connect all preferred attributes and to execute several queries by going step by step down in the preference order, by applying a trial and error strategy. This way of querying is cumbersome and, moreover, returns too few and—in most of the cases—no results. After some queries with no results, the user gets frustrated. Even if some results are returned, the user needs to create queries with all different alternatives in order to be able to select the best match. In our current example, the conjunctive query yields an empty result, as none of the courses in Fig. 7 has all the most preferred properties.

Disjunctive. The second approach is to disjunctively put all the possible desired outcomes into a single query. This query usually returns a large result set that does contain the desired optimal courses but also a lot of nonoptimal results that are dominated by better ones. In our example, this query yields 25 courses (see an excerpt of the results in Fig. 8), including courses with suboptimal attribute combinations. For instance, the lecture "Mathematics (Engineers)," offered by the Faculty for Algebra, is suitable but obviously worse than "Mathematics (Geography)," offered by the Faculty for Analysis (third item in Fig. 7). The latter dominates the former, as it is a 90-minutes lecture, which is preferred to a 120-minutes lecture. For this reason, it is not worthwhile to include the longer lecture into the result set. By following this procedure, filtering out nonoptimal results, the PPSS reduces the number of results from 25 to 4.

Figure    Fig. 8. The 25 courses at the University of Hannover that match the disjunctive query. The four optimal courses included.

Both the conjunctive and the disjunctive approaches are not satisfactory. The former comes up with no results and the latter puts the burden on the user with many nonrelevant courses. Therefore, our preference approach solves this problem by returning to the user not too many results (leaving optimal ones out) and not too few (including suboptimal ones), but returning exactly the ones that are optimal according to the user's preferences given in the query.

## Related Work

To the best of our knowledge, using preference handling to support the learning process has not been considered thus far. Personalization that is based on single-value preferences (preferences not providing an order but a single value) has been subject of manifold research. For some examples, we refer the reader to [ 3], [ 5], and [ 38]. The work described in this paper focuses explicitly on how learner preferences look like and exploits the structure of the user-given alternatives.

Some research has been carried out in area of quantitative preferences. In [ 39], a framework for expressing and combining quantitative preferences is described. Two other quantitative approaches are already mentioned in Section 3.3, such as query relaxation and ${\rm top}\hbox{-}k$ . The main drawback of any quantitative solution is that the user is forced to either define a utility function (or a relaxation function) or to use a predefined one. Both alternatives do not sufficiently fit a learning scenario in which users are not willing to specify detailed numeric functions. Furthermore, as learners have different preferences, learning styles, and constraints, predefine solutions do not fit as well.

Preference-based search in the domain of digital libraries is provided in [ 40]. In this work, preferences are defined for one single dimension: over keywords of the desired object. Due to this fact, the preferences are used for sorting the results and cannot be exploited to filter irrelevant objects. In [ 41], different approaches for catalog search are compared. It was found that the preference-based alternative is the most promising. However, the opportunities for defining preferences in the search form of the compared preference approach, as presented in [ 41], are limited to the identification and prioritization of dimensions but do not allow for preferences between the values of the dimensions. This is crucial for complex domains, such as learning resources where most of the dimensions are discrete.

## Conclusionsand Further Work

Learner models as well as search capabilities in existing educational systems typically allow for hard constraints that learning material should fulfill. However, in many cases, users do not just think in terms of hard constraints but rather have soft constraints in their mind, such as "Monday is better but Tuesday would be fine as well." Preferences allow users to specify these wishes in a way that can be processed by engines in order to return only the best matches based on such wishes: those results that dominate the rest of potentially relevant ones. These preference-enabled queries are easy to process and provide intuitive semantics of what is meant with a preference order.

In this paper, we described how such preferences and preference-based queries can be used for selecting for suitable learning resources. We showed that our approach is more expressive than existing approaches, which are either restricted to a single value preference or require a quantitative representation of preferences. By considering the learner's preferences, the learning objects that are selected by the system are optimal for the learning process. Moreover, suboptimal learning objects are not shown to the user, which saves the user from the burden of selecting from a huge set of possibilities. Our approach allows for both hard and soft constraints. We presented a very broad notion of soft constraints that allows for preferences including prioritized as well as nonprioritized composition, partial order preferences, and conditional preferences.

We presented the implementation of our approach as a Web service in the Personal Reader Framework. We exploited the preference extension of a widespread Semantic Web query language in order to query a large data set of learning objects in a user-friendly way. Further, we demonstrated the value of our approach via an experiment at the University of Hannover's learning management system.

Our future work focuses on the improvement of our current prototype with optimized algorithms that are based on recent results on skylining research. We currently investigate enhancements to our user interface in order to allow more expressive preferences, which are already supported by our implemented engine. The storage and reuse of preferences is another topic of future research: a preference repository [ 9] may store some of the preferences that tend to be static (such as the preferred language, location, and so forth) and reuse them automatically for future search requests. The central user modeling service of the Personal Reader Framework may serve as such a repository. In addition, preferences may also be used for improving existing automatic course generation algorithms (such as [ 42] and [ 36]) and recommendations (first ideas in [ 43]). We are currently exploring these directions of research.

## ACKNOWLEDGMENTS

The authors' efforts were supported in part by the European Commission in the TENCompetence Project (IST-2004-02787; http://www.tencompetence.org).

## REFERENCES

• 1. A. Jameson, Adaptive Interfaces and Agents. Lawrence Erlbaum Assoc., pp. 305-330, 2003.
• 2. G. Cheetam, and G. Chivers, Professions, Competence and Informal Learning. Edgard Elgar Publishing, 2005.
• 3. P. Brusilovsky, "Adaptive Hypermedia," User Modeling and User-Adapted Interaction, Ten Year Anniversary Issue 11, A. Kobsa, ed., pp. 87-110, 2001.
• 4. H. Hills, Individual Preferences in E-Learning. Gower, 2003.
• 5. A. Kobsa, "The Adaptive Web: Methods and Strategies of Web Personalization," LNCS, ch. Generic User Modelling Systems, P. Brusilovsky, A. Kobsa, and W. Nejdl, eds., vol. 4321, Springer-Verlag, 2007.
• 6. P. Brusilovsky, and C. Peylo, "Adaptive and Intelligent Web-Based Educational Systems," Int'l J. Artificial Intelligence in Education, special issue on Adaptive and Intelligent Web-Based Educational Systems, vol. 13, pp. 159-172, 2003.
• 7. F. Abel, E. Herder, P. Kärger, D. Olmedilla, and W. Siberski, "Exploiting Preference Queries for Searching Learning Resources," Proc. Second European Conf. Technology Enhanced Learning (EC-TEL '07), pp. 143-157, 2007.
• 8. S. Skiena, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, ch. 5.4.2 Hasse Diagrams, pp. 163, 169-170, and 206-208, Addison-Wesley, 1990.
• 9. S. Holland, and W. Kießling, "Situated Preferences and Preference Repositories for Personalized Database Applications," Proc. 23rd Int'l Conf. Conceptual Modeling (ER '04), pp. 511-523, 2004.
• 10. W. Kießling, "Foundations of Preferences in Database Systems," Proc. 28th Int'l Conf. Very Large Data Bases (VLDB '02), pp. 311-322, 2002.
• 11. J. Chomicki, "Preference Formulas in Relational Queries," ACM Trans. Database Systems, vol. 28, no. 4, pp. 427-466, 2003.
• 12. W.-T. Balke, U. Güntzer, and W. Siberski, "Restricting Skyline Sizes Using Weak Pareto Dominance," Informatik—Forschung und Entwicklung, vol. 21, nos. 3-4, pp. 165-178, 2007.
• 13. C.-Y. Chan, P.-K. Eng, and K.-L. Tan, "Stratified Computation of Skylines with Partially-Ordered Domains," Proc. ACM SIGMOD '05, pp. 203-214, 2005.
• 14. S. Borzsonyi, D. Kossmann, and K. Stocker, "The Skyline Operator," Proc. 17th Int'l Conf. Data Eng. (ICDE), 2001.
• 15. K.-L. Tan, P.-K. Eng, and B.C. Ooi, "Efficient Progressive Skyline Computation," Proc. 27th Int'l Conf. Very Large Databases (VLDB), 2001.
• 16. D. Papadias, Y. Tao, G. Fu, and B. Seeger, "An Optimal and Progressive Algorithm for Skyline Queries," Proc. ACM SIGMOD '03, pp. 467-478, 2003.
• 17. A. Motro, "Vague: A User Interface to Relational Databases that Permits Vague Queries," ACM Trans. Information Systems, vol. 6, no. 3, pp. 187-214, 1988.
• 18. T. Gaasterland, "Cooperative Answering through Controlled Query Relaxation," IEEE Expert, vol. 12, no. 5, pp. 48-59, 1997.
• 19. N. Koudas, C. Li, A.K.H. Tung, and R. Vernica, "Relaxing Join and Selection Queries," Proc. 32nd Int'l Conf. Very Large Data Bases (VLDB '06), VLDB Endowment, pp. 199-210, 2006.
• 20. I. Muslea, "Machine Learning for Online Query Relaxation," Proc. 10th ACM SIGKDD Int'l Conf. Knowledge Discovery and Data Mining (KDD '04), pp. 246-255, 2004.
• 21. S. Agrawal, S. Chaudhuri, G. Das, and A. Gionis, "Automated Ranking of Database Query Results," Proc. First Biennial Conf. Innovative Data Systems Research (CIDR), 2003.
• 22. M.P. Atkinson, M.E. Orlowska, P. Valduriez, S.B. Zdonik, and M.L. Brodie, eds., Proc. 25th Int'l Conf. Very Large Data Bases (VLDB), 1999.
• 23. C. Li, M.A. Soliman, K.C.-C. Chang, and I.F. Ilyas, "RankSQL: Supporting Ranking Queries in Relational Database Management Systems," Proc. 31st Int'l Conf. Very Large Data Bases (VLDB '05), pp. 1342-1345, 2005.
• 24. R. Fagin, "Combining Fuzzy Information from Multiple Systems," Proc. 15th ACM SIGACT-SIGMOD-SIGART Symp. Principles of Database Systems (PODS '96), pp. 216-226, 1996.
• 25. U. Güntzer, W.-T. Balke, and W. Kießling, "Optimizing Multi-Feature Queries for Image Databases," Proc. 26th Int'l Conf. Very Large Data Bases (VLDB '00), pp. 419-428, 2000.
• 26. M. Theobald, H. Bast, D. Majumdar, R. Schenkel, and G. Weikum, "TopX: Efficient and Versatile ${\rm Top}\hbox{-}k$ Query Processing for Semistructured Data," VLDB J., vol. 17, no. 1, pp. 81-115, 2008.
• 27. W. Kießling, and G. Köstler, "Preference SQL—Design, Implementation, Experiences," Proc. 28th Int'l Conf. Very Large Data Bases (VLDB '02), pp. 990-1001, 2002.
• 28. W. Siberski, J.Z. Pan, and U. Thaden, "Querying the Semantic Web with Preferences," Proc. Fifth Int'l Semantic Web Conf. (ISWC '06), pp. 612-624, 2006.
• 29. R. Koper, and B. Daniel, "Developing Advanced Units of Learning Using IMS Learning Design Level B," Int'l J. Advanced Technology for Learning, 2005.
• 30. N.V. Stash, A.I. Cristea, and P.M.D. Bra, "Authoring of Learning Styles in Adaptive Hypermedia: Problems and Solutions," Proc. 13th Int'l World Wide Web Conf. Alternate Track Papers and Posters (WWW '04), pp. 114-123, 2004.
• 31. S.Y. Chen, and R.D. Macredie, "Cognitive Styles and Hypermedia Navigation: Development of a Learning Model," J. Am. Soc. Information Science and Technology, vol. 53, no. 1, pp. 3-15, 2002.
• 32. N. Henze, and M. Kriesell, "Personalization Functionality for the Semantic Web: Architectural Outline and First Sample Implementations, Semantic Web Challenge 2005," Proc. Int'l Conf. Adaptive Hypermedia and Adaptive Web-Based Systems (AH '04), Aug. 2004.
• 33. A. Seaborne, "An Open Source Implementation of SPARQL," Proc. WWW Developers Track Presentation, http://www2006.org/programme/item.php?id=d18, 2006.
• 34. B. McBride, "Jena: A Semantic Web Toolkit," IEEE Internet Computing, vol. 6, no. 6, pp. 55-59, Nov./Dec. 2002.
• 35. N. Henze, and D. Krause, "Personalized Access to Web Services in the Semantic Web," Proc. Third Int'l Semantic Web User Interaction Workshop (SWUI '06), Nov. 2006.
• 36. M. Baldoni, C. Baroglio, I. Brunkhorst, E. Marengo, and V. Patti, "A Personalization Service for Curriculum Planning," Proc. 14th Workshop Adaptivity and User Modeling in Interactive Systems (ABIS '06), Oct. 2006.
• 37. F. Abel, R. Baumgartner, A. Brooks, C. Enzi, G. Gottlob, N. Henze, M. Herzog, M. Kriesell, W. Nejdl, and K. Tomaschewski, "The Personal Publication Reader, Semantic Web Challenge 2005," Proc. Fourth Int'l Semantic Web Conf. (ISWC '05), Nov. 2005.
• 38. P. Dolog, N. Henze, W. Nejdl, and M. Sintek, "Personalization in Distributed E-Learning Environments," Proc. 13th Int'l World Wide Web Conf. Alternate Track Papers and Posters (WWW '04), pp. 170-179, 2004.
• 39. R. Agrawal, and E.L. Wimmers, "A Framework for Expressing and Combining Preferences," Proc. ACM SIGMOD '00, pp. 297-306, 2000.
• 40. N. Spyratos, and V. Christophides, "Querying with Preferences in a Digital Library," Proc. Int'l Workshop Federation over the Web, LNAI 3847, Dagstuhl Seminar (N05182), May 2005.
• 41. S. Dring, S. Fischer, W. Kießling, and T. Preisinger, "Optimizing the Catalog Search Process for E-Procurement Platforms," Proc. Int'l Workshop Data Eng. Issues in E-Commerce (DEEC '05), pp. 39-48, 2005.
• 42. C. Ullrich, "Course Generation Based on HTN Planning," Proc. 13th Ann. Workshop SIG Adaptivity and User Modeling in Interactive Systems, 2005.
• 43. B. Satzger, M. Endres, and W. Kießling, E-Commerce and Web Technologies, ch. A Preference-Based Recommender System, Springer, 2006.

format: plain