c 2014 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. Re-publication of material from this volume requires permission by the copyright owners.
Herausgeber: Der 26. Workshop ”Grundlagen von Datenbanken” (GvDB) 2014 fand dieses Jahr vom 21.10.2014 bis 24.10.2014 auf dem Ritten in Su¨dtirol statt, einem reizvollen Hochplateau mit Blick auf die Dolomiten. Bereits die Anreise war ein Highlight: vom Bahnhof Bozen ging es mit der la¨ngsten Seilbahn Su¨dtirols nach oben und dann mit der Rittner Bahn, einer alten Schmalspur-Stras¨enbahn, u¨ber die La¨rchenwiesen bis zum Tagungsort. Der vierta¨gige Workshop wurde vom GI-Arbeitskreis ”Grundlagen von Informationssystemen” im Fachbereich Datenbanken und Informationssysteme (DBIS) veranstaltet und hat die konzeptionellen und methodischen Grundlagen von Datenbanken und Informationssystemen zum Thema, ist aber auch fu¨r neue Anwendungen offen. Die Workshopreihe und der Arbeitskreis feiern dieses Jahr ihr 25-ja¨hriges Bestehen. Der AK ist damit der a¨ltesten Arbeitskreise der GI. Organisiert wurde der Jubila¨umsworkshop gemeinsam von Fr. Dr. Friederike Klan von der Heinz-Nixdorf-Stiftungsprofessur fu¨r Verteilte Informationssysteme der Friedrich-Schiller-Universita¨t Jena, Hr. Prof. Dr. Gu¨nther Specht von der Forschungsgruppe Datenbanken und Informationssysteme (DBIS) der Universita¨t Innsbruck und Hr. Prof. Dr. Johann Gamper von der Gruppe Datenbanken und Informationssysteme (DIS) der Freien Universita¨t Bozen-Bolzano.
Der Workshop soll die Kommunikation zwischen Wissenschaftlern/-innen im deutschsprachigen Raum fo¨rdern, die sich grundlagenorientiert mit Datenbanken und Informationssystemen bescha¨ftigen. Er bietet insbesondere Nachwuchswissen-schaftler/-innen die Mo¨glichkeit, ihre aktuellen Arbeiten einem gro¨s¨eren Forum in lockerer Atmospha¨re vorzustellen. Mit der Kulisse der beeindruckenden Su¨dtiroler Bergwelt bot der Workshop auf 1200 Metern Meeresho¨he einen idealen Rahmen fu¨r offene und inspirierende Diskussionen dazu ohne Zeitzwang. Insgesamt wurden 14 Arbeiten aus den Einsendungen nach einem Review-Prozess ausgewa¨hlt und vorgestellt. Besonders hervorzuheben ist die Vielfa¨ltigkeit der Themenbereiche: sowohl Kerngebiete in Datenbanksystemen bzw. Datenbankdesign, als auch Themen zur Informationsextraktion, Empfehlungssysteme, Verarbeitung von Zeitreihen, Graphalgorithmen im GIS Bereich, sowie zu Datenschutz und Datenqualita¨t wurden vorgestellt.
Die Vortra¨ge erga¨nzten zwei Keynotes: Ulf Leser, Professor an der Humboldt-Universita¨t zu Berlin, hielt eine Keynote zu Next Generation Data Integration (for Life Sciences) und Francesco Ricci, Professor an der Freien Universita¨t von Bozen-Bolzano zu Context and Recommendations: Challenges and Results. Beiden Vortragenden sei an dieser Stelle fu¨r ihre spontane Bereitschaft zu Kommen und ihre interessanten Vortra¨ge gedankt. Neben dem Wissensaustausch darf auch die soziale Komponente nicht fehlen. Die beiden gemeinsamen Ausflu¨ge bleiben sicher allen lange in guter Erinnerung. Zum einen erklommen wir das bereits schneebedeckte Rittner Horn (2260 Hm), von dem man einen herrlichen Blick auf die Dolomiten hat. Zum anderen ist bei einem Aufenthalt im Herbst in Su¨dtirol das so genannte To¨rggelen nicht wegzudenken: eine Wanderung zu lokalen Bauernscha¨nken, die die Ko¨stlichkeiten des Jahres zusammen mit Kastanien und heurigem Wein auftischen. Sogar der Rektor der Universita¨t Bozen-Bolzano kam dazu extra vom Tal herauf. Eine Konferenz kann nur erfolgreich in einer guten Umgebung stattfinden. Daher danken wir an dieser Stelle den Mitarbeitern des Hauses der Familie fu¨r ihre Arbeit im Hintergrund. Weiterer Dank gilt allen Autoren, die mit ihren Beitra¨gen und Vortra¨gen erst einen interessanten Workshop ermo¨glichen, sowie dem Programmkomitee und allen Gutachtern fu¨r ihre Arbeit. Abschlies¨end gilt dem Organisationsteam, das interaktiv u¨ber alle Landesgrenzen hinweg (Deutschland, O¨ sterreich und Italien) hervorragend zusammen gearbeitet hat, ein gros¨es Dankescho¨n. So international war der GvDB noch nie.
Auf ein Wiedersehen beim na¨chsten GvDB-Workshop
Friederike Klan Johann Gamper
Torsten Grust Andreas Heuer Friederike Klan Birgitta Ko¨ nig-Ries Klaus Meyer-Wegener Gunter Saake Kai-Uwe Sattler Eike Schallehn Ingo Schmitt Holger Schwarz
Gu¨ nther Specht
Karlsruher Institut fu¨ r Technologie Universita¨t Du¨ sseldorf Universita¨t Bozen-Bolzano Universita¨t Tu¨ bingen Universita¨t Rostock Friedrich-Schiller-Universita¨t Jena Friedrich-Schiller-Universita¨t Jena Universita¨t Erlangen Universita¨t Magdeburg Technische Universita¨t Ilmenau Universita¨t Magdeburg Brandenburgische Technische Universita¨t Cottbus Universita¨t Stuttgart Universita¨t Innsbruck
Universita¨t Magdeburg Universita¨t Innsbruck Next Generation Data Integration (for the Life Sciences) (Keynote)
Ulf Leser Context and Recommendations: Challenges and Results (Keynote) Francesco Ricci Optimization of Sequences of XML Schema Modifications - The ROfEL Approach
Thomas No¨singer, Andreas Heuer and Meike Klettke Automatic Decomposition of Multi-Author Documents Using Grammar Analysis
Michael Tschuggnall and Gu¨nther Specht Proaktive modellbasierte Performance-Analyse und -Vorhersage von Datenbankanwendungen
Christoph Koch Big Data und der Fluch der Dimensionalita¨t: Die effiziente Suche nach Quasi
Hannes Grunert and Andreas Heuer Combining Spotify and Twitter Data for Generating a Recent and Public Dataset for Music Recommendation
Martin Pichl, Eva Zangerle and Gu¨nther Specht
Nikolaus Krismer, Gu¨nther Specht and Johann Gamper Software Design Approaches for Mastering Variability in Database Systems
David Broneske, Sebastian Dorok, Veit Koeppen and Andreas Meister
Andreas Finger, Ilvio Bruder, Andreas Heuer, Martin Klemkow and Steffen Konerow 53 Databases under the Partial Closed-world Assumption: A Survey
Simon Razniewski and Werner Nutt Towards Semantic Recommendation of Biodiversity Datasets based on Linked
Felicitas Lo¨ffler, Bahar Sateli, Rene´ Witte and Birgitta Ko¨nig-Ries 9 10 11 17 23 29 35 41 47 59 65 Exploring Graph Partitioning for Shortest Path Queries on Road Networks
Theodoros Chondrogiannis and Johann Gamper Missing Value Imputation in Time Series Using Top-k Case Matching Kevin Wellenzohn, Hannes Mitterer, Johann Gamper, Michael Bo¨hlen and Mourad Khayati
Thomas Bo¨ttcher and Ingo Schmitt
Willi Mann and Nikolaus Augsten 71 77 83 89 Next Generation Data Integration (for the Life Sciences) Ever since the advent of high-throughput biology (e.g., the Human Genome Project), integrating the large number of diverse biological data sets has been considered as one of the most important tasks for advancement in the biological sciences. The life sciences also served as a blueprint for complex integration tasks in the CS community, due to the availability of a large number of highly heterogeneous sources and the urgent integration needs. Whereas the early days of research in this area were dominated by virtual integration, the currently most successful architecture uses materialization. Systems are built using ad-hoc techniques and a large amount of scripting. However, recent years have seen a shift in the understanding of what a ”data integration system” actually should do, revitalizing research in this direction. In this tutorial, we review the past and current state of data integration (exemplified by the Life Sciences) and discuss recent trends in detail, which all pose challenges for the database community.
About the Author Ulf Leser obtained a Diploma in Computer Science at the Technische Universita¨t Mu¨nchen in 1995. He then worked as database developer at the Max-Planck-Institute for Molecular Genetics before starting his PhD with the Graduate School for ”Distributed Information Systems” in Berlin. Since 2002 he is a professor for Knowledge Management in Bioinformatics at Humboldt-Universita¨t zu Berlin. Context and Recommendations: Challenges and Results Recommender Systems (RSs) are popular tools that automatically compute suggestions for items that are predicted to be interesting and useful to a user. They track users’ actions, which signal users’ preferences, and aggregate them into predictive models of the users’ interests. In addition to the long-term interests, which are normally acquired and modeled in RSs, the specific ephemeral needs of the users, their decision biases, the context of the search, and the context of items’ usage, do influence the user’s response to and evaluation for the suggested items. But appropriately modeling the user in the situational context and reasoning upon that is still challenging; there are still major technical and practical difficulties to solve: obtaining sufficient and informative data describing user preferences in context; understanding the impact of the contextual dimensions on user decision-making process; embedding the contextual dimensions in a recommendation computational model. These topics will be illustrated in the talk, making examples taken from the recommender systems that we have developed. Francesco Ricci is associate professor of computer science at Free University of Bozen-Bolzano, Italy. His current research interests include recommender systems, intelligent interfaces, mobile systems, machine learning, case-based reasoning, and the applications of ICT to tourism and eHealth.
He has published more than one hundred of academic papers on these topics and has been invited to give talks in many international conferences, universities and companies.
He is among the editors of the Handbook of Recommender Systems (Springer 2011), a reference text for researchers and practitioners working in this area. He is the editor in chief of the Journal of Information Technology & Tourism and in the editorial board of the Journal of User Modeling and User Adapted Interaction. He is member of the steering committee of the ACM Conference on Recommender Systems. He served on the program committees of several conferences, including as a program co-chair of the ACM Conference on Recommender Systems (RecSys), the International Conference on Case-Based Reasoning (ICCBR) and the International Conference on Information and Communication Technologies in Tourism (ENTER).
Copyright c by the paper’s authors. Copying permitted only for private and academic purposes.
In: G. Specht, H. Gamper, F. Klan (eds.): Proceedings of the 26th GIWorkshop on Foundations of Databases (Grundlagen von Datenbanken), 21.10.2014 - 24.10.2014, Bozen, Italy, published at http://ceur-ws.org. Optimization of Sequences of XML Schema Modifications
The ROfEL Approach Thomas Nösinger, Meike Klettke, Andreas Heuer
Database Research Group
University of Rostock, Germany (tn, meike, ah)@informatik.uni-rostock.de The transformation language ELaX (Evolution Language for XML-Schema [16]) is a domain-specific language for modifying existing XML Schemas. ELaX was developed to express complex modifications by using add, delete and update statements. Additionally, it is used to consistently log all change operations specified by a user. In this paper we present the rule-based optimization algorithm ROfEL (Rule-based Optimizer for ELaX) for reducing the number of logged operations by identifying and removing unnecessary, redundant and also invalid modifications. This is an essential prerequisite for the co-evolution of XML Schemas and corresponding XML documents. 1. INTRODUCTION
The eXtensible Markup Language (XML) [
This may result in the adaptation of the XML Schema definition.
In [16] we presented the transformation language ELaX (Evolution Language for XML-Schema) to describe and formulate these XML Schema modifications. Furthermore, we mentioned briefly that ELaX is also useful to log information about modifications consistently, an essential prerequisite for the co-evolution process of XML Schema and corresponding XML documents [14].
One problem of storing information over a long period of time is, that there can be different unnecessary or redundant modifications. Consider modifications which firstly add an Copyright c by the paper’s authors. Copying permitted only for private and academic purposes.
In: G. Specht, H. Gamper, F. Klan (eds.): Proceedings of the 26th GIWorkshop on Foundations of Databases (Grundlagen von Datenbanken), 21.10.2014 - 24.10.2014, Bozen, Italy, published at http://ceur-ws.org. element and shortly afterwards delete the same element. In the overall context of an efficient realization of modification steps, such operations have to be removed. Further issues are incorrect information (possibly caused by network problems), for example if the same element is deleted twice or the order of modifications is invalid (e.g. update before add).
The new rule-based optimizer for ELaX (ROfEL - Rulebased Optimizer for ELaX) had been developed for solving the above mentioned problems. With ROfEL it is possible to identify unnecessary or redundant operations by using different straightforward optimization rules. Furthermore, the underlying algorithm is capable to correct invalid modification steps. All in all, ROfEL could reduce the number of modification steps by removing or even correcting the logged ELaX operations.
This paper is organized as follows. Section 2 gives the necessary background of XML Schema, ELaX and corresponding concepts. Section 3 and section 4 present our approach, by first specifying our ruled-based algorithm ROfEL and then showing how our approach can be applied for an example. Related work is shown in section 5. Finally, in section 6 we draw our conclusions.
TECHNICAL BACKGROUND
In this section we present a common notation used in the
remainder of this paper. At first, we will shortly introduce
the XSD (XML Schema Definition [
The XML Schema abstract data model consists of different components (simple and complex type definitions, element and attribute declarations, etc.). Additionally, the element information item serves as an XML representation of these components and defines which content and attributes can be used in an XML Schema. The possibility of specifying declarations and definitions in a local or global scope leads to four different modeling styles [13]. One of them is the Garden of Eden style, in which all above mentioned components are globally defined. This results in a high re-usability of declarations and defined data types and influences the flexibility of an XML Schema in general.
The transformation language ELaX1 was developed to handle modifications on an XML Schema and to express such modifications formally. The abstract data model, element information item and Garden of Eden style were important through the development process and influence 1The whole transformation language ELaX is available at: www.ls-dbis.de/elax the EBNF (Extended Backus-Naur Form) like notation of ELaX.
An ELaX statement always starts with ”add”, ”delete” or ”update” followed by one of the alternative components (simple type, element declaration, etc.), an identifier of the current component and completed with optional tuples of attributes and values (examples follow on, e.g. see figure 1). The identifier is a unique EID (emxid)2, a QNAME (qualified name) or a subset of XPath expressions. In the remaining parts we will use the EID as the identifier, but a transformation would be easily possible.
ELaX statements are logged for further analyses and also as a prerequisite for the rule-base optimizer (see section 3).
Figure 1 illustrates the relational schema of the log. The file-ID time EID Toypp-e Tmyspge- content 1 1 1 add 0 add element name 'name' type 'xs:decimal' id 'EID1' ; 1 2 1 upd 0 update element name 'name' change type 'xs:string' ; 1 3 2 add 0 add element name 'count' type 'xs:decimal' id 'EID2' ; … … … … … … chosen values are simple ones (especially the length). The attributes file-ID and time are the composite key for the logging relation, the EID represents the unique identifier for a component of the XSD. The op-Type is a short form for add, delete (del) or update (upd) operations, the msg-Type is for the different message types (ELaX (0), etc.). Lastly, the content contains the logged ELaX statements. The fileID and msg-Type are management information, which are not covered in this paper.
RULE-BASED OPTIMIZER
The algorithm ROfEL (Rule-based Optimizer for ELaX) was developed to reduce the number of logged ELaX operations. This is possible by combining given operations and/or removing unnecessary or even redundant operations. Furthermore, the algorithm could identify invalid operations in a given log and correct these to a certain degree.
ROfEL is a rule-based algorithm. Provided that a log of ELaX operations is given (see section 2), the following rules are essential to reduce the number of operations. In compliance with ELaX these operations are delete (del), add or update (upd). If a certain distinction is not necessary a general operation (op) or variable ( ) are used, empty denotes a not given operation. Additionally, the rules are classified by their purpose to handle redundant (R), unnecessary (U) or invalid (I) operations. ROfEL stops (S) if no other rules are applicable, for example no other operation with the same EID is given.
S: empty → op(EID) ⇒ op(EID) // ↓ most recent operation: delete (del) ↓ R: del(EID) → del(EID) ⇒ del(EID) U: add(EID, content) → del(EID) ⇒ empty U: upd(EID, content) → del(EID) ⇒ del(EID) with time(del(EID)) := TIME(del(EID), upd(EID, content)) (1) (2) (3) (4) 2Our conceptual model is EMX (Entity Model for XML Schema [15]), in which every component of a model has its own, global identifier: EID // ↓ most recent operation: add ↓ U: op(EID) → del(EID) → add(EID, content)
⇒ op(EID) → add(EID, content) I: add(EID, ) → add(EID, content) I: upd(EID, ) → add(EID, content) ⇒ add(EID, content) ⇒ upd(EID, content) // ↓ most recent operation: update (upd) ↓ I: op(EID) → del(EID) → upd(EID, content)
⇒ op(EID) → upd(EID, content) U: add(EID, content) → upd(EID, content)
⇒ add(EID, content) U: add(EID, content) → upd(EID, content’)
⇒ add(EID, MERGE(content0, content)) R: upd(EID, content) → upd(EID, content)
⇒ upd(EID, content) U: upd(EID, content) → upd(EID, content’)
⇒ upd(EID, MERGE(content0, content)) The rules have to be sequentially analyzed from left to right (→), whereas the left operation comes temporally before the right one (i.e., time(left) < time(right). To warrant that the operations are working on the same component, the EID of both operations is equal. If two operations exist and a rule applies to them, then the result can be found on the right side of ⇒. The time of the result is the time of the prior (left) operation, except further investigations are explicit necessary or the time is unknown (e.g. empty).
Another point of view illustrates, that the introduced rules are complete concerning the given operations add, delete and update. Figure 2 represents an operation matrix, in which every possible combination is covered with at least one rule. On the x-axis the prior operation and on the y-axis the (5) (6) (7) (8) (9) (10) (11) (12) operation
add add (6) recent delete (3) update (9) , (10) prior delete (5) (2) (8) update (7) (4) (11) , (12) recent operation are given, whereas the three-valued rules (5) and (8) are minimized to the both most recent operations (e.g. without op(EID)). The break-even point contains the applying rule or rules (considering the possibility of merging the content, see below).
Rule (4) is one example for further investigations. If a component is deleted (del(EID)) but updated (upd(EID)) before, then it is not possible to replace the prior operation with the result (del(EID)) without analyzing other operations between them. The problem is: if another operation (op(EID’)) references the deleted component (e.g. a simple type) but because of ROfEL upd(EID) (it is the prior operation) is replaced with del(EID), then op(EID’) would be invalid. Therefore, the function TIME() is used to determine the correct time of the result. The function is given in pseudocode in figure 3. TIME() has two input parameTIME(op, op’): // time(op) = t; time(op’) = t’; time(opx) = tx; // op.EID == op’.EID; op.EID != opx.EID; t > t’; begin if ((t > tx > t’) AND
(op.EID in opx.content)) then return t; return t’; end. ters and returns a time value, dependent on the existence of an operation, which references the EID in its content. If no such operation exists, the time of the result in rule (4) would be the time of the left (op), otherwise of the right operation (op’ ). The lines with // are comments and contain further information, some hints or even explanations of variables.
The rules (6), (7) and (8) adapt invalid operations. For example if a component is updated but deleted before (see rule (8)), then ROfEL has to decide, which operation is valid. In this and similar cases the most recent operation is preferred, because it is more difficult (or even impossible) to check the intention of the prior operation. Consequently, in rule (8) del(EID) is removed and rule op(EID) → upd(EID, content) applies (op(EID) could be empty; see rule (1)).
The rules (10) and (12) removes unnecessary operations by merging the content of the involved operations. The function MERGE() implements this, the pseudocode is presented in figure 4. MERGE() has two input parameter, the content of the most recent (left) and prior (right) operation. The content is given as a sequence of attribute-value pairs (see ELaX description in section 2). The result of the function is the combination of the input, whereas the content of the most recent operation is preferred analogical to the above mentioned behaviour for I rules. All attributevalue pairs of the most recent operation are completely inserted into the result. Simultaneously, these attributes are removed from the content of the prior operation. At the end of the function, all remaining attributes of the prior (right) operation are inserted, before the result is returned.
All mentioned rules, as well as the functions TIME() and MERGE() are essential parts of the main function ROFEL(); the pseudocode is presented in figure 5. ROFEL()
ROFEL(log): // log = ((t1,op1), (t2,op2), ...); t1 < t2 < ...; begin for (i := log.size(); i >= 2; i := i - 1) for (k := i - 1; k >= 1 ; k := k - 1) if(!(log.get(i).EID == log.get(k).EID AND
log.get(i).time != log.get(k).time)) then continue; // R: del(EID) -> del(EID) => del(EID) (2) if (log.get(i).op-Type == 1 AND
log.get(k).op-Type == 1) then log.remove(i); return ROFEL(log); // U: upd(EID, content) -> del(EID) // => del(EID) (4) if (log.get(i).op-Type == 1 AND
log.get(k).op-Type == 2) then temp := TIME(log.get(i), log.get(k)); if (temp == log.get(i).time) then log.remove(k); return ROFEL(log); log.get(k) := log.get(i); log.remove(i); return ROFEL(log); [...] // U: upd(EID,con) -> upd(EID,con’) // => upd(EID, MERGE(con’,con)) (12) if (log.get(i).op-Type == 2 AND
log.get(k).op-Type == 2) then temp := MERGE(log.get(i).content,
log.get(k).content); log.get(k).content := temp; log.remove(i); return ROFEL(log); return log; end. has one input parameter, the log of ELaX operations. This log is a sequence sorted according to time, it is analyzed reversely. In general, one operation is pinned (log.get(i)) and compared with the next, prior operation (log.get(k)).
If log.get(k) modifies the same component as log.get(i) (i.e., EID is equal) and the time is different, then an applying rule is searched, otherwise the next operation (log.get(k - 1)) is analyzed. The algorithm terminates, if the outer loop completes successfully (i.e., no further optimization is possible).
Three rules are presented in figure 5; the missing ones are skipped ([...]). The first rule is (2), the occurrence of redundant delete operations. According to the above mentioned time choosing guidelines, the most recent operation (log.get(i)) is removed. After this the optimizer starts again with the modified log recursively (return ROFEL(log)).
The second rule is (4), which removes an unnecessary update operation, because the whole referenced component will be deleted later. This rule uses the TIME() function of figure 3 to decide, which time should be assigned to the result.
If another operation between log.get(i) and log.get(k) exists and this operation contains or references log.get(i).EID, then the most recent time (log.get(i).time) is assigned, otherwise the prior time (log.get(k).time).
The last rule is (12), different updates on the same component are given. The MERGE() function of figure 4 combines the content of both operations, before the content of the prior operation is changed and the most recent operation is removed.
After introducing detailed information about the concept of the ROfEL algorithm, we want to use it to optimize an example in the next section.
EXAMPLE
In the last section we specified the rule-based algorithm ROfEL (Rule-based Optimizer for ELaX), now we want to explain the use with an example: we want to store some information about a conference. We assume the XML Schema of figure 6 is given, a corresponding XML document is also presented. The XML Schema is in the Garden of Eden style and contains four element declarations (conf, name, count, start ) and one complex type definition (confType) with a group model (sequence). The group model has three element references, which reference one of the simple type element declarations mentioned above. The identification of all components is simplified by using an EID, it is visualized as a unique ID attribute (id = ”..”).
The log of modification steps to create this XML Schema is presented in figure 7. The relational schema is reduced in comparison to figure 1. The time, the component EID, the op-Type and the content of the modification steps are given.
The log contains different modification steps, which are not time given in the XML Schema (EID > 9). Additionally, some entries are connected within the new introduced column ROfEL. The red lines and numbers represent the involved log entries and applying ROfEL rule.
The sorted log is analyzed reversely, the operation with time stamp 14 is pinned and compared with time entry 13.
Because the modified component is not the same (EID not equal), the next operation with time 12 is taken. Both operations delete the same component (op-Type == 1 ). According to rule (2), the redundant entry 14 is removed and ROFEL restarts with the adapted log.
Rule (4) applies next, a component is updated but deleted later. This rule calls the TIME() function to determine, if the time of the result (i.e., del(EID)) should be 12 or 8.
Because no operation between 12 and 8 references EID 42, the time of the result of (4) is 8. The content of time 8 is replaced with delete element name ’stop’;, the op-Type is set to 1 and the time entry 12 is deleted.
Afterwards, ROFEL restarts again and rule (3) could be used to compare the new operation of entry 8 (original entry 12) with the operation of time 5. A component is inserted but deleted later, so all modifications on this component are unnecessary in general. Consequently, both entries are deleted and the component with EID 42 is not given in the XML Schema of figure 6.
The last applying rule is (10). An element declaration is inserted (time 1) and updated (time 2). Consequently, the MERGE() function is used to combine the content of both operations. According to the ELaX specification, the content of the update operation contains the attribute type with the value xs:string, whereas the add operation contains the attribute type with the value xs:decimal and id with EID1. All attribute-value pairs of the update operation are completely inserted into the output of the function (type = ”xs:string”). Simultaneously, the attribute type is removed from the content of the add operation (type = ”xs:decimal”).
The remaining attributes are inserted in the output (id = ”EID1”). Afterwards, the content of entry 1 is replaced by add element ’name’ type ”xs:string” id ”EID1”; and the second entry is deleted (time 2).
The modification log of figure 7 is optimized with rules (2), (4), (3) and (10). It is presented in figure 8. All in all, five of 14 entries are removed, whereas one is replaced by a combination of two others. This simple example illustrates how ROfEL can reduce the number of logged operations introduced in section 3. More complex examples are easy to construct and can be solved by using the same rules and the same algorithm.
RELATED WORK
Comparable to the object lifecycle, we create new types
or elements, use (e.g. modify, move or rename) and delete
them. The common optimization rules to reduce the
number of operations are originally introduced in [
Regarding other transformation languages, the most
commonly used are XQuery [
Moreover, different transformations to improve efficiency are mentioned.
In [
In [
Another XML Schema modification language is
XSchemaUpdate [
In [
CONCLUSION
The rule-based algorithm ROfEL (Rule-based Optimizer for ELaX) was developed to reduce the number of logged ELaX (Evolution Language for XML-Schema [16]) operations. In general ELaX statements are add, delete and update operations on the components of XML Schema, specified by a user.
ROfEL allows the identification and deletion of unnecessary and redundant modifications by applying different heuristic rules. Additionally, invalid operations are also corrected or removed. In general if the preconditions and conditions for an adaptation of two ELaX log entries are satisfied (e.g. EID equivalent, op-Type correct, etc.), one rule is applied and the modified, reduced log is returned.
We are confident, that even if ROfEL is domain specific and the underlying log is specialized for our needs, the above specified rules are applicable in other scenarios or applications, in which the common modification operations add, delete and update are used (minor adaptations preconditioned).
Future work. The integration of a cost-based component in ROfEL could be very interesting. It is possible, that under consideration of further analyses the combination of different operations (e.g. rule (10)) is inefficient in general. In this and similar cases a cost function with different thresholds could be defined to guarantee, that only efficient adaptations of the log are applied. A convenient cost model would be necessary, but this requires further research.
Feasibility of the approach. At the University of Rostock we implemented the prototype CodeX (Conceptual design and evolution for XML Schema) for dealing with the co-evolution [14] of XML Schema and XML documents; ROfEL and corresponding concepts are fully integrated. As we plan to report in combination with the first release of CodeX, the significantly reduced number of logged operations proves that the whole algorithm is definitely feasible. Automatic Decomposition of Multi-Author Documents Using Grammar Analysis Michael Tschuggnall and Günther Specht
Databases and Information Systems Institute of Computer Science, University of Innsbruck, Austria {michael.tschuggnall, guenther.specht}@uibk.ac.at ABSTRACT The task of text segmentation is to automatically split a text document into individual subparts, which differ according to specific measures. In this paper, an approach is presented that attempts to separate text sections of a collaboratively written document based on the grammar syntax of authors. The main idea is thereby to quantify differences of the grammatical writing style of authors and to use this information to build paragraph clusters, whereby each cluster is assigned to a different author. In order to analyze the style of a writer, text is split into single sentences, and for each sentence a full parse tree is calculated. Using the latter, a profile is computed subsequently that represents the main characteristics for each paragraph. Finally, the profiles serve as input for common clustering algorithms. An extensive evaluation using different English data sets reveals promising results, whereby a supplementary analysis indicates that in general common classification algorithms perform better than clustering approaches.
Keywords Text Segmentation, Multi-Author Decomposition, Parse Trees, pqgrams, Clustering
INTRODUCTION
The growing amount of currently available data is hardly manageable without the use of specific tools and algorithms that provide relevant portions of that data to the user. While this problem is generally addressed with information retrieval approaches, another possibility to significantly reduce the amount of data is to build clusters. Within each cluster, the data is similar according to some predefined features. Thereby many approaches exist that propose algorithms to cluster plain text documents (e.g. [16], [22]) or specific web documents (e.g. [33]) by utilizing various features.
Approaches which attempt to divide a single text document into distinguishable units like different topics, for example, are usually referred to as text segmentation approaches. Here, also many features including statistical models, similarities between words or other semantic analyses are used. Moreover, text clusters are also used in recent plagiarism detection algorithms (e.g. [34]) which Copyright c by the paper’s authors. Copying permitted only for private and academic purposes.
In: G. Specht, H. Gamper, F. Klan (eds.): Proceedings of the 26th GIWorkshop on Foundations of Databases (Grundlagen von Datenbanken), 21.10.2014 - 24.10.2014, Bozen, Italy, published at http://ceur-ws.org. try to build a cluster for the main author and one or more clusters for intrusive paragraphs. Another scenario where the clustering of text is applicable is the analysis of multi-author academic papers: especially the verification of collaborated student works such as bachelor or master theses can be useful in order to determine the amount of work done by each student.
Using results of previous work in the field of intrinsic plagiarism detection [31] and authorship attribution [32], the assumption that individual authors have significantly different writing styles in terms of the syntax that is used to construct sentences has been reused. For example, the following sentence (extracted from a web blog): ”My chair started squeaking a few days ago and it’s driving me nuts." (S1) could also be formulated as ”Since a few days my chair is squeaking - it’s simply annoying .” (S2) which is semantically equivalent but differs significantly according to the syntax as can be seen in Figure 1. The main idea of this work is to quantify those differences by calculating grammar profiles and to use this information to decompose a collaboratively written document, i.e., to assign each paragraph of a document to an author.
The rest of this paper is organized as follows: Section 2 at first recapitulates the principle of pq-grams, which represent a core concept of the approach. Subsequently the algorithm is presented in detail, which is then evaluated in Section 3 by using different clustering algorithms and data sets. A comparison of clustering and classification approaches is discussed in Section 4, while Section 5 depicts related work. Finally, a conclusion and future work directions are given in Section 6.
ALGORITHM
In the following the concept of pq-grams is explained, which serves as the basic stylistic measure in this approach to distinguish between authors. Subsequently, the concrete steps performed by the algorithm are discussed in detail.
Preliminaries: pq-grams
Similar to n-grams that represent subparts of given length n of
a string, pq-grams extract substructures of an ordered, labeled tree
[
The pq-gram index then consists of all possible pq-grams of a tree. In order to obtain all pq-grams, the base is shifted left and right additionally: If then less than p nodes exist horizontally, the corresponding place in the pq-gram is filled with *, in(S1)
S NP
VP PRP NN VBD (My) (chair) (started) (S2) dicating a missing node. Applying this idea to the previous example, also the pq-gram [PP-IN-*-*-*] (no nodes in the base) is valid, as well as [PP-NP-*-*-DT] (base shifted left by two), [PP-NP-*-DT-JJ] (base shifted left by one), [PP-NP-JJNNS-*] (base shifted right by one) and [PP-NP-NNS-*-*] (base shifted right by two) have to be considered. As a last example, all leaves have the pq-gram pattern [leaf_label-*-*-*-*].
Finally, the pq-gram index is the set of all valid pq-grams of a tree, whereby multiple occurrences of the same pq-grams are also present multiple times in the index.
Clustering by Authors
The number of choices an author has to formulate a sentence in terms of grammar structure is rather high, and the assumption in this approach is that the concrete choice is made mostly intuitively and unconsciously. On that basis the grammar of authors is analyzed, which serves as input for common state-of-the-art clustering algorithms to build clusters of text documents or paragraphs.
The decision of the clustering algorithms is thereby based on the frequencies of occurring pq-grams, i.e., on pq-gram profiles. In detail, given a text document the algorithm consists of the following NNS (nuts) 1. At first the document is preprocessed by eliminating unnecessary whitespaces or non-parsable characters. For example, many data sets often are based on novels and articles of various authors, whereby frequently OCR text recognition is used due to the lack of digital data. Additionally, such documents contain problem sources like chapter numbers and titles or incorrectly parsed picture frames that result in nonalphanumeric characters. 2. Subsequently, the document is partitioned into single paragraphs. For simplification reasons this is currently done by only detecting multiple line breaks. 3. Each paragraph is then split into single sentences by utilizing a sentence boundary detection algorithm implemented within the OpenNLP framework1. Then for each sentence a full grammar tree is calculated using the Stanford Parser [19]. For example, Figure 1 depicts the grammar trees resulting from analyzing sentences (S1) and (S2), respectively.
The labels of each tree correspond to a part-of-speech (POS) tag of the Penn Treebank set [23], where e.g NP corresponds to a noun phrase, DT to a determiner or JJS to a superlative adjective. In order to examine the building structure of sentences only like it is intended by this work, the concrete words, i.e., the leafs of the tree, are omitted. 4. Using the grammar trees of all sentences of the document, the pq-gram index is calculated. As shown in Section 2.1 all valid pq-grams of a sentence are extracted and stored into a pq-gram index. By combining all pq-gram indices of all sentences, a pq-gram profile is computed which contains a list of all pq-grams and their corresponding frequency of appearance in the text. Thereby the frequency is normalized by the total number of all appearing pq-grams. As an example, the five mostly used pq-grams using p = 2 and q = 3 of a sample document are shown in Table 1. The profile is sorted descending by the normalized occurrence, and an additional rank value is introduced that simply defines a natural order which is used in the evaluation (see Section 3). 2.3
Using the WEKA framework [15], the following clustering
algorithms have been evaluated: K-Means [
For the clustering algorithms K-Means, Hierarchical Clustering and Farthest First the number of clusters has been predefined according to the respective test data. This means if the test document has been collaborated by three authors, the number of clusters has also been set to three. On the other hand, the algorithms Cascaded K-Means and X-Means implicitly decide which amount of clusters is optimal. Therefore these algorithms have been limited only in ranges, i.e., the minimum and maximum number of clusters has been set to two and six, respectively.
EVALUATION
The utilization of pq-gram profiles as input features for modern clustering algorithms has been extensively evaluated using different documents and data sets. As clustering and classification problems are closely related, the global aim was to experiment on the accuracy of automatic text clustering using solely the proposed grammar feature, and furthermore to compare it to those of current classification techniques. 3.1
Test Data and Experimental Setup
In order to evaluate the idea, different documents and test data sets have been used, which are explained in more detail in the following. Thereby single documents have been created which contain paragraphs written by different authors, as well as multiple documents, whereby each document is written by one author. In the latter case, every document is treated as one (large) paragraph for simplification reasons.
For the experiment, different parameter settings have been evaluated, i.e., the pq-gram values p and q have been varied from 2 to 4, in combination with the three different feature sets. Concretely, the following data sets have been used: • Twain-Wells (T-W): This document has been specifically created for the evaluation of in-document clustering. It contains 50 paragraphs of the book ”The Adventures of Huckleberry Finn” by Mark Twain, and 50 paragraphs of ”The Time Machine” by H. G. Wells2. All paragraphs have been randomly shuffled, whereby the size of each paragraph varies from approximately 25 words up to 280 words. • Twain-Wells-Shelley (T-W-S): In a similar fashion a threeauthor document has been created. It again uses (different) paragraphs of the same books by Twain and Wells, and appends it by paragraphs of the book ”Frankenstein; Or, The Modern Prometheus” by Mary Wollstonecraft Shelley. Summarizing, the document contains 50 paragraphs by Mark Twain, 50 paragraphs by H. G. Wells and another 50 paragraphs by Mary Shelley, whereby the paragraph sizes are similar to the Twain-Wells document. • The Federalist Papers (FED): Probably the mostly referred text corpus in the field of authorship attribution is a series of 85 political essays called ”The Federalist Papers” written by John Jay, Alexander Hamilton and James Madison in the 18th century. While most of the authorships are undoubted, 2The books have been obtained from the Project Gutenberg library, http://www.gutenberg.org, visited July 2014 many works have studied and questioned the correct authorship of 12 disputed essays [24], which have been excluded in the experiment. • The PAN’12 competition corpus (PAN12): As a well-known, state-of-the-art corpus originally created for the use in authorship identification, parts3 of the PAN2012 corpus [18] have been integrated. The corpus is composed of several fiction texts and split into several subtasks that cover smalland common-length documents (1800-6060 words) as well as larger documents (up to 13000 words) and novel-length documents (up to 170,000 words). Finally, the test setused in this evaluation contains 14 documents (paragraphs) written by three authors that are distributed equally.
The best results of the evaluation are presented in Table 2, where the best performance for each clusterer over all data sets is shown in subtable (a), and the best configuration for each data set is shown in subtable (b), respectively. With an accuracy of 63.7% the KMeans algorithm worked best by using p = 2, q = 3 and by utilizing all available features. Interestingly, the X-Means algorithm also achieved good results considering the fact that in this case the number of clusters has been assigned automatically by the algorithm. Finally, the hierarchical cluster performed worst gaining an accuracy of nearly 10% less than K-Means.
Regarding the best performances for each test data set, the results for the manually created data sets from novel literature are generally poor. For example, the best result for the two-author document Twain-Wells is only 59.6%, i.e., the accuracy is only slightly better than the baseline percentage of 50%, which can be achieved by randomly assigning paragraphs into two clusters.4 On the other hand, the data sets reused from authorship attribution, namely the FED and the PAN12 data set, achieved very good results with an accuracy of about 89% and 83%, respectively. Nevertheless, as the other data sets have been specifically created for the clustering evaluation, these results may be more expressive. Therefore a comparison between clustering and classification approaches is discussed in the following, showing that the latter achieve significantly better results on those data sets when using the same features.
K-Means X-Means Farthest First Cascaded K-Means Hierarchical Clust. p 3 2 4 2 4 q 2 4 2 2 3
All Rank Occurrence-Rate Rank Occurrence-Rate
T-W T-W-S FED PAN12-A/B (a) Clustering Algorithms
X-Means X-Means Farth. First K-Means p 3 3 4 3 q 2 4 3 3
All All Rank
All (b) Test Data Sets
COMPARISON OF CLUSTERING AND CLASSIFICATION APPROACHES
For the given data sets, any clustering problem can be
rewritten as classification problem with the exception that the latter need
training data. Although a direct comparison should be treated with
caution, it still gives an insight of how the two different approaches
perform using the same data sets. Therefore an additional
evaluation is shown in the following, which compares the performance of
the clustering algorithms to the performance of the the following
classification algorithms: Naive Bayes classifier [17], Bayes
Network using the K2 classifier [
Table 3 shows the performance of each classifier compared to the best clustering result using the same data and pq-setting. It can be seen that the classifiers significantly outperform the clustering results for the Twain-Wells and Twain-Wells-Shelley documents. The support vector machine framework (LibSVM) and the linear classifier (LibLinear) performed best, reaching a maximum accuracy of nearly 87% for the Twain-Wells document. Moreover, the average improvement is given in the bottom line, showing that most of the classifiers outperform the best clustering result by over 20% in average. Solely the kNN algorithm achieves minor improvements as it attributed the two-author document with a poor accuracy of about 60% only.
A similar general improvement could be achieved on the threeauthor document Twain-Wells-Shelley as can be seen in subtable (b). Again, LibSVM could achieve an accuracy of about 75%, whereas the best clustering configuration could only reach 49%. Except for the kNN algorithm, all classifiers significantly outperform the best clustering results for every configuration.
Quite different comparison results have been obtained for the Federalist Papers and PAN12 data sets, respectively. Here, the improvements gained from the classifiers are only minor, and in some cases are even negative, i.e., the classification algorithms perform worse than the clustering algorithms. A general explanation is the good performance of the clustering algorithms on these data sets, especially by utilizing the Farthest First and K-Means algorithms.
In case of the Federalist Papers data set shown in subtable (c), all algorithms except kNN could achieve at least some improvement. Although the LibLinear classifier could reach an outstanding accuracy of 97%, the global improvement is below 10% for all classifiers. Finally, subtable (d) shows the results for PAN12, where the outcome is quite diverse as some classifiers could improve the clusterers significantly, whereas others worsen the accuracy even more drastically. A possible explanation might be the small data set (only the subproblems A and B have been used), which may not be suited very well for a reliable evaluation of the clustering approaches.
Summarizing, the comparison of the different algorithms reveal that in general classification algorithms perform better than clustering algorithms when provided with the same (pq-gram) feature set. Nevertheless, the results of the PAN12 experiment are very diverse and indicate that there might be a problem with the data set itself, and that this comparison should be treated carefully.
RELATED WORK
Most of the traditional document clustering approaches are based on occurrences of words, i.e., inverted indices are built and used to group documents. Thereby a unit to be clustered conforms exactly Algorithm Max K-Means 44.3 X-Means 38.3 X-Means 45.6 X-Means 45.0 X-Means 47.0 X-Means 49.0 X-Means 36.2 K-Means 35.6 X-Means 35.6 average improvement Algorithm Max Farth. First 77.3 Farth. First 78.8 X-Means 78.8 K-Means 81.8 K-Means 78.8 Farth. First 86.4 Farth. First 86.6 Farth. First 89.4 Farth. First 84.8 average improvement Algorithm Max K-Means 83.3 K-Means 83.3 K-Means 83.3 K-Means 83.3 K-Means 83.3 Farth. First 75.0 K-Means 83.3 K-Means 83.3 K-Means 83.3 average improvement
(d) PAN12-A/B
to one document. The main idea is often to compute topically
related document clusters and to assist web search engines to be able
to provide better results to the user, whereby the algorithms
proposed frequently are also patented (e.g. [
The literature on cluster analysis within a single document to
discriminate the authorships in a multi-author document like it is
done in this paper is surprisingly sparse. On the other hand, many
approaches exist to separate a document into paragraphs of
different topics, which are generally called text segmentation problems.
In this domain, the algorithms often perform vocabulary analysis
in various forms like word stem repetitions [27] or word frequency
models [29], whereby ”methods for finding the topic boundaries
include sliding window, lexical chains, dynamic programming,
agglomerative clustering and divisive clustering” [
Probably one of the first approaches that uses stylometry to automatically detect boundaries of authors of collaboratively written We characterize a graph partition as good if it minimizes the number of connecting edges between the components. However, graph partitioning is an N P -hard problem, thus an optimal solution is out of the question [21]. A popular approach is multilevel graph partitioning (MGP), which can be found in many software libraries, such as METIS [22]. Algorithms such as PUNCH [20] and Spatial Partition Clustering (SPC) [23] take advantage of road network characteristics in order to provide a more efficient graph partitioning. We use METIS for graph partitioning since it is the most efficient approach out of all available ones [24]. METIS requires only the number of components as an argument in order to perform the partitioning. The number of components influences both the number of the in-component shortcuts and the size of the shortcut graph. 3.2
In-component Shortcuts
The second step of the preprocessing phase is the computation of the in-component shortcuts. For each node n in the original graph, we compute the shortest path from the node to every outgoing border node of the component in which n is located. Then we create outgoing shortcuts which abstract the shortest path from n to each outgoing border node. The incoming shortcuts are computed in a similar fashion. Thus, the total number of in-component shortcuts, S, is
k S = X i=1
Ni × (|Biinc | + |Biout |), where Ni is the number of nodes in component Ci and Biinc , Biout are the incoming and outgoing border nodes of Ci, respectivelly. Figure 2 shows the in-component shortcuts for a node located in component C2.
For each border node in a component, b ∈ C, we execute Dijkstra’s algorithm with b as source and all other nodes (including border nodes) in C as targets. Depending on the type of the source node, the expansion strategy is different. When an incoming border node is the source, forward edges are expanded; vice versa, when an outgoing border node is the source, incoming edges are expanded. This strategy ensures that the maximum number of node expansions is at most twice the number of border nodes of G. 3.3
Shortcut Graph Construction
The third step of the preprocessing phase of our approach is the construction of the shortcut graph. Given a graph G, the shortcut graph of G is a graph Gsc(B, Esc), where B is the set of border nodes of G and Esc = EC ∪ SG is the union of the connecting edges, EC , of G and the shortcuts, SG, from every incoming border node to every outgoing border node of the same component. Thus, the number of vertices and edges in the shortcut graph is, respectively,
k |B| = X i=1 k
|Biinc ∪ Biout | and |Esc| =
X (|Biinc | × |Biout |) + EC .
i=1 Figure 3 shows the shortcut graph of our running example. Notice that only border nodes are vertices of the shortcut graph. The set of edges consists of connecting edges and the in-component shortcuts between the border nodes of the same component. Note that there is no need for extra computations in order to populate the shortcut graph.
CORRIDOR MATRIX
In Section 3 we presented how PbS creates shortcuts in order to
answer queries when the source and the target points are in
different components. However, when the source and the target points
of a query are located in the same component, the shortest path
may lie entirely inside the component. Therefore, the search
algorithm will never reach the border nodes and the shortcuts will not
be expanded. In such a case, the common approach is to use
bidirectional search to return the shortest path. However, if the
components of the partitioned graph are large, the query processing can be
quite slow. In order to improve the processing time of such queries,
we partition each component again into sub-components, and for
each component, we compute its Corridor Matrix (CM). In
general, given a partition of a graph G in k components, the Corridor
Matrix (CM) of G is a k × k matrix, where each cell C(i, j) of
CM contains a list of components that are crossed by some
shortest path from a node s ∈ Ci to a node t ∈ Cj . We call such a
list the corridor from Ci to Cj . The concept of the CM is similar
to Arc-Flags [
C1 C2 C3 C4 C5 C1 ∅ C2 ∅ C3 ∅ C4 ∅ C5 ∅
{C2, C3}
To optimize the look-up time in CM, we implemented each component list using a bitmap of length k. Therefore, the space complexity of the CM in the worst case is O(k3). The actual space occupied by the CM is smaller, since we do not allocate space for bitmaps when the component list is empty. For the computation of the Corridor Matrix, we generate the Shortcut Graph in the same way as described in Section 3.3. To compute the distances between all pairs of vertices, we use the Floyd-Warshall algorithm [25], which is specifically designed to compute the all-pair shortest path distance efficiently. After having computed the distances between the nodes, instead of retrieving each shortest path, we retrieve only the components that are crossed by each path, and we update the CM accordingly.
SHORTEST PATH ALGORITHM
In order to process a shortest path query from a source point s to a target point t, we first determine the components of the graph the nodes s ∈ Cs and t ∈ Ct are located in. If Cs = Ct, we execute a modified bidirectional search from s to t. Note that the shortcuts are not used for processing queries for which the source and target are located in the same component C. Instead, we retrieve the appropriate corridor from the CM of C, which contains a list of sub-components. Then, we apply bidirectional search and prune all nodes that belong to sub-components which are not in the retrieved corridor.
In the case that the points s and t are not located in the same component, we exploit the pre-computed shortcuts. First, we retrieve the lengths of the in-component outgoing shortcuts from s to all the outgoing borders of Cs and the length of the in-component incoming shortcuts from all the incoming borders of Ct to t. Then we apply a many-to-many bidirectional search in the overlay graph from all the outgoing borders of Cs to all the incoming borders of Ct. We use the length of the in-component shortcuts (retrieved in the first step) as initial weights for the source and target nodes of the bidirectional search in the Shortcut Graph. The list of edges consisting the path is a set of connecting edges of the original graph and in-component shortcuts. For each shortcut we retrieve the precomputed set of the original edges. The cost to retrieve the original path is linear to the size of the path. After the retrieval we replace the shortcuts with the list of edges in the original graph and we return the new edge list, which is the shortest path from s to t in the original graph.
In this section, we compare our PbS method with CRP, the method our own approach is based on, and CH, a lightweight yet very efficient state-of-the-art approach for shortest path queries in road networks [17]. CRP can handle arbitrary metrics and edge weight updates, while CH is a technique with fast pre-processing and relatively low query processing time. We implemented in Java the basic version of CRP and PbS. The CH algorithm in the experiments is from Graphhopper Route Planner [26]. Due to the different implementations of the graph models between ours and CH, we do not measure the runtime. Instead, for preprocessing we count the extra shortcuts created by each algorithm, while for query processing we count the number of expanded nodes.
For the experiments we follow the same evaluation setting as in [17]. We use 5 publicly available datasets [27], four of of which are a part of the US road network, and the smallest one represents the road network of Rome. We present the characteristics of each dataset in Table 1. In order to compare our PbS approach and CRP with CH, we run our experiments over 5 query sets Q1–Q5, which 2 1 0 0.75 0.5 0.25 0
CAL FLA BAY
NY ROME
California/Nevada
Florida SF Bay Area New York City Center of Rome contain 1000 queries each. We make sure that the distance of every query in set Qi is smaller than the distance of every query in set Qi+1. We also evaluate the CM separately by comparing our CM implementation against Arc Flags and the original bidirectional search for a set of 1000 random queries in the ROME dataset. We use a small dataset in order to simulate in-component query processing.
Preprocessing and Space Overhead
Figures 5 and 6 show a series of measurements for the preprocessing cost of our approach in comparison to CRP and CH over the four largest datasets. Figure 5 shows how many shortcuts are created by each approach. The extra shortcuts can be translated into the space overhead required in order to speed-up shortest path queries. CH uses shortcuts which represent only two edges, while the shortcuts in PbS and CRP are composed of much longer sequences. The difference between the shortcuts produced by CRP and CH is much less. In short, PbS produces about two orders of magnitude more shortcuts than CRP and CH. Moreover, we can observe that the number of shortcuts produced by PbS is getting lower as the number of components is increasing.
CH
CRP
PbS 3 ·107 shortcuts
3 ·107 shortcuts 128 256 384 512 128 256 384
512 (a) NY 1 ·108 shortcuts
(b) BAY 2 ·108 shortcuts 2 1 0 1.5
1 0.5
0 256 512
The same tendency as observed for the number of shortcuts can be observed for the preprocessing time. In Figure 6, we can see that PbS requires much more time than CRP and CH in order to create shortcuts. However, we should also notice that the update 1 ·104 expanded nodes
1 ·104 expanded nodes 128 256 384 512 128 256 384
512 (a) NY ·104 expanded nodes
(b) BAY ·104 expanded nodes cost for CRP and PbS is only a small portion of the preprocessing cost. When an edge weight changes, we need to update only the shortcuts that contains that particular edge. In contrast, for CH the the update cost is the same as the preprocesing cost since a change in a single weight can influence the entire hierarchy.
CH
CRP
PbS preprocessing time(sec)
preprocessing time(sec) 300 200 100
0 1,500 1,000 500 0 128 256 384
512
Figure 7 shows a series of measurements of the performance of CRP and PbS. We evaluate both techniques for different partitions and various numbers of components. An important observation is the tendency of the performance for CRP and PbS. The performance of CRP gets worse for partitions with many components while the opposite happens for PbS. The reason is that for partitions with few components, PbS manages to process many queries with two look-ups (the case where the source and the target are in adjacent components).
In Figure 8 we compare CH with CRP (we choose the best result) and two configurations of PbS: PbS-BT, which is the configuration that leads to the best performance, and PbS-AVG, which is the average performance of PbS among all configurations. We can see that PbS outperforms CRP in all datasets from Q1 to Q5. However, CH is faster in terms of query processing than our PbS approach. CH is more suitable for static networks as the constructed hierarchy of shortcuts enables the shortest path algorithm to expand much fewer nodes.
In Figure 9, we compare the performance of our bidirectional algorithm using the proposed CM, the original bidirectional search and the bidirectional algorithm using Arc Flags. We observe that the bidirectional search is the slowest since no pruning is applied.
Between Arc Flags and CM, the Arc Flags provide slightly better pruning thus fewer expanded nodes by the bidirectional search. On the other hand, the preprocessing time required to compute the Arc Flags is significantly higher than the time required to compute the CM.
CONCLUSION
In this paper we presented PbS, an approach which uses graph partitioning in order to compute shortcuts and speed-up shortest path queries in road networks. Our aim was a solution which supports efficient and incremental updates of edge weights, yet is efficient enough in many real-world applications. In the evaluation, we showed that our PbS approach outperforms CRP. PbS supports edge weight updates as any change in the weight of an edge can influence only shortcuts in a single component. On the other hand, CH is faster than our PbS approach. However, CH cannot handle well edge weight updates as almost the entire hierarchy of shortcuts has to be recomputed every time a single weight changes. For queries where the source and the target are in the same component, we introduced the CM. The efficiency of the CM in query processing approaches the efficiency of Arc Flags, while consuming much less space.
In future work, we plan to extend our approach to support multimodal transportation networks, where the computation has to consider a time schedule, and dynamic and traffic aware networks, where the weights of the edges change over time. We will also improve the preprocessing phase of our approach both in terms of time overhead, by using parallel processing, and space overhead, by using compression techniques or storing some of the precomputed information on the disk.
Q2
Q3
Q4
Q5
Q2
Q3
Q4
Q5 Q2
Q3
Q4
Q5 (a) NY
Q2
Q3 (b) BAY
Q4
Q5 8,000 6,000 4,000 2,000 3,000 2,000 1,000
0 8,000 6,000 4,000 2,000 0 Q1 ·104 1.5
1 0.5
Missing Value Imputation in Time Series using Top-k Case
Matching Kevin Wellenzohn Hannes Mitterer
Free University of Free University of
Bozen-Bolzano Bozen-Bolzano kevin.wellenzohn@unibz.it hannes.mitterer@unibz.it Johann Gamper Free University of
Bozen-Bolzano gamper@inf.unibz.it
M. H. Böhlen
University of Zurich boehlen@ifi.uzh.ch
Mourad Khayati
University of Zurich mkhayati@ifi.uzh.ch ABSTRACT In this paper, we present a simple yet effective algorithm, called the Top-k Case Matching algorithm, for the imputation of missing values in streams of time series data that are similar to each other. The key idea of the algorithm is to look for the k situations in the historical data that are most similar to the current situation and to derive the missing value from the measured values at these k time points. To efficiently identify the top-k most similar historical situations, we adopt Fagin’s Threshold Algorithm, yielding an algorithm with sub-linear runtime complexity with high probability, and linear complexity in the worst case (excluding the initial sorting of the data, which is done only once). We provide the results of a first experimental evaluation using real-world meteorological data. Our algorithm achieves a high accuracy and is more accurate and efficient than two more complex state of the art solutions.
Keywords Time series, imputation of missing values, Threshold Algorithm
INTRODUCTION
Time series data is ubiquitous, e.g., in the financial stock market or in meteorology. In many applications time series data is incomplete, that is some values are missing for various reasons, e.g., sensor failures or transmission errors. However, many applications assume complete data, hence need to recover missing values before further data processing is possible.
In this paper, we focus on the imputation of missing values in long streams of meteorological time series data. As a case study, we use real-world meteorological data collected by the Südtiroler Beratungsring1 (SBR), which is an organization that provides professional and independent consultancy to the local wine and apple farmers, e.g., to determine the optimal harvesting time or to warn about potential threats, such as apple scab, fire blight, or frost. Es1http://www.beratungsring.org/ Copyright © by the paper’s authors. Copying permitted only for private and academic purposes.
In: G. Specht, H. Gamper, F. Klan (eds.): Proceedings of the 26th GIWorkshop on Foundations of Databases (Grundlagen von Datenbanken), 21.10.2014 - 24.10.2014, Bozen, Italy, published at http://ceur-ws.org. pecially frost is dangerous as it can destroy the harvest within a few minutes unless the farmers react immediately. The Südtiroler Beratungsring operates more than 120 weather stations spread all over South Tyrol, where each of them collects every five minutes up to 20 measurements including temperature, humidity etc. The weather stations frequently suffer outages due to sensor failures or errors in the transmission of the data. However, the continuous monitoring of the current weather condition is crucial to immediately warn about imminent threats such as frost and therefore the need arises to recover those missing values as soon as they are detected.
In this paper, we propose an accurate and efficient method to automatically recover missing values. The need for a continuous monitoring of the weather condition at the SBR has two important implications for our solution. Firstly, the proposed algorithm has to be efficient enough to complete the imputation before the next set of measurements arrive in a few minutes time. Secondly, the algorithm cannot use future measurements which would facilitate the imputation, since they are not yet available.
The key idea of our Top-k Case Matching algorithm is to seek for the k time points in the historical data when the measured values at a set of reference stations were most similar to the measured values at the current time point (i.e., the time point when a value is missing). The missing value is then derived from the values at the k past time points. While a naïve solution to identify the top-k most similar historical situations would have to scan the entire data set, we adopt Fagin’s Threshold Algorithm, which efficiently answers top-k queries by scanning, on average, only a small portion of the data. The runtime complexity of our solution is derived from the Threshold Algorithm and is sub-linear with high probability and linear in the worst case, when all data need to be scanned. We provide the results of a first experimental evaluation using real-world meteorological data from the SBR. The results are promising both in terms of efficiency and accuracy. Our algorithm achieves a high accuracy and is more accurate than two state of the art solutions.
The rest of the paper is organized as follows. In Section 2, we review the existing literature about imputation methods for missing values. In Section 3, we introduce the basic notation and a running example. In Section 4, we present our Top-k Case Matching algorithm for the imputation of missing values, followed by the results of an experimental evaluation in Section 5. Section 6 concludes the paper and outlines ideas for future work.
RELATED WORK
Khayati et al. [
Khayati et al. [
The above techniques are designed to handle missing values in static time series. Therefore, they are not applicable in our scenario, as we have to continuously impute missing values as soon as they appear. A naïve approach to run the algorithms each time a missing value occurs is not feasible due to their relatively high runtime complexity.
There are numerous statistical approaches for the imputation of
missing values, including easy ones such as linear or spline
interpolation, all the way up to more complex models such as the ARIMA
model. The ARIMA model [
BACKGROUND
Let S = {s1, . . . , sn} be a set of time series. Each time series, s ∈ S, has associated a set of reference time series Rs, Rs ⊆
s . The value of a time series s ∈ S at time t is denoted as S \ { } s(t). A sliding window of a time series s is denoted as s([t1, t2]) and represents all values between t1 and t2.
EXAMPLE 1. Table 1 shows four temperature time series in a
time window w = [
The Top-k Case Matching algorithm we propose assumes that the time series data is aligned, which generally is not the case for our data. Each weather station collects roughly every 5 minutes new measurements and transmits them to a central server. Since the stations are not perfectly synchronized, the timestamps of the measurements typically differ, e.g., one station collects measurements at 09:02, 09:07, . . . , while another station collects them at 09:04, 09:09, . . . . Therefore, in a pre-processing step we align the time series data using linear interpolation, which yields measurement values every 5 minutes (e.g., 00:00, 00:05, 00:10, . . . ). If we observe a gap of more than 10 minutes in the measurements, we assume that the value is missing.
s (Schlanders) r2 (Göflan) r1 (Kortsch) r3 (Laas) s u il s e C e e r g e D n i e r u t a r e p m e T 16 15 14 1 2 3 4 5 6
7
Timestamps
For the imputation of missing values we assign to each time series s a set Rs of reference time series, which are similar to s.
The notion of similarity between two time series is tricky, though.
Intuitively, we want time series to be similar when they have similar values and behave similarly, i.e., values increase and decrease roughly at the same time and by the same amount.
As a simple heuristic for time series similarity, we use the spatial proximity between the stations that record the respective time series. The underlying assumption is that, if the weather stations are nearby (say within a radius of 5 kilometers), the measured values should be similar, too. Based on this assumption, we manually compiled a list of 3–5 reference time series for each time series.
This heuristic turned out to work well in most cases, though there are situations where the assumption simply does not hold. One reason for the generally good results is most likely that in our data set the over 100 weather stations cover a relatively small area, and hence the stations are very close to each other.
Weather phenomena are often repeating, meaning that for example during a hot summer day in 2014 the temperature measured at the various weather stations are about the same as those measured during an equally hot summer day in 2011. We use this observation for the imputation of missing values. Let s be a time series where the current measurement at time θ, s(θ), is missing. Our assumption on which we base the imputation is as follows: if we find historical situations in the reference time series Rs such that the past values are very close to the current values at time θ, then also the past measurements in s should be very similar to the missing value s(θ). Based on this assumption, the algorithm searches for similar climatic situations in historical measurements, thereby leveraging the vast history of weather records collected by the SBR.
More formally, given a base time series s with reference time series Rs, we are looking for the k timestamps (i.e., historical situations), D = {t1, . . . , tk}, ti < θ, which minimize the error function δ(t) = X |r(θ) − r(t)|.
r∈Rs That is, δ(t) ≤ δ(t0) for all t ∈ D and t0 6∈ D ∪ {θ}. The error function δ(t) is the accumulated absolute difference between the current temperature r(θ) and the temperature at time t, r(t), over all reference time series r ∈ Rs. Once D is determined, the missing value is recovered using some aggregation function g ({s(t)|∀t ∈ D}) over the measured values of the time series s at the timestamps in D. In our experiments we tested the average and the median as aggregation function (cf. Section 5).
EXAMPLE 2. We show the imputation of the missing value s(7) in Table 1 using as aggregation function g the average. For the imputation, we seek the k = 2 most similar historical situations. The two timestamps D = {4, 1} minimize δ(t) with δ(4) = |15.0° − 15.0°| + |16.0° − 15.9°| + |14.3° − 14.2°| = 0.2° and δ(1) = 0.3°. The imputation is then simply the average of the base station measurements at time t = 4 and t = 1, i.e.,s(7) = avg(16.2°, 16.1°) = 21 (16.2° + 16.1°) = 16.15°.
A naïve implementation of this algorithm would have to scan the entire database of historical data to find the k timestamps that minimize δ(t). This is, however, not scalable for huge time series data, hence a more efficient technique is needed.
What we are actually trying to do is to answer a top-k query for
the k timestamps which minimize δ(t). There exist efficient
algorithms for top-k queries. For example, Fagin’s algorithm [
Our Top-k Case Matching algorithm is a variation of TA with slightly different settings. Fagin et al. assume objects with m attributes, a grade for each attribute and a monotone aggregation function f : Rm 7→ R, which aggregates the m grades of an object into an overall grade. The monotonicity property is defined as follows.
DEFINITION 1. (Monotonicity) Let x1, . . . , xm and x01, . . . , x0m be the m grades for objects X and X0, respectively. The aggregation function f is monotone if f (x1, . . . , xm) ≤ f (x01, . . . , x0m) given that xi ≤ x0i for each 1 ≤ i ≤ m.
The TA finds the k objects that maximize the function f . To do so it requires two modes of accessing the data, one being sorted and the other random access. The sorted access is ensured by maintaining a sorted list Li for each attribute mi, ordered by the grade in descending order. TA keeps a bounded buffer of size k and scans each list Li in parallel until the buffer contains k objects and the lowest ranked object in the buffer has an aggregated grade that is greater than or equal to some threshold τ . The threshold τ is computed using the aggregation function f over the grades last seen under the sorted access for each list Li.
EXAMPLE 3. Table 2 shows four objects {A, B, C, D} and their grade for the two attributes interestingness and popularity. Let us assume that k = 2 and the aggregation function f (x1, x2) = x1 + x2. Further, assume that the bounded buffer currently contains {(C, 18), (A, 16)} and the algorithm has read the data up to the boxes shown in gray. At this point the algorithm computes the threshold using the interestingness grade for object B and the popularity grade of object C, yielding τ = f (5, 9) = 5 + 9 = 14. Since the lowest ranked object in the buffer, object A, has an aggregated grade that is greater than τ , we can conclude that C and A are the top-2 objects. Note that the algorithm never read object D, yet it can conclude that D cannot be part of the top-k list.
interestingness
popularity
D grade 10 9 5 4
A grade 10 9 8 6
In order to use the Threshold Algorithm for the imputation of missing values in time series data, we have to adapt it. Instead of looking for the top-k objects that maximize the aggregation function f , we want to find the top-k timestamps that minimize the error function δ(t) over the reference time series Rs. Similar to TA, we need sorted access to the data. Therefore, for each time series r ∈ Rs we define Lr to be the time series r ordered first by value and then by timestamp in ascending order. Table 3 shows the sorted data for the three reference time series of our running example (ignore the gray boxes and small subscript numbers for the moment).
The general idea of our modified TA algorithm is the following. The scan of each sorted lists starts at the current element, i.e., the element with the timestamp t = θ. Instead of scanning the lists Lri only in one direction as TA does, we scan each list sequentially in two directions. Hence, as an initialization step, the algorithm places two pointers, posr+ and posr−, at the current value r(θ) of time series r (the gray boxes in Table 3). During the execution of the algorithm, pointer posr+ is only incremented (i.e., moved down the list), whereas posr− is only decremented (i.e., moved up the list). To maintain the k highest ranking timestamps, the algorithm uses a bounded buffer of size k. A new timestamp t0 is added only if the buffer is either not yet full or δ(t0) < δ(t), where t is the last ¯ ¯ (i.e., lowest ranking) timestamp in the buffer. In the latter case the timestamp t is removed from the buffer.
¯
After this initialization, the algorithm iterates over the lists Lr in round robin fashion, i.e., once the last list is reached, the algorithm wraps around and continues again with the first list. In each iteration, exactly one list Lr is processed, and either pointer posr+ or posr− is advanced, depending on which value the two pointers point to has a smaller absolute difference to the current value at time θ, r(θ). This process grows a neighborhood around the element r(θ) in each list. Whenever a pointer is advanced by one position, the timestamp t at the new position is processed. At this point, the algorithm needs random access to the values r(t) in each list to compute the error function δ(t). Time t is added to the bounded buffer using the semantics described above.
The algorithm terminates once the error at the lowest ranking timestamp, t, among the k timestamps in the buffer is less or equal to the thres¯hold, i.e., δ(t) ≤ τ . The threshold τ is defined as τ = Pr∈Rs |r(θ) − r(po¯sr)|, where posr is either posr+ or posr−, depending on which pointer was advanced last. That is, τ is the sum over all lists Lr of the absolute differences between r(θ) and the value under posr+ or posr−.
EXAMPLE 4. We illustrate the Top-k Case Matching algorithm for k = 2 and θ = 7. Table 4 shows the state of the algorithm in each iteration i. The first column shows an iteration counteri, the second the buffer with the k current best timestamps, and the last column the threshold τ . The buffer entries are tuples of the form (t, δ(t)). In iteration i = 1, the algorithm moves the pointer to t = 4 in list Lr1 and adds (t = 4, δ(4) = 0.2°) to the buffer. Since δ(4) = 0.2° > 0.0° = τ , the algorithm continues. The pointer in Lr2 is moved to t = 6, and (6, 0.4°) is added to the buffer. In iteration i = 4, timestamp 6 is replaced by timestamp 1. Finally, in iteration i = 6, the error at timestamp t = 1 is smaller or equal to τ , i.e., δ(1) = 0.3° ≤ τ6 = 0.3°. The algorithm terminates and returns the two timestamps D = {4, 1}.
Algorithm 1 shows the pseudo code of the Top-k Case Matching algorithm. The algorithm has three input parameters: a set of time series Rs, the current timestamp θ, and the parameter k. It returns the top-k most similar timestamps to the current timestamp θ. In line 2 the algorithm initializes the bounded buffer of size k, and in line 4 the pointers posr+ and posr− are initialized for each reference time series r ∈ Rs. In each iteration of the loop in line 7, the algorithm advances either posr+ or posr− (by calling Algorithm 2) and reads a new timestamp t. The timestamp t is added to the bounded buffer using the semantics described before. In line 15, the algorithm computes the threshold τ . If the buffer contains k timestamps and we have δ(t) ≤ τ , the top-k most similar timestamps were ¯ found and the algorithm terminates.
Algorithm 2 is responsible for moving the pointers posr+ and posr− for each list Lr. The algorithm uses three utility functions. The first isnext(), which takes a pointer as input and returns the next position by either incrementing or decrementing, depending
Algorithm 1: Top−k Case Matching
Result: k timestamps that minimize δ(t) 1 L ← {Lr|r ∈ Rs} 2 buffer ← boundendBuffer(k) 3 for r ∈ Rs do 4 posr−, posr+ ← position of r(θ) in Lr 5 end 6 while L <> ∅ do 7 for Lr ∈ L do 8 t ← AdvancePointer(Lr) 9 if t = NIL then 10 L ← L \ {Lr} 11 else 12 13 14 15 16 if t 6∈ buffer then
buffer.addWithPriority(t, δ(t)) end τ ← ComputeThreshold(L) if buffer.size() = k and buffer.largestError() ≤ τ then
return buffer 17 18 19 end 20 end 21 end 22 return buffer
end on the direction of the pointer. If next() reaches the end of a list, it returns NIL. The utility functions timestamp() and value() return the timestamp and value of a list Lr at a given position, respectively. There are four cases, which the algorithm has to distinguish: 1. None of the two pointers reached the beginning or end of the list. In this case, the algorithm checks which pointer to advance (line 5). The pointer that is closer to r(θ) after advancing is moved by one position. In case of a tie, we arbitrarily decided to advance posr+. 2. Only posr− reached the beginning of the list: the algorithm increments posr+ (line 11). 3. Only posr+ reached the end of the list: the algorithm decrements posr− (line 13). 4. The two pointers reached the beginning respective end of the list: no pointer is moved.
In the first three cases, the algorithm returns the timestamp that was discovered after advancing the pointer. In the last case, NIL is returned.
At the moment we use an in-memory implementation of the algorithm, which loads the whole data set into main memory. More specifically, we keep two copies of the data in memory: the data sorted by timestamp for fast random access and the data sorted by value and timestamp for fast sorted access.
Note that we did not normalize the raw data using some standard technique like the z-score normalization, as we cannot compute that efficiently for streams of data without increasing the complexity of our algorithm. 4.4
Proof of Correctness
The correctness of the Top-k Case Matching algorithm follows directly from the correctness of the Threshold Algorithm. What remains to be shown, however, is that the aggregation function δ(t) is monotone.
Result: Next timestamp to look at or NIL 1 pos ← NIL 2 if next(posr+) <> NIL and next(posr−) <> NIL then 3 Δ+ ← |r(θ) − value(Lr[next(posr+)])| 4 Δ− ← |r(θ) − value(Lr[next(posr−)])| 5 if Δ+ ≤ Δ− then 6 pos, posr+ ← next(posr+) 7 else 8 pos, posr− ← next(posr−) 9 end 10 else if next(posr+) <> NIL and next(posr−) = NIL then 11 pos, posr+ ← next(posr+) 12 else if next(posr+) = NIL and next(posr−) <> NIL then 13 pos, posr− ← next(posr−) 14 end 15 if pos <> NIL then 16 return timestamp(Lr[pos]) 17 else 18 return NIL 19 end
THEOREM 4.1. The aggregation function δ(t) is a monotonically increasing function.
PROOF. Let t1 and t2 be two timestamps such that |r(θ) − r(t1)| ≤ |r(θ) − r(t2)| for each r ∈ Rs. Then it trivially follows that δ(t1) ≤ δ(t2) as the aggregation function δ is the sum of |r(θ) − r(t1)| over each r ∈ Rs and, by definition, each component of δ(t1) is less than or equal to the corresponding component in δ(t2). 4.5
The space and runtime bounds of the algorithm follow directly from the probabilistic guarantees of TA, which has sub-linear cost with high probability and linear cost in the worst case. Note that sorting the raw data to build the lists Lr is a one-time preprocessing step with complexity O(n log n). After that the system can insert new measurements efficiently into the sorted lists with logarithmic cost.
In this section, we present preliminary results of an experimental
evaluation of the proposed Top-k Case Matching algorithm. First,
we study the impact of parameter k on the Top-k Case Matching
and a baseline algorithm. The baseline algorithm, referred to as
“Simple Average”, imputes the missing value s(θ) with the average
of the values in the reference time series at time θ, i.e., s(θ) =
|R1s| Pr∈Rs r(θ). Second, we compare our solution with two state
of the art competitors, REBOM [
Varying k
In this experiment, we study the impact of parameter k on the accuracy and the runtime of our algorithm. We picked five base stations distributed all over South Tyrol, each having two to five reference stations. We simulated a failure of the base station during a time interval, w, of 8 days in the month of April 2013. This amounts to a total of 11452 missing values. We then used the Top-k Case Matching (using both the average and median as aggregation function g) and Simple Average algorithms to impute the missing values. As a measure of accuracy we use the average absolute difference between the real value s(θ) and the imputed value s∗(θ), i.e., Δ = |w1 | Pθ∈w |s(θ) − s∗(θ)|
Figure 2 shows how the accuracy of the algorithms changes with varying k. Interestingly and somewhat unexpectedly, Δ decreases as k increases. This is somehow contrary to what we expected, since with an increasing k also the error function δ(t) grows, and therefore less similar historical situations are used for the imputation. However, after a careful analysis of the results it turned out that for low values of k the algorithm is more sensitive to outliers, and due to the often low quality of the raw data the imputation is flawed. °C0.8 n i Δ cen 0.7 e r e f f iD0.6 e g a r e vA0.5 0
100 50
Parameter k
Table 5 shows an example of flawed raw data. The first row is the current situation, and we assume that the value in the gray box is missing and need to be recovered. The search for the k = 3 most similar situations using our algorithm yields the three rows at the bottom. Notice that one base station value is 39.9° around midnight of a day in August, which is obviously a very unlikely thing to happen. By increasing k, the impact of such outliers is reduced and hence Δ decreases. Furthermore, using the median as aggregation function reduces the impact of outliers and therefore yields better results than the average.
Figure 3 shows the runtime, which for the Top-k Case Matching algorithm linearly increases with k. Notice that, although the imputation of missing values for 8 days takes several minutes, the algorithm is fast enough to continuously impute missing values in our application at the SBR. The experiment essentially corresponds to a scenario, where in 11452 base stations an error occurs at the same time. With 120 weather stations operated by the SBR, the number of missing values at each time is only a tiny fraction of the missing values that we simulated in this experiment.
Comparison with CD and REBOM
In this experiment, we compare the Top-k Case Matching
algorithm with two state-of-the-art algorithms, REBOM [
We used four time series, each containing 50.000 measurements, which corresponds roughly to half a year of temperature measurements. We simulated a week of missing values (i.e., 2017 measurements) in one time series and used the other three as reference time series for the imputation.
Top-k (Median)
Top-k (Average)
CD REBOM 50
Parameter k
The box plot in Figure 4 shows how the imputation error |s(θ) − s∗(θ)| is distributed for each of the four algorithms. The left and right line of the box are the first and third quartile, respectively.
The line inside the box denotes the median and the left and right whiskers are the 2.5% and 97.5% percentile, which means that the plot incorporates 95% of the values and omits statistical outliers.
The experiment clearly shows that the Top-k Case Matching algorithm is able to impute the missing values more accurately than CD and REBOM. Although not visualized, also the maximum observed error for our algorithm is with 2.29° (Average) and 2.21° (Median) considerably lower than 3.71° for CD and 3.6° for REBOM.
0
0.5 1 1.5 Absolute Difference in °C
2
In terms of runtime, the Top-k Case Matching algorithm needed 16 seconds for the imputation of the 2017 missing measurements, whereas CD and REBOM needed roughly 10 minutes each. Note, however, that this large difference in run time is also due to the fact that CD and REBOM need to compute the Pearson correlation coefficient which is a time intensive operation.
In this paper, we presented a simple yet efficient and accurate algorithm, termed Top-k Case Matching, for the imputation of missing values in time series data, where the time series are similar to each other. The basic idea of the algorithm is to look for the k situations in the historical data that are most similar to the current situation and to derive the missing values from the data at these time points. Our Top-k Case Matching algorithm is based on Fagin’s Threshold Algorithm. We presented the results of a first experimental evaluation. The Top-k Case Matching algorithm achieves a high accuracy and outperforms two state of the art solutions both in terms of accuracy and runtime.
As next steps we will continue with the evaluation of the
algorithm, taking into account also model based techniques such as
DynaMMo [
There are several possibilities to further improve the algorithm.
First, we would like to explore whether the algorithm can dynamically determine an optimal value for the parameter k, which is currently given by the user. Second, we would like to make the algorithm more robust against outliers. For example, the algorithm could consider only historical situations that occur roughly at the same time of the day. Moreover, we can bend the definition of “current situation” to not only consider the current timestamp, but rather a small window of consecutive timestamps. This should make the ranking more robust against anomalies in the raw data and weather phenomena such as the foehn. Third, right now the similarity between time series is based solely on temperature data. We would like to include the other time series data collected by the weather stations, such as humidity, precipitation, wind, etc. Finally, the algorithm should be able to automatically choose the currently handpicked reference time series based on some similarity measures, such as the Pearson correlation coefficient.
ACKNOWLEDGEMENTS
The work has been done as part of the DASA project, which is funded by the Foundation of the Free University of Bozen-Bolzano.
We wish to thank our partners at the Südtiroler Beratungsring and the Research Centre for Agriculture and Forestry Laimburg for the good collaboration and helpful domain insights they provided, in particular Armin Hofer, Martin Thalheimer, and Robert Wiedmer.
Dominanzproblem bei der Nutzung von
Multi-Feature-Ansätzen
Thomas Böttcher Technical University Cottbus-Senftenberg
Walther-Pauer-Str. 2, 03046 Cottbus tboettcher@tu-cottbus.de
Ingo Schmitt Technical University Cottbus-Senftenberg
Walther-Pauer-Str. 2, 03046 Cottbus schmitt@tu-cottbus.de Ein Vergleich von Objekten anhand unterschiedlicher Eigenschaften liefert auch unterschiedliche Ergebnisse. Zahlreiche Arbeiten haben gezeigt, dass die Verwendung von mehreren Eigenschaften signifikante Verbesserungen im Bereich des Retrievals erzielen kann. Ein großes Problem bei der Verwendung mehrerer Eigenschaften ist jedoch die Vergleichbarkeit der Einzeleigenschaften in Bezug auf die Aggregation. Ha¨ufig wird eine Eigenschaft von einer anderen dominiert. Viele Normalisierungsansa¨tze versuchen dieses Problem zu lo¨sen, nutzen aber nur eingeschra¨nkte Informationen. In dieser Arbeit werden wir einen Ansatz vorstellen, der die Messung des Grades der Dominanz erlaubt und somit auch eine Evaluierung verschiedener Normalisierungsansa¨tze.
Keywords Dominanz, Score-Normalisierung, Aggregation, Feature Im Bereich des Information-Retrievals (IR), MultimediaRetrievals (MMR), Data-Mining (DM) und vielen anderen Gebieten ist ein Vergleich von Objekten essentiell, z.B. zur Erkennung a¨hnlicher Objekte bzw. Duplikate oder zur Klassifizierung der untersuchten Objekte. Der Vergleich von Objekten einer Objektmenge O basiert dabei in der Regel auf deren Eigenschaftswerten. Im Bereich des MMR sind Eigenschaften (Features) wie Farben, Kanten oder Texturen ha¨ufig genutzte Merkmale. In vielen Fa¨llen genu¨gt es fu¨r einen erscho¨pfenden Vergleich von Objekten nicht, nur eine Eigenschaft zu verwenden. Abbildung 1 zeigt anhand des Beispiels eines Farbhistogramms die Schwa¨chen einer einzelnen Eigenschaft. Obwohl beide Objekte sich deutlich unterscheiden so weisen sie ein sehr a¨hnliches Farbhistogramm auf.
Statt einer Eigenschaft sollte vielmehr eine geeignete Kombination verschiedener Merkmale genutzt werden, um mittels einer verbesserten Ausdruckskraft [16] genauere Ergebnissen zu erzielen. Der (paarweise) Vergleich von Objekten anhand Copyright © by the paper’s authors. Copying permitted only for private and academic purposes.
In: G. Specht, H. Gamper, F. Klan (eds.): Proceedings of the 26th GIWorkshop on Foundations of Databases (Grundlagen von Datenbanken), 21.10.2014 - 24.10.2014, Bozen, Italy, published at http://ceur-ws.org.
Figure 1: Unterschiedliche Objekte mit sehr hoher Farb¨ahnlichkeit von Eigenschaften erfolgt mittels eines Distanz- bzw. A¨ hnlichkeitsmaßes1. Bei der Verwendung mehrerer Eigenschaften lassen sich Distanzen mittels einer Aggregationsfunktion verknu¨pfen und zu einer Gesamtdistanz zusammenfassen.
Der Einsatz von unterschiedlichen Distanzmaßen und Aggregationsfunktionen bringt jedoch verschiedene Probleme mit sich: Verschiedene Distanzmaße erfu¨llen unterschiedliche algebraische Eigenschaften und nicht alle Distanzmaße sind fu¨r spezielle Probleme gleich geeignet. So erfordern Ansa¨tze zu metrischen Indexverfahren oder Algorithmen im DataMining die Erfu¨llung der Dreiecksungleichung. Weitere Probleme ko¨nnen durch die Eigenschaften der Aggregationsfunktion auftreten. So kann diese z.B. die Monotonie oder andere algebraische Eigenschaften der Einzeldistanzmaße zersto¨ren. Diese Probleme sollen jedoch nicht im Fokus dieser Arbeit stehen.
Fu¨r einen A¨ hnlichkeitsvergleich von Objekten anhand mehrerer Merkmale wird erwartet, dass die Einzelmerkmale gleichermaßen das Aggregationsergebnis beeinflussen. Ha¨ufig gibt es jedoch ein Ungleichgewicht, welches die Ergebnisse so stark beeinflusst, dass einzelne Merkmale keinen oder nur einen geringen Einfluss besitzen. Fehlen algebraische Eigenschaften oder gibt es eine zu starke Dominanz, so ko¨nnen die Merkmale und dazugeho¨rigen Distanzmaße nicht mehr sinnvoll innerhalb einer geeigneten Merkmalskombination eingesetzt werden. Im Bereich der Bildanalyse werden zudem immer komplexere Eigenschaften aus den Bilddaten extrahiert.
Damit wird auch die Berechnung der Distanzen basierend auf diesen Eigenschaften immer spezieller und es kann nicht sichergestellt werden welche algebraische Eigenschaften erfu¨llt werden. Durch die vermehrte Verwendung von vielen Einzelmerkmalen steigt auch das Risiko der Dominanz eines oder weniger Merkmale.
Kernfokus dieser Arbeit ist dabei die Analyse von MultiFeature-Aggregationen in Bezug auf die Dominanz einzelner Merkmale. Wir werden zuna¨chst die Dominanz einer Eigen1Beide lassen sich ineinander u¨berfu¨hren [Sch06], im Folgenden gehen wir daher von Distanzmaßen aus. schaft definieren und zeigen wann sich eine solche Dominanz manifestiert. Anschließend fu¨hren wir ein Maß zur Messung des Dominanzgrades ein. Wir werden daru¨ber hinaus zeigen, dass die Ansa¨tze bestehender Normalisierungsverfahren nicht immer ausreichen um das Problem der Dominanz zu lo¨sen. Zusa¨tzlich ermo¨glicht dieses Maß die Evaluation verschiedener Normalisierungsansa¨tze.
Die Arbeit ist dabei wie folgt aufgebaut. In Kapitel 2 werden noch einmal einige Grundlagen zur Distanzfunktion und zur Aggregation dargelegt. Kapitel 3 bescha¨ftigt sich mit der Definition der Dominanz und zeigt anhand eines Beispiels die Auswirkungen. Weiterhin wird ein neues Maß zur Messung des Dominanzgrades vorgestellt. Kapitel 4 liefert einen U¨ berblick u¨ber bestehende Ansa¨tze. Kapitel 5 gibt eine Zusammenfassung und einen Ausblick fu¨r zuku¨nftige Arbeiten.
GRUNDLAGEN Das folgende Kapitel definiert die grundlegenden Begriffe und die Notationen, die in dieser Arbeit verwendet werden.
Distanzberechnungen auf unterschiedlichen Merkmalen erfordern in der Regel auch den Einsatz unterschiedlicher Distanzmaße. Diese sind in vielen Fa¨llen speziell auf die Eigenschaft selbst optimiert bzw. angepasst. Fu¨r eine Distanzberechnung auf mehreren Merkmalen werden dementsprechend auch unterschiedliche Distanzmaße beno¨tigt.
Ein Distanzmaß zwischen zwei Objekten basierend auf einer Eigenschaft p sei als eine Funktion d : O × O 7→ R≥0 definiert. Ein Distanzwert basierend auf einem Objektvergleich zwischen or und os u¨ber einer einzelnen Eigenschaft pj wird mit dj (or, os) ∈ R≥0 beschrieben. Unterschiedliche Distanzmaße besitzen damit auch unterschiedliche Eigenschaften.
Zur Klassifikation der unterschiedlichen Distanzmaße werden folgende vier Eigenschaften genutzt: Selbstidentita¨t: ∀o ∈ O : d(o, o) = 0, Positivita¨t: ∀or 6= os ∈ O : d(or, os) > 0, Symmetrie: ∀or, os ∈ O : d(or, os) = d(os, or) und Dreiecksungleichung: ∀or, os, ot ∈ O : d(or, ot) ≤ d(or, os) + d(os, ot).
Erfu¨llt eine Distanzfunktion alle vier Eigenschaften so wird
sie als Metrik bezeichnet [
Ist der Vergleich zweier Objekte anhand einer einzelnen Eigenschaft nicht mehr ausreichend, um die gewu¨nschte (Un-) A¨ hnlichkeit fu¨r zwei Objekte or,os ∈ O zu bestimmen , so ist die Verwendung mehrerer Eigenschaften no¨tig. Fu¨r eine Distanzberechnung mit m Eigenschaften p = (p1 . . . pm) werden zuna¨chst die partiellen Distanzen δrs = dj (or, os)
j bestimmt. Anschließend werden die partiellen Distanzwerte δrjs mittels einer Aggregationsfunktion agg : R≥m0 7→ R≥0 zu einer Gesamtdistanz aggregiert. Die Menge aller aggregierten Distanzen (Dreiecksmatrix) fu¨r Objektpaar aus O, sei durch δj = (δ1j , δ2j . . . , δlj ) mit l = n22−n bestimmt. Dieser Ansatz erlaubt eine Bestimmung der Aggregation auf den jeweiligen Einzeldistanzwerten. Die Einzeldistanzfunktionen dj sind in sich geschlossen und damit optimiert auf die Eigenschaft selbst. Bisher haben wir das Problem der Dominanz nur kurz eingefu¨hrt. Eine detaillierte Motivation und Heranfu¨hrung an das Problem soll in diesem Kapitel erfolgen. Hierzu werden wir zuna¨chst die Begriffe U¨berbewertung und Dominanzproblem einfu¨hren. Die Auswirkungen des Dominanzproblem auf das Aggregationsergebnis sollen anschließend durch ein
Beispiel erla¨utert werden. Abschließend werden wir ein Maß definieren, um den Grad der Dominanz messen zu ko¨nnen. 3.1
Problemdefinition Wie bereits erwa¨hnt ist der Einsatz vieler, unterschiedlicher Eigenschaften (Features) und ihrer teilweise speziellen Distanzmaße nicht trivial und bringt einige Herausforderungen mit sich. Das Problem der Dominanz soll in diesem Unterabschnitt noch einmal genauer definiert werden.
Zuna¨chst definieren wir das Kernproblem bei der Aggregation mehrerer Distanzwerte.
Problem: Fu¨r einen A¨hnlichkeitsvergleich von Objekten anhand mehrerer Merkmale sollen die Einzelmerkmale gleichermaßen das Aggregationsergebnis beeinflussen. Dominieren die partiellen Distanzen δrjs eines Distanzmaßes dj das Aggregationsergebnis, so soll diese Dominanz reduziert bzw. beseitigt werden.
Offen ist an dieser Stelle die Frage, wann eine Dominanz einer Eigenschaft auftritt, wie sich diese auf das Aggregationsergebnis auswirkt und wie der Grad der Dominanz gemessen werden kann.
Das Ergebnis einer Aggregation von Einzeldistanzwerten ist
erneut ein Distanzwert. Dieser soll jedoch von allen
Einzeldistanzwerten gleichermaßen abha¨ngen. Ist der Wertebereich,
der zur Aggregation verwendeten Distanzfunktionen nicht
identisch, so kann eine Verfa¨lschung des
Aggregationsergebnisses auftreten. Als einfaches Beispiel seien hier zwei
Distanzfunktionen d1 und d2 genannt, wobei d1 alle Distanzen
auf das Intervall [
Allgemein werden dann die aggregierten Distanzwerte
sta¨rker oder schwa¨cher durch Einzeldistanzwerte einer (zur
Aggregation verwendeten) Distanzfunktion beeinflusst als
gewu¨nscht. Wir bezeichnen diesen Effekt als eine U¨
berwertung. Der Grad der U¨ berbewertung la¨sst sich mittels
Korrelationsanalyse (z.B. nach Pearson [
Definition 1 (U¨berbewertung einer Distanzfunktion).
Fu¨r zwei Distanzfunktionen dj und dk, bei der die Distanzwerte δj in Abha¨ngigkeit einer Aggregationsfunktion agg das Aggregationsergebnis sta¨rker beeinflussen als δk, also die Differenz der Korrelationswerte ρ(δj , δagg) − ρ(δk, δagg) > ist, bezeichnen wir dj als u¨berbewertet gegenu¨ber dk.
Eine empirische Untersuchung hat gezeigt, dass sich ab einem Wert ≥ 0.2 eine Beeintra¨chtigung des Aggregationsergebnisses zu Gunsten einer Distanzfunktion zeigt.
Ausgehend von einer U¨ berbewertung definieren wir das Problem der Dominanz.
Definition 2 (Dominanzproblem). Ein Dominanzproblem liegt vor, wenn es eine U¨berbewertung einer Distanzfunktion dj gegenu¨ber dk gibt.
Das Problem einer U¨ berbewertung bei unterschiedlichen
Wertebereichen in denen die Distanzen abgebildet werden ist
jedoch bereits weitreichend bekannt. In vielen Fa¨llen
kommen Normalisierungsverfahren (z.B. im Data-Mining [
Zur Vermeidung einer U¨ berbewertung werden Distanzen
ha¨ufig auf ein festes Intervall normalisiert (i.d.R. auf [
Damit ist zumindest das Problem in unserem vorherigen Beispiel gelo¨st.
Das Problem der Dominanz tritt jedoch nicht nur bei unterschiedlichen Wertebereichen auf. Auch bei Distanzfunktionen, die alle auf den gleichen Wertebereich normalisiert sind, kann das Dominanzproblem auftreten. Im folgenden Abschnitt soll anhand eines Beispiels dieses Dominanzproblem demonstriert werden.
Beispiel eines Dominanzproblems
In Abbildung 2 sind drei Distanzverteilungen ν1, ν2 und ν3
aus einer Stichprobe zu den zugeho¨rigen Distanzfunktionen
d1, d2 sowie d3 dargestellt. Der Wertebereich der
Funktionen sei auf das Intervall [
(c) ν3 Wir betrachten nun die Distanzfunktionen d1 und d2. Bezu¨glich einer beispielhaften Aggregationsfunktion2 2Das Problem der Dominanz tritt auch bei anderen Aggre1 1 1 aggQd1,d2 (or, os) = d1(or, os) ∗ d2(or, os) kann nun gezeigt werden, dass d1 sta¨rker den aggregierten Distanzwert beeinflusst als d2.
In Abbildung 3 sind zwei verschiedene Rangfolgen aller 10 Distanzwerte zwischen fu¨nf zufa¨lligen Objekten der Verteilungen ν1 und ν2 dargestellt, sowie die Aggregation mittels aggQ. Die Distanz-ID definiert hierbei einen Identifikator fu¨r ein Objektpaar. Betrachtet man die ersten fu¨nf Ra¨nge der aggregierten Distanzen, so sieht man, dass die top5-Objekte von Distanzfunktion d1 komplett mit denen der Aggregation u¨bereinstimmen, wa¨hrend bei Distanzfunktion d2 lediglich zwei Werte in der Rangfolge der aggregierten Distanzen auftreten. Gleiches gilt fu¨r die Ra¨nge 6–10. Damit zeigt die Distanzfunktion d1 eine Dominanz gegenu¨ber der Distanzfunktion d2. Schaut man sich noch einmal die Intervalle der Verteilung ν1 und ν2 an, so zeigt sich, dass die Dominanz dem großen Unterschied der Verteilungsintervalle (0.7 vs. 0.2) obliegt. Eine Dominanz manifestiert sich also vor allem wenn eine große Differenz zwischen den jeweiligen Intervallen der Distanzverteilungen liegt. 3.3
Messung der Dominanz Um die U¨ berwertung aus unserem Beispiel und somit die Dominanz zu quantifizieren, wird die Korrelation zwischen den Distanzen von d1 (d2) und der aggregierten Distanzen aus dagg bestimmt. Zur Berechnung der Korrelation ko¨nnen mehrere Verfahren genutzt werden. Verwendet man wie im obigen Beispiel nur die Ra¨nge, so bietet sich Spearmans Rangkorrelationskoeffizient an [13].
ρ(A, B) =
Cov(Rang(A), Rang(B)) σRang(A) ∗ σRang(B)
mit Cov(X, Y ) = E [(X − μx) ∗ (Y − μy)] Hierbei sei Cov(X, Y ) die u¨ber den Erwartungswert von X und Y definierte Kovarianz. Bezogen auf das vorherige Beispiel erhalten wir eine Korrelation nach Spearman fu¨r d1 von ρ1 = 0.94 und fu¨r d2 ρ2 = 0.45. Die Differenz der Korrelationswerte liegt dabei bei ρ1 − ρ2 = 0.49. Ab = 0.2 la¨sst sich eine U¨ berbewertung einer Distanzfunktion feststellen.
Somit haben wir mit ρ1 − ρ2 = 0.49 > 0.2 eine starke U¨ berbewertung von d1 gegenu¨ber d2 in Bezug auf das Aggregationsergebnis gezeigt.
Durch die Verwendung der Rangwerte gibt es allerdings
einen Informationsverlust. Eine alternative Berechnung ohne
Informationsverlust wa¨re durch Pearsons
Korrelationskoeffizienten mo¨glich [
Bisher haben wir die Korrelation zwischen den
aggregierten Werten und denen aus je einer Distanzverteilung
verglichen. Um direkt eine Beziehung zwischen zwei
verschiedenen Distanzverteilungen bzgl. einer aggregierten Verteilung
zu bestimmen, werden zuna¨chst die zwei Korrelationswerte
ρ1 und ρ2 der Distanzfunktionen d1 und d2 bzgl. ihres
Einflusses auf das Aggregationsergebnis graphisch dargestellt
[
Rang
Distanz-ID 1 2 3 4 5 6 7 8 9 10 1 8 4 9 5 7 10 3 2 6 ρ2 0.8 0.6 0 0
(ρ1, ρ2) α 0.2
u ρ1 dem Anstieg m = 1 befinden. Wir bezeichnen diese Gerade als Kalibrierungslinie. Fu¨r unser Beispiel genu¨gt es, nur positive Korrelationswerte zu betrachten. Damit kennzeichnen alle Punkte unterhalb dieser Linie einen gro¨ßeren Einfluss durch d1. Analog gilt bei allen Punkten oberhalb dieser Linie (grau schraffierter Bereich) eine gro¨ßere Beeinflussung durch d2. Abbildung 4 zeigt graphisch die Korrelation fu¨r unser Beispiel von ρ1 und ρ2 auf das Aggregationsergebnis.
Um die Abweichung vom gewu¨nschten Zustand zu
bestimmen, ermitteln wir den Winkel zwischen dem Ortsvektor
~u = (ρ1, ρ2)T durch den Punkt (ρ1, ρ2) und der
horizontalen Koordinatenachse [
4 Calerr(δi, δj , δagg) = 1 − π arctan
Corr(δj, δagg)
Corr(δi, δagg)
Hierbei definiert Corr(X, Y ) ein geeignetes
Korrelationsmaß, in unserem Fall der Rangkorrelationskoeffizient von
Spearman. Wir bezeichnen dieses Maß als
Kalibrierungsfehler, wobei ein Fehler von 0 bedeutet, dass es keine Dominanz
gibt und somit beide Distanzfunktionen gleichermaßen in
das Aggregationsergebnis einfließen. Der Wertebereich des
Kalibrierungsfehlers Calerr liegt in [
Definition 3 (Kalibrierungsfehler ). Ein Kalibrierungsfehler liegt vor, wenn es eine Dominanz einer Distanzfunktion d1 gegenu¨ber d2 gibt, d.h. die Korrelationswerte nicht auf der Kalibrierungslinie liegen. Entsprechend sind zwei Verteilungen von Distanzwerten kalibriert, wenn kein Kalibrierungsfehler auftritt.
Analog zur Definition eines -Wertes zeigte eine empirische Untersuchung fu¨r einen Wert τ ≥ 0.1 eine ungleichma¨ßige Auswirkung auf das Aggregationsergebnis. 3.4
Zusammenfassung
Wir haben in diesem Kapitel gezeigt wann ein
Dominanzproblem auftritt und wie groß der Einfluss auf das
Aggregationsergebnis sein kann. Mit der Verwendung von Gleichung
(2) ist es nun mo¨glich den Grad des Dominanzproblems bzw.
den Kalibrierungsfehler messen zu ko¨nnen. Ein Hauptgrund
fu¨r das Auftreten des Dominanzproblem liegt in der
Verteilung der Distanzen. Sind die Intervalle, in denen die
Distanzen liegen unterschiedlich groß, so ist die Dominanz einer
Eigenschaft unvermeidbar. Ko¨nnen diese Intervalle der
Distanzverteilungen aneinander angeglichen werden ohne
dabei die Rangfolge zu verletzen, so ko¨nnte dies das
Dominanzproblem lo¨sen. Weiterhin ermo¨glicht das Maß des
Kalibrierungsfehlers die Evaluation von Normalisierungsansa¨tzen.
4. STAND DER TECHNIK
Die Aggregation auf Basis mehrerer Eigenschaften ist ein
weit verbreitetes Feld. Es gibt bereits eine Vielzahl von
Arbeiten die sich mit dem Thema der Score-Normalization
bescha¨ftigten. Die Evaluierung solcher Ansa¨tze erfolgt in vielen
Fa¨llen, vor allem im Bereich des IR, direkt u¨ber die
Auswertung der Qualita¨t der Suchergebnisse anhand verschiedener
Dokumentenkollektionen, z.B. TREC-Kollektionen3. Dieses
Vorgehen liefert aber kaum Anhaltspunkte, warum sich
einige Normalisierungsansa¨tze besser fu¨r bestimmte
Anwendungen eignen als andere [
Betrachten wir zuna¨chst verschiedene lineare
Normalisierungen der Form normalize(δ) = ymin + xmδa−xx−mximnin (ymax −
ymin) [15], wobei die Bezeichnungen xmin, xmax, ymin und
ymax verschiedene Normalisierungsparameter darstellen.
Tabelle 1 stellt einige solcher linearer Ansa¨tze dar [
Name Min-Max Fitting ZUMV ZUMV2 MAD ymin 0 0 < a 0 2 0 ymax 1 a < b < 1 1 3 1 xmin min(δ) min(δ) μδ μδ Median(δ) xmax max(δ) max(δ) σδ σδ
MAD(δ)
Neben den linearen Normalisierungsfunktionen gibt es auch
zahlreiche nicht-lineare. Darunter fallen z.B. der
tanhEstimator [
Avampatzis und Kamps stellen in [
Fu¨r das Problem der Dominanz la¨sst sich einfach zeigen,
dass diese Ansa¨tze keinen direkten Einfluss auf die
Distanzverteilung haben. Es werden maximal zwei statistische
Merkmale (Minimum, Maximum, Median etc.) genutzt, um
eine Normalisierung durchzufu¨hren [
Ebenfalls problematisch sind Aggregationen auf unterschiedlichen Distanzverteilungen, z.B. Normal- und Gleichverteilungen.
Es gibt allerdings auch Ansa¨tze, die die Distanzverteilung
als Grundlage zur Normalisierung heranziehen. Hierbei wird
versucht die Distanzen aus unterschiedlichen Quellen so
abzubilden, dass sie mo¨glichst exakt gleiche Verteilungen
besitzen. Die Ansa¨tze von Manmatha [
In dieser Arbeit wurde ein Verfahren vorgestellt um die Dominanz unterschiedlicher Eigenschaften messen zu ko¨nnen. Hierzu wurde zuna¨chst der Begriff der Dominanz und dessen Auswirkung untersucht. Anschließend wurde auf Basis eines von Distanzverteilungen ein Maß vorgestellt, mit dessen Hilfe der Grad der Dominanz bestimmt werden kann.
Dies ermo¨glicht uns eine U¨ berbewertung zu erkennen und die Qualita¨t eines Normalisierungsverfahrens zu evaluieren.
Die in dieser Arbeit vorgestellten Normalisierungsverfahren wiesen jedoch einige Schwa¨chen auf. Hinzu kommt, dass die algebraischen Eigenschaften der zugrunde liegenden Distanzfunktionen ga¨nzlich ungeachtet blieben (Problem fehlender Metrikeigenschaften). In zuku¨nftigen Arbeiten soll daher ein Ansatz entwickelt werden, der beide Probleme gleichermaßen zu lo¨sen versucht. Hierzu soll ein Verfahren der multivariaten Statistik, die multidimensionale Skalierung, verwendet werden. Zusa¨tzlich sollen die Auswirkungen unterschiedlicher Normalisierungsansa¨tze auf Dominanz und (Retrieval-) Qualita¨t untersucht werden. PEL: Position-Enhanced Length Filter for Set Similarity
Joins
Willi Mann Department of Computer Sciences
Jakob-Haringer-Str. 2
Salzburg, Austria wmann@cosy.sbg.ac.at ABSTRACT Set similarity joins compute all pairs of similar sets from two collections of sets. Set similarity joins are typically implemented in a filter-verify framework: a filter generates candidate pairs, possibly including false positives, which must be verified to produce the final join result. Good filters produce a small number of false positives, while they reduce the time they spend on hopeless candidates. The best known algorithms generate candidates using the so-called prefix filter in conjunction with length- and position-based filters.
In this paper we show that the potential of length and position have only partially been leveraged. We propose a new filter, the position-enhanced length filter, which exploits the matching position to incrementally tighten the length filter; our filter identifies hopeless candidates and avoids processing them. The filter is very efficient, requires no change in the data structures of most prefix filter algorithms, and is particularly effective for foreign joins, i.e., joins between two different collections of sets. 1. INTRODUCTION
The set similarity join computes all pairs of similar sets from two collections of sets. The similarity is assessed using a set similarity function, e.g., set overlap, Jaccard, or Cosine similarity, together with a threshold. A pair of sets is in the join result if the similarity exceeds the threshold.
Set similarity joins have many interesting applications
ranging from near duplicate detection of Web documents to
community mining in social networks [
The best algorithms for set similarity joins are based on
an inverted list index and the so-called prefix filter [
Nikolaus Augsten Department of Computer Sciences
Jakob-Haringer-Str. 2
Salzburg, Austria nikolaus.augsten@sbg.ac.at opments in the field leverage the position of the matching tokens between two prefixes (positional filter) and the number of remaining tokens in the overall set (length filter) to further reduce the number of candidates.
This paper proposes a new filter, the position-enhanced length filter (PEL), which tightens the length filter based on the position of the current token match. In previous work, position and length information have only partially been exploited. PEL fully leverages position and length to achieve additional pruning power. As a key feature, PEL does not require changes in the prefix filter index, but is applied on top of previous algorithms at almost no cost. In our experiments we show that PEL is particularly effective for foreign joins. PEL also performs well for self joins over large collections of small sets.1
The remaining paper is organized as follows: Section 2 introduces the set similarity join, provides background material, and an in-depth analysis of filtering techniques based on position and length. Our novel position-enhanced length filter (PEL) is introduced in Section 3. We empirically evaluate our technique and demonstrate its effectiveness on real world data in Section 4. In Section 5 we survey related work and finally draw conclusions in Section 6.
BACKGROUND
We revisit candidate generation, candidate reduction, and efficient verification techniques discussed in literature. The main concepts of this section are summarized in Figure 1.
We shorty explain the prefix filter, translate normalized thresholds to overlap thresholds, revisit length- and position-based filter conditions, and discuss prefixes in index implementations of set similarity joins.
Prefix Filter. The fastest set similarity joins are based
on the prefix filter principle [
Threshold for normalized set overlap. Normalized set similarity measures take the set sizes into account. For 1In a self join, both input relations are identical, which cannot be assumed in a foreign join. minoverlap(t, s0, s1) minsize(t, s0) pmaxsize(t, s0, p0) maxsize(t, s0) 1 +tt (|s0| + |s1|) tp|s0| · |s1| t(|s0|+|s1|)
2 t t |s0| t2 |s0| t |s0| 2−t t |s0|−(1+t)·p0
t (|s0|−p0)2
|s0|·t2 (2−t)·|s0|−2p0
t |s0| t |s0| t2 (2−t)|s0| t Jaccard Cosine
Dice Overlap
Similarity function J (s0, s1) = ||ss00∪∩ss11|| C(s0, s1) = √|s|s00∩|s·|1s|1|
O(s0, s1) = |s0 ∩ s1| the purpose of set similarity joins, the normalized threshold is translated into an overlap threshold (called minoverlap).
The overlap threshold may be different for each pair of sets.
For example, for the Cosine threshold tC (join predicate |s0 ∩ s1|/p|s0| · |s1| ≥ tC ), minoverlap(tC , s0, s1) := tC · p|s0| · |s1|. Table 1 lists the definitions of well-known set similarity functions with the respective overlap thresholds.
Length filter. For a given threshold t and a reference set s0, the size of the matching partners must be within the interval [minsize(t, s0), maxsize(t, s0)] (see Table 1).
This was first observed for the PartEnum algorithm [
Prefix length. The prefix length is |s0| − tO + 1 for
a given overlap threshold tO and set s0. For normalized
thresholds t the prefix length does not only depend on s0,
but also on the sets we compare to. If we compare to s1, the
minimum prefix size of |s0| is minprefix(t, s0, s1) = |s0| −
minoverlap(t, s0, s1) + 1. When we index one of the join
partners, we do not know the size of the matching partners
upfront and need to cover the worst case; this results in the
prefix length maxprefix(t, s0) = |s0|−minsize(t, s0)+1 [
For self joins we can further reduce the prefix length [
Positional filter. The minimum prefix length for a pair of sets is often smaller than the worst case length, which we use to build and probe the index. When we probe the index with a token from the prefix of s0 and find a match in the prefix of set s1, then the matching token may be outside the optimal prefix. If this is the first matching token between s0 and s1, we do not need to consider the pair. In general, a candidate pair s0, s1 must be considered only if
minoverlap(t, s0, s1) ≤ o + min{|s0| − p0, |s1| − p1}, (1) where o is the current overlap (i.e., number of matching tokens so far excluding the current match) and p0 (p1) is the position of the current match in the prefix of s0 (s1); positions start at 0.
Previous work: Position-enhanced length filter (PEL): • minoverlap(t, s0, s1): equivalent overlap threshold for
Jaccard, Cosine, or Dice threshold t for a pair of sets s0, s1. • minsize(t, s0), maxsize(t, s0): minimum and maximum
size of any set that can satisfy threshold t w.r.t. set s0. • maxprefix(t, s0) = |s0| − minsize(t, s0) + 1: length of
probing prefix • midprefix(t, s0) = |s0| − minoverlap(t, s0, s0) + 1: length
of indexing prefix for self joins • minprefix(t, s0, s1) = |s0| − minoverlap(t, s0, s1) + 1:
length of optimal prefix for a particular pair of sets • pmaxsize(t, s0, p0): new tighter limit for maximum set size based on the probing set position
Figure 1: Overview of functions.
The positional filter is stricter than the prefix filter and is applied on top of it. The pruning power of the positional filter is larger for prefix matches further to right (i.e., when p0, p1 increase). Since the prefix filter may produce the same candidate pair multiple times (for each match in the prefix), an interesting situation arises: a pair that passes the positional filter for the first match may not pass the filter for later matches. Thus, the positional filter is applied to pairs that are already in the candidate set whenever a new match is found. To correctly apply the positional filter we need to maintain the overlap value for each pair in the candidate set. We illustrate the positional filter with examples.
Example 1. Set s0 in Figure 2 is the probing set (prefix length maxprefix = 4), s1 is the indexed set (prefix length midprefix = 2, assuming self join). Set s1 is returned from the index due to the match on g (first match between s0 and s1). The required overlap is dminoverlapC (0.8, s0, s1)e = 8. Since there are only 6 tokens left in s1 after the match, the maximum overlap we can get is 7, and the pair is pruned.
This is also confirmed by the positional filter condition (1) (o = 0, p0 = 3, p1 = 1).
Example 2. Assume a situation similar to Figure 2, but the match on g is the second match (i.e., o = 1, p0 = 3, p1 = 1). Condition (1) holds and the pair can not be pruned, i.e., it remains in the candidate set.
Example 3. Consider Figure 3 with probing set s0 and indexed set s1. The match on token a adds pair (s0, s1) to the candidate set. Condition (1) holds for the match on a (o = 0, p0 = 0, p1 = 0), and the pair is not pruned by the positional filter. For the next match (on e), however, condition (1) does not hold (o = 1, p0 = 1, p1 = 4) and the positional filter removes the pair from the candidate set.
Thus, the positional filter does not only avoid pairs to enter pred: C(s0, s1) ≥ 0.8 ⇒ dminoverlap(s0, s1, 0.8)e = 8 s1: a g ? ? ? ? ? ? indexed set (idx)
pred: C(s0, s1) ≥ 0.6 ⇒ dminoverlap(s0, s1, 0.8)e = 8
14 s0: a e ? ? ? ? ? ? ? ? ? ? ? ? ? ? pr
Improving the Prefix Filter
The prefix filter often produces candidates that will be
removed immediately in the next filter stage, the positional
filter (see Example 1). Ideally, such candidates are not
produced at all. This issue is addressed in the mpjoin
algorithm [
Consider condition (1) for the positional filter. We split the condition into two new conditions by expanding the minimum such that the conjunction of the new conditions is equivalent to the positional filter condition: minoverlap(t, s0, s1) ≤ o + |s0| − p0 minoverlap(t, s0, s1) ≤ o + |s1| − p1 The mpjoin algorithm leverages condition (2) as follows.
The probing sets s0 are processed in increasing size order, so |s0| grows monotonically during the execution of the algorithm. Hence, for a specific set s1, minoverlap grows monotonically. We assume o = 0 (and justify this assumption later). For a given index entry (s1, p1), the right side of condition (2) is constant, while the left side can only grow. After the condition fails to hold for the first time, it will never hold again, and the index list entry is removed. For a given index set s1, this improvement changes the effective length of the prefix (i.e., the part of the sets where we may detect matches) w.r.t. a probing set s0 to minprefix(t, s0, s1) = |s1| − minoverlap(t, s0, s1) + 1, which is optimal. On the downside, a shorter prefix may require more work in the verification phase: in some cases, the verification can start after the prefix as will be discussed in Section 2.3. 2.3
Verification
Efficient verification techniques are crucial for fast set similarity joins. We revisit a baseline algorithm and two improvements, which affect the verification speed of both false and true positives. Unless explicitly mentioned, the term prefix subsequently refers to maxprefix (probing set) resp. s1: a e h ? ? ? ? ? ? idx
Figure 4: Verification: where to start? pred: J(s0, s1) ≥ 0.7 ⇒ dminoverlap(. . .)e = 6 pred: J(s0, s1) ≥ 0.7
⇒ dminoverlap(. . .)e = 5 s0: c d e ? ? ? ? pr
s0: c d e ? ? ? ? pr s1: e ? ? ? ? ? idx
s1: e ? ? ? ? idx (a) Match impossible
(b) Match possible midprefix (indexing set) as discussed in earlier sections.
Since the sets are sorted, we compute the overlap in a merge fashion. At each merge step, we verify if the current overlap and the remaining set size are sufficient to achieve the threshold, i.e., we check positional filter condition (1).
(A) Prefix overlap [
(B) Position of last match [
Small candidate set vs. fast verification. The positional filter is applied on each candidate pair returned by the prefix filter. The same candidate pair may be returned multiple times for different matches in the prefix. The positional filter potentially removes existing candidate pairs when they appear again (cf. Section 2.1). This reduces the size of the candidate set, but comes at the cost of (a) lookups in the candidate set, (b) deletions from the candidate set, and (c) book keeping of the overlaps for each candidate pair.
Overall, it might be more efficient to batch-verify a larger
candidate set than to incrementally maintain the candidates;
Ribeiro and Ha¨rder [
In this section, we motivate the position-enhanced length filter (PEL), derive the new filter function pmaxsize, discuss the effect of PEL on self vs. foreign joins, and show how to apply PEL to previous algorithms.
Motivation. The introduction of the position-enhanced length filter is inspired by examples for positional filtering 800 A
D
maxsize probing set size pmaxsize minsize
B 100 position in prefix
maxprefix 200 like Figure 5(a). In set s1, the only match in the prefix occurs at the leftmost position. Despite this being the leftmost match in s1, the positional filter removes s1: the overlap threshold cannot be reached due the position of the match in s0. Apparently, the position of the token in the probing set can render a match of the index sets impossible, independently of the matching position in the index set. Let us analyze how we need to modify the example such that it passes the positional filter: the solution is to shorten index set s1, as shown in Figure 5(b). This suggests that some tighter limit on the set size can be derived from the position of the matching token.
Deriving the PEL filter. For the example in Figure 5(a) the first part of the positional filter, i.e., condition (2), does not hold. We solve the equation minoverlap(t, s0, s1) ≤ |s0| − p0 to |s1| by replacing minoverlap with its definition for the different similarity functions. The result is pmaxsize(t, s0, p0), an upper bound on the size of eligible sets in the index. This bound is at the core of the PEL filter, and definitions of pmaxsize for various similarity measures are listed in Table 1.
Application of PEL. We integrate the pmaxsize upper bound into the prefix filter. The basic prefix filter algorithm processes a probing set as follows: loop over the tokens of the probing set from position p0 = 0 to maxprefix(t, s0) − 1 and probe each token against the index. The index returns a list of sets (their IDs) which contain this token. The sets in these lists are ordered by increasing size, so we stop processing a list when we hit a set that is larger than pmaxsize(t, s0, p0).
Intuitively, we move half of the positional filter to the prefix filter, where we can evaluate it at lower cost: (a) the value of pmaxsize needs to be computed only once for each probing token; (b) we check pmaxsize against the size of each index list entry, which is a simple integer comparison.
Overall, this is much cheaper than the candidate lookup that the positional filter must do for each index match.
Self Joins vs. Foreign Joins. The PEL filter is more powerful on foreign joins than on self joins. In self joins, the size of the probing set is an upper bound for the set size in the index. For all the similarity functions in Table 1, pmaxsize is below the probing set size in less than 50% of the prefix positions. Figure 6 gives an example: The probing set size is 1000, the Jaccard threshold is 0.8, so minsize(0.8, 1000) = 800, maxsize(0.8, 1000) = 1250, and the prefix size is 201. The x-axis represents the position in the prefix, the y-axis represents bounds for the set size of the other set. The region between minsize and maxsize is the base region. The base region is partitioned into four regions (A, B, C, and D) by the probing set size and pmaxsize. For foreign joins, our filter reduces the base region to A+C. If we assume that all set sizes occur equally likely in the individual inverted lists of the index, our filter cuts the number of index list entries that must be processed by 50%. Since the tokens are typically ordered by their frequency, the list length will increase with increasing matching position. Thus the gain of PEL in practical settings can be expected to be even higher.
This analysis holds for all parameters of Jaccard and Dice.
For Cosine, the situation is more tricky since pmaxsize is quadratic and describes a parabola. Again, this is in our favor since the parabola is open to the top, and the curve that splits the base region is below the diagonal.
For self joins, the only relevant regions are A and B since the size of the sets is bounded by the probing set size. Our filter reduces the relevant region from A + B to A. As Figure 6 illustrates, this reduction is smaller than the reduction for foreign joins. For the similarity functions in Table 1, B is always less than a quarter of the full region A + B. In the example, region B covers about 0.22 of A + B.
Algorithm 1: AllPairs-PEL(Sp, I, t) Version using pmaxsize for foreign join; input : Sp collection of outer sets, I inverted list index covering maxprefix of inner sets, t similarity threshold output: res set of result pairs (similarity at least t) 1 foreach s0 in Sp do 2 M = {}; /* Hashmap: candidate set → count */ 3 for p0 ← 0 to maxprefix(t, s0) − 1 do 4 for s1 in Is0[p] do 5 if |s1| < minsize(t, s0) then 6 remove index entry with s1 from Is0[p]; 7 else if |s1| > pmaxsize(t, s0, p0) then 8 break; 9 else 10 if M [s1] = ∅ then 11 M = M ∪ (s1, 0); 12 M [s1] = M [s1] + 1; 13 end 14 end 15 /* Verify() verifies the candidates in M */ 16 res = res ∪ V erif y(s0, M, t); 17 end
Algorithm. Algorithm 1 shows AllPairs-PEL2, a version of AllPairs enhanced with our PEL filter. AllPairsPEL is designed for foreign joins, i.e., the index is constructed in a preprocessing step before the join is executed.
The only difference w.r.t. AllPairs is that AllPairs-PEL uses pmaxsize(t, s0, p0) instead of maxsize(t, s0) in the condition on line 7. The extensions of the algorithms ppjoin and mpjoin with PEL are similar.
An enhancement that is limited to ppjoin and mpjoin is to simplify the positional filter: PEL ensures that no candidate set can fail on the first condition (Equation 2) of the split positional filter. Therefore, we remove the first part of the 2We use the -PEL suffix for algorithm variants that make use of our PEL filter.
DBLP
TREC ENRON
Table 2: Input set characteristics.
#sets in set size # of diff. collection min max avg tokens 3.9 · 106 2 283 12 1.34 · 106 3.5 · 105 2 628 134 3.4 · 105
5 · 105 1 192 000 298 7.3 · 106 minimum in the original positional filter (Equation 1), such that the minimum is no longer needed.
Note that the removal of index entries on line 6 is the easiest solution to apply minsize, but in real-world scenarios, it only makes sense for a single join to be executed. For a similarity search scenario, we recommend to apply binary search on the lists. For multiple joins with the same indexed sets in a row, we suggest to use an overlay over the index that stores the pointer for each list where to start.
EXPERIMENTS
We compare the algorithms AllPairs [
Table 2 lists basic characteristics of the input sets. We conduct our experiments on an Intel Xeon 2.60GHz machine with 128 GB RAM running Debian 7.6 ’wheezy’. We compile our code with gcc -O3. Claims about results on “all” thresholds for a particular data set refer to the thresholds {0.5, 0.6, 0.7, 0.75, 0.8, 0.85, 0.9, 0.95}. We stop tests whose runtime exceeds one hour.
Foreign Joins. For foreign joins, we join a collection of sets with a copy of itself, but do not leverage the fact that the 3http://www.informatik.uni-trier.de/~Ley/db/ 4http://trec.nist.gov/data/t9_filtering.html 5https://www.cs.cmu.edu/~enron/ collections are identical. Figures 7(a) and 7(b) show the performance on DBLP with Jaccard similarity threshold 0.75 and Cosine similarity 0.85. These thresholds produce result sets of similar size. We observe a speedup of factor 3.5 for AllPairs-PEL over AllPairs with Jaccard, and a speedup of 3.8 with Cosine. For mpjoin to mpjoin-PEL we observe a speedup of 4.0 with Jaccard and 4.2 with Cosine. Thus, the PEL filter provides a substantial speed advantage on these data points. For other Jaccard thresholds and mpjoin vs. mpjoin-PEL, the maximum speedup is 4.1 and the minimum speedup is 1.02. For threshold 0.5, only mpjoin-PEL finishes within the time limit of one hour. Among all Cosine thresholds and mpjoin vs. mpjoin-PEL, the maximum speedup is 4.2 (tC = 0.85), the minimum speedup is 1.14 (tC = 0.95).
We only consider Cosine thresholds tC ≥ 0.75, because the non-PEL variants exceed the time limit for smaller thresholds. There is no data point where PEL slows down an algorithm. It is also worth noting that AllPairs-PEL beats mpjoin by a factor of 2.7 with Jaccard threshold tJ = 0.75 and 3.3 on Cosine threshold tC = 0.85; we observe such speedups also on other thresholds.
Figure 7(c) shows the performance on TREC with Jaccard threshold tJ = 0.75. The speedup for AllPairs-PEL compared to AllPairs is 1.64, and for mpjoin-PEL compared to mpjoin 2.3. The minimum speedup of mpjoin over all thresholds is 1.26 (tJ = 0.95), the maximum speedup is 2.3 (tJ = 0.75). Performance gains on ENRON are slightly smaller – we observe speedups of 1.15 (AllPairs-PEL over AllPairs), and 1.85 (mpjoin-PEL over mpjoin) on Jaccard threshold tJ = 0.75 as illustrated in Figure 7(d). The minimum speedup of mpjoin over mpjoin-PEL is 1.24 (tJ = 0.9 and 0.95), the maximum speedup is 2.0 (tJ = 0.6).
Figure 8(a) shows the number of processed index entries (i.e., the overall length of the inverted lists that must be scanned) for Jaccard threshold tJ = 0.75 on TREC. The number of index entries increases by a factor of 1.67 for AllPairs w.r.t. AllPairs-PEL, and a factor of 4.0 for mpjoin w.r.t. mpjoin-PEL.
Figure 8(b) shows the number of candidates that must be verified for Jaccard threshold tJ = 0.75 on TREC. On AllPairs, PEL decreases the number of candidates. This is because AllPairs does not apply any further filters before verification. On mpjoin, the number of candidates increases by 20%. This is due to the smaller number of matches from the prefix index in the case of PEL: later matches can remove pairs from the candidate set (using the positional filter) and thus decrease its size. However, the larger candidate set for PEL does not seriously impact the overall performance: the positional filter is also applied in the verification phase, where the extra candidate pairs are pruned immediately.
Self joins. Due to space constraints, we only show results for DBLP and ENRON, i.e., the input sets with the smallest and the largest average set sizes, respectively. Figure 7(e) and 7(f) show the performance of the algorithms on DBLP and ENRON with Jaccard threshold tJ = 0.75. Our PEL filter provides a speed up of about 1.22 for AllPairs, and 1.17 for mpjoin on DBLP. The maximum speedup we observe is 1.70 (AllPairs-PEL vs. AllPairs, tJ = 0.6); for tJ = 0.95 there is no speed difference between mpjoin and mpjoin-PEL. On the large sets of ENRON, the performance is worse for AllPairs-PEL because verification takes more time than PEL can save in the probing phase (by reducing the number of processed index entries). There is almost no 500 400 300 200 100 sec
sec 400 illrsaP ill-rsaLPEP ijonp ij-opnLEP 231000000 A A m m 150 sec 300 sec 30 sec 0 0 0 0 (a) Foreign join, (b) Foreign join, (c) Foreign join, (d) Foreign j., ENDBLP, tJ = 0.75. DBLP, tC = 0.85. TREC, tJ = 0.75 RON, tJ = 0.75 0 0 (e) Self join, (f) Self join, EN
DBLP, tJ = 0.75 RON, tJ = 0.75 s -sLPE -LPE ir ira in i llaP llP jop jonp A A m m 8.0e10
0 (a) Number of processed index entries. difference between mpjoin and mpjoin-PEL. The maximum increase in speed is 9% (threshold 0.8, mpjoin), the maximum slowdown is 30% (threshold 0.6, AllPairs).
Summarizing, PEL substantially improves the runtime in foreign join scenarios. For self joins, PEL is less effective and, in some cases, may even slightly increase the runtime. 5. RELATED WORK
Sarawagi and Kirpal [
AdaptJoin [
We presented PEL, a new filter based on the pmaxsize upper bound derived in this paper. PEL can be easily plugged into algorithms that store prefixes in an inverted list index (e.g., AllPairs, ppjoin, or mpjoin). For these algorithms, PEL will effectively reduce the number of list entries that must be processed. This reduces the overall lookup time in the inverted list index at the cost of a potentially larger candidate set. We analyzed this trade-off for foreign joins and self joins. Our empirical evaluation demonstrated that 100 60 20 sec