Universität Bonn
Institut für Informatik III

Gaming and Searching
Spielen und Suchen

Alexander Markowetz (PhD, HKUST, 2008)
Assistant Professor / Juniorprofessor

Abteilung III

Institut für Informatik

Rheinische Friedrich-Wilhelms-Universität Bonn

Römerstraße 164, 53117 Bonn

Tel.: +49 228 73-7409
Fax.: +49 228 73-4382 (bitte Titelblatt einfügen / please include a cover page)
E-Mail: alex@iai.uni-bonn.de

PGP Public Key

Skype: markowetz My status

LinkedIn

Alexander Markowetz in a Computer Science Library

Ringvorlesung
Datenschutz


Teaching / Lehre

Diplomarbeiten

Biography

Prior to my current position, I obtained my PhD from the Hong Kong University of Science and Technology (HKUST), under the supervision of Dimitris Papadias, of the Department of Computer Science and Engineering. Before this, I received a Diploma in computer science from the Philipps University, Marburg , Germany, working with Bernhard Seeger. I spent the summer of 2004 with Torsten Suel at Polytechnic University, Brooklyn, where I wrote my diploma thesis. Another trip in 2000 took me to Vassilis Tsotras at University of California Riverside.

A brief CV can be found here.

My current research interests are (i) Online Games and (ii) Keyword Search over Relational Data.

Biographie

Vor meiner derzeitigen Stelle war ich Doktorand Position unter Dimitris Papadias an dem Department of Computer Science and Engineering der Hong Kong University of Science and Technology (HKUST). Davor erhielt ich mein Diplom von der Philipps Universität, Marburg, unter der Betreuung von Bernhard Seeger. Meine Diplomarbeit habe ich im Sommer 2004 bei Torsten Suel an der NYU Polytechnic in Brooklyn geschrieben. Ein früherer Auslandsaufenthalt führte mich zu  Vassilis Tsotras an der University of California Riverside.

Hier findet sich ein kurzer Lebenslauf.

Meine derzeitigen Forschungsschwerpunkte sind (i) Online-Spiele, und (ii) Keywordsuche auf relationalen Daten.

Meine Antrittsvorlesung im Rahmen des Bonner Dies Academicus.

Online Gaming

This research investigates Massive-Multiplayer Online Games (MMOG) and Virtual Worlds (VW). Both applications have evolved into a multi-billion dollar business. Recently, World of Warcraft, an online game, reached ten million subscribers, generating enormous revenues. Similarly, Second Life, a virtual world, announced 12 million user accounts. Both applications are only in their infancy. Eventually, online role playing will outgrow Hollywood’s movie industry. Virtual worlds are expected to trigger a technological revolution, similar to the rise of the Internet. I am particularly interested in the following two aspects:

  1. Gaming Architectures  In MMOG, a central server stores the current game state in the form of relational tables. Clients send updates, such as “move my character to the right”. The server verifies the request, updates the game state, and informs all other clients, who display the character to its right. MMOG constitute large, intricate information systems. Handling requests from several thousand users in real-time, they rely on large distributed server farms. These architectures are general enough to even allow user-side scripting. At the same time, they must be highly secure, since virtual goods translate into real-world value, and legions of hackers probe for exploits. Currently, the main bottleneck resides in the server load, i.e. how many users a single server supports, and how much detail it handles.

  2. Searching Virtual Worlds Objects in a virtual world exist, iff they are stored in a server-sided data table. The entire world thus constitutes a database. This paradigm differs radically from traditional IR, where documents mediate between users and the world. Yet, virtual worlds will soon be as important as our physical environment, and we will want to index them. So, who will be the Google of Second Life? And what functionality will they provide? Currently the research community has not even identified basic search tasks. If the world becomes a database, what will we be searching for? Keys and umbrellas?

Online-Spiele

Diese Forschung untersucht Online Spiele mit extremen Benutzerzahlen, sogenannte Massive-Multiplayer Online Games (MMOG), und Virtuelle Welten (VW).  Beide Anwendungen haben sich zu Multi-Millionen Dollar Branchen gemausert. Vor kurzem erreichte World of Warcraft, ein Online-spiel, zehn Millionen Teilnehmer. Gleichzeitig meldete Second Life, eine virtuelle Welt, den 12 millionsten  Benutzer. Beide Anwendungen stecken noch in den Kinderschuhen. Über kurz oder lang werden Online-Spiele Hollywood’s Filmindustrie übertreffen. Virtuelle Welten werden eine technologische Revolution auslösen, die mit der Entstehung des Internets vergleichbar ist. Meine Forschung untersucht insbesondere die folgenden beiden Aspekte:

  1. Spiele Architekturen Bei MMOG speichert ein zentraler Server den derzeitigen Zustand des Spieles. Benutzer senden Updates, wie z.B. “bewege meine Spielfigur nach rechts”. Der Server verifiziert diese Anweisung, ändert den Zustand des Spieles, und informiert anschließend alle anderen Mitspieler, die die Spielfigur jetzt an der neuen Position darstellen. MMOG bilden große, überaus komplexe Informations-Systeme. Sie bearbeiten Anweisungen von mehreren tausend Benutzern in Echtzeit, und benötigen daher große verteilte Serverfarmen. Diese Architekturen müssen abstrakt genug gehalten sein, um Benutzern das Ausführen eigener Skripte zu erlauben. Gleichzeitig müssen sie hohc-sicher sein, da sich virtuelle Güter gegen reale Währungen verkaufen lassen, und daher tausende Hacker versuchen in solche Systeme einzudringen. Der derzeitige Performance-Engpass liegt bei der Serverlast, d.h., wie viele Benutzer ein Server unterstützt, und welchen Grad an Detail er erlaubt.

  2. Suchen in Virtuellen Welten Objekte in virtuellen Welten existieren genau dann, wenn sie in einer Datenbank abgespeichert sind. Die gesamte Welt findet sich daher in der Datenbank wieder. Dieses Paradigma unterscheidet sich grundlegend von traditionellen Suchmaschinen, wo Dokumente zwischen Benutzer und realer Welt vermitteln. Es ist jedoch davon auszugehen, dass virtuelle Welten eines Tages genauso wichtig für uns sind, wie unsere physische Umgebung, und dass wir sie daher durchsuchen werden wollen. Wer wird dann der Google für Second Life? Und welche Funktionalität wird er bereitstellen? Derzeit hat die Forschung noch nicht einmal die einfachsten Suchvorgänge identifiziert. Wenn jedoch die Welt eine Datenbank ist, wonach werden wir suchen? Nach unseren Schlüsseln und Regenschirmen?

Keyword Search over Relational Data

Relational keyword search (R-KWS) allows accessing a DBMS through keywords. In contrast to Web search, it constructs results by joining tuples from various tables. Assume a movie database with tables for directors, movies and actors. The query "Tarantino, Travolta" retrieves the records of director Quentin Tarantino and actor John Travolta, connected through the movie Pulp Fiction. R-KWS has several key advantages. First, it is extremely simple. Second, it does not require knowledge of the database schema. Third, it poses the only feasible solution for certain search tasks. Assume numerous, intricately connected tables. Probing all interactions between "Tarantino" and "Travolta" requires several thousand SQL expressions, but can be replaced by a single keyword query. R-KWS semantics are defined on a data graph, whose nodes represent tuples, connected by edges, iff they can be joined. A query is answered by the set of minimal sub-graphs containing all keywords; for example the tuples of Travolta, Pulp Fiction and Tarantino. There are two general methodologies for query processing: graph-based (GB) and operator-based (OB). The first materializes the data graph in memory, and retrieves results by means of graph traversal. The second answers a query through thousands of small SQL statements. In my research, I have extended KWS to data streams, proposing operator-based as well as graph-based methods. This application proved immensely complex, and many observations equally apply to R-KWS. Recently, I tackled the remaining bottlenecks in R-KWS: (i) the expensive enumeration of SQL queries, and (ii) their enormous number. I introduce pre-computed SQL expressions, avoiding expensive generation. Most importantly, I propose indexing reachability within the data graph, eliminating unproductive SQL expressions prior to their execution. This method constitutes a novel paradigm in data management and is expected to reach far beyond keyword search.

Keyword-Suche auf Relationalen Daten

Relationale Keyword-Suche (R-KWS) erlaubt Datenbankanfragen durch Schlagwörter. Im Gegensatz zu Web-Suchmaschinen, werden hierbei Tupel aus verschiedenen Tabellen zu Ergebnissen kombiniert. Nehmen wir eine Film-Datenbank an, mit Tabellen für Regisseure, Schauspieler, und Filme. Die Anfrage "Tarantino, Travolta" führt zu den Einträgen für den Regisseur Quentin Tarantino und den Schauspieler John Travolta, verbunden durch das Tupel für den gemeinsamen Film Pulp Fiction. R-KWS hat mehrere Vorteile. Erstens ist es extrem einfach. Zweitens muss der Benutzer das Datenbankschema nicht kennen. Drittens ist es die einzig menschlich machbare Anfragesprache für viele Suchaufgaben. In einer Datenbank mit zahlreichen, komplex verbundenen Tabellen können alle Interaktionen zwischen "Tarantino" und "Travolta" nur mithilfe von mehreren tausend SQL Anweisungen gefunden werden. Dieselbe Aufgabe lässt sich mit einer einzigen Keyword-Suche lösen. Die R-KWS Semantik ist auf einem Datengraph definiert, dessen Knoten relationale Tupel repräsentieren, die durch Kanten verbunden sind, falls man sie sinnvoll verbinden kann (Join). Eine Anfrage wird mit der Menge von minimalen Sub-Graphen beantwortet, die alle Schlagwörter erhalten, z.B. durch den Verbund der Tupel für John Travolta, Pulp Fiction und Quentin Tarantino. Es gbt zwei grundlegende Ansätze zur Anfragebearbeitung: graph-basiert (GB) und operator-basiert (OB). Erstere materialisiert den Datengraph im Hauptspeicher, und traversiert ihn auf der Suche nach Ergebnissen. Die zweite Methode beantwortet die Anfrage mittels tausender automatisch generierter SQL Ausdrücke. In meiner Forschung habe ich Keyword-Suche auf relationale Datenströme erweitert, und einen operator-basierten sowohl als auch einen graph-basierten Ansatz zur Abfragebearbeitung vorgestellt. Diese Anwendung stellte sich als sehr komplex heraus, jedoch lassen sich viele Beobachtungen zurück auf statische Tabellen übertragen. In jüngeren Zeit bin ich die verbleibenden zwei Engpässe angegangen: (i) die teure Erzeugung von SQL Anweisungen, und (ii) ihre enorme Anzahl. Vorberechnete SQL Anfragen vermeiden die Generierung zum Anfragezeitpunkt. vor allem habe ich ein Methode zur Graph-Indexierung vorgestellt, die es erlaubt unproduktive SQL Anfragen bereits vor ihrer Ausführung zu eliminieren. Diese Methode stellt ein neues Paradigma zum Datenmanagement dar, und wir Kreise ziehen, weit außerhalb von Keyword-Suche.

Past Research

  1. Spatio-Temporal Index Structures Commonly found in geographic information systems (GIS), spatial index structures manage objects in low-dimensional space, such as positions of hotels or taxis. Typical queries retrieve objects that fall within a certain area (range queries), or are close to the user’s position (nearest neighbors). Others count objects in an area (spatial aggregates), or seek statistical patterns (spatial data mining). Similarly, temporal data is also multidimensional but subject to several restrictions, requiring specific data structures.

  2. Relational Data Streams A data stream management system (DSMS) processes small relational tuples, arriving at ultra high frequency. Such data is commonly generated from environmental sensors or by monitoring online activity, for example recording every time a user views an online shopping item. Due to its extreme arrival rates, this data cannot be written to disk. Instead, it is processed in memory, by means of specialized operators.

  3. Geographic Information Retrieval Although World Wide Web implies globally available data, Internet users often seek local information. During extensive pre-processing, a geographic search engine infers geographic positions for every document. For example, a document containing the term “big apple” is considered to provide information about New York. For a given query, documents are ranked according to (i) the relevance to the keyword and (ii) spatial proximity, necessitating an entire range of new data structures. Our 2004 prototype of a geographic search engine reached industrial strength and predated similar efforts by most commercial competitors.

Frühere Forschung

  1. Räumlich-Temporelle Indexstrukturen In Geographischen Informations-Systemen (GIS) verwalten räumliche Indexstrukturen Objekte im niederdimensionalen Raum, wie z.B. die Positionen von Hotels oder Taxis. Typische Anfragen suchen nach Objekten die sich in einem bestimmten Gebiet befinden, oder in der Nähe des Benutzers (Nächster-Nachbar Anfrage). Andere zählen die Objekte in einem Gebiet (räumliche Aggregate), oder suchen statistische Muster (räumliches Data Mining). Temporale Daten verhalten sich grundsätzlich ähnlich, unterliegen jedoch zusätzlichen Restriktionen, und  benötigen daher spezielle Datenstrukturen.

  2. Relationale Datenströme Ein Datenstrom-Management-System (DSMS) verarbeitet kleine relationale Tupel, die in ultra-hoher Geschwindigkeit empfangen werden. Solche Daten werden häufig von Umweltsensoren erzeugt, oder resultieren aus den Aktivitäten von Online-Nutzern, wo z.B. jedes mal ein Tupel gesendet wird, wenn ein Nutzer einen Artikel eines Web-Shops ansieht. Aufgrund der extrem hohen Raten können solche Daten nicht auf Platte geschrieben werden, und müssen stattdessen im Hauptspeicher verarbeitet werden, meist mithilfe von speziellen relationalen Operatoren.

  3. Geographische Suchmaschinen Obwohl der Ausdruck weltweites Datennetz eine globale Verfügbarkeit impliziert, sind Internet-Nutzer meist an lokalen Informationen interessiert. Durch aufwendige Vorverarbeitung verknüpft eine geographische Suchmaschine jedes Dokument mit entsprechenden geographischen Regionen. Zum Beispiel wird angenommen, dass ein Dokument mit dem Ausdruck “big apple” Informationen über New York enthält. Suchergebnisse werden dann nach zwei Kriterien geordnet: (i) der Relevanz bzgl. der Schlagwörter, und (ii) räumlicher Nähe, und benötigen daher spezielle Datenstrukturen. Unser Prototyp von 2004 war entsprechenden kommerziellen Anstrengungen voraus, und erreichte ein einsatzfähiges Niveau.

Selected Publications / Ausgesuchte Publikationen (@DBLP, @Citeseer , complete)

Program Comittees / Programmkomittee

Services

Co-Authors / Co-Autoren

Hobbies

Web Pages

  • www.fahrradschmiede.de A family owned bicycle supermarket, for which I co-ordinated online marketing.

  • www.thehkgroove.com Fund-raising concerts in Hong Kong (now offline).

  • www.waldhof-sachsen.de Documentation of the rebuilding efforts for an estate in Saxony, destroyed by the centennial flood in 2002.

Blogs