sunSunday, May 6, 2007Pre-conference W3C AC MeetingmonMonday, May 7, 2007Pre-conference W3C AC Meeting and MoretueTuesday, May 8, 2007Building the WebwedWednesday, May 9, 2007The Global WebthuThursday, May 10, 2007Mining the WebfriFriday, May 11, 2007Weaving the WebsatSaturday, May 12, 2007The World Wide Web and You am18:30am to 10:00ambreak1breakam210:30am to 12 noonlunchlunch breakpm11:30pm to 3:00pmbreak2breakpm23:30pm to 5:00pmpm35:00pm to 5:30pmeveningEvening HM1Hotel, Mezzanine 1HM2Hotel, Mezzanine 2CC1Conference Centre, Level 1CC2Conference Centre, Level 2 vanhorneVanHorneCC2hybrid832shaughnShaughnessyCC2classroom90beattyBeattyCC2classroom90colemanColemanCC2classroom90theatreTheatreCC1theatre252mtstephenMt StephenHM1rounds150petrakPetrakHM2rounds45newbrunswickNew BrunswickHM2classroom112albertaAlbertaHM2classroom176cascadeCascadeHM2classroom300oakOakHM1?32-50norquayNorquayHM1?32-50frontenacFrontenacHM1?24-40champlainChamplainHM1?40-50mckenzieMcKenzieHM1?20-40palliserPalliserHM1?24-40empressEmpressHM1?16-28lacombeLacombeHM1?12-28alhambraAlhambraHM2rounds200grizzlyGrizzly HouseOffsiterestaurant60 W3CACW3C AC MeetingYellowW4AW4A ConferenceAquamarinewowWorld Organization of WebmastersOrangetutorialTutorialsPinkworkshopWorkshopsLightCoralplenaryPlenariesAquapaperRefereed PapersLightSkyBluepanelPanelsTurquoisepostersPostersLightCyansponsoredSponsored TalksPaleGoldenroddevelDevelopers TrackMediumSpringGreenW3CW3C TrackSalmonhistoryWeb History TrackMediumSlateBluemuseumWeb History DisplaySilverexhibitionSponsor ExhibitionVioletbofBOFsFuchsiamiscMiscellaneousWhiteSmoke mtstephensunW3CAC6:30pm to 9:30pm0W3C AC ReceptioneveningcascadesunW3CACOrientation for new members0W3C AC Meetingpm1pm2alhambramonW3CAC0W3C AC LunchlunchcascademonW3CAC(Day 1 of 2)0W3C AC Meetingam1am2pm1pm2albertamonwowhttp://www2007.org/wow.phpCurrent Best Practices in Web Development and Design Tutorial (with WOW Web Professional Certification Exam Option)0World Organization of Webmasters (WOW)am1am2pm1pm2albertamonwow(Petrak or Riverview Lounge)0WOW LunchlunchnewbrunswickmonW4Ahttp://www.w4a.info/(Day 1 of 2)0Web Accessibility (W4A) Conferenceam1am2pm1pm2newbrunswickmonW4A0W4A LunchlunchgrizzlymonW4AOffsite at Grizzly House, 6:00pm to 8:00pm0W4A Banqueteveningempresstuetutorialhttp://www2007.org/tutorial-T0.php(Full-day tutorial)0Robust Management of Web and Grid Ontologies and MetadataT0tutorialam1am2pm1pm2shaughntueworkshophttp://www2007.org/workshop-W1.php(Full-day workshop)0AIRWeb 2007: Adversarial Information Retrieval on the WebW1workshopam1am2pm1pm2frontenactueworkshophttp://www2007.org/workshop-W2.php(Full-day workshop)0Health Care and Life Sciences Data Integration for the Semantic WebW2workshopam1am2pm1pm2mckenzietueworkshophttp://www2007.org/workshop-W3.php(Full-day workshop)0I3: Identity, Identifiers, Identifications -- Entity-Centric Approaches to Information and Knowledge Management on the WebW3workshopam1am2pm1pm2newbrunswicktueW4Ahttp://www.w4a.info/(Day 2 of 2)0Web Accessibility (W4A) Conferenceam1am2pm1pm2pallisertueworkshophttp://www2007.org/workshop-W5.php(Full-day workshop)0MobEA V: Mobile Web in the Developing WorldW5workshopam1am2pm1pm2cascadetueW3CAC(Day 2 of 2)0W3C AC Meetingam1am2pm1pm2beattytueworkshophttp://www2007.org/workshop-W6.php(Full-day workshop)0Query Log Analysis: Social and Technological ChallengesW6workshopam1am2pm1pm2albertatueworkshophttp://www2007.org/workshop-W7.php(Full-day workshop)0Social and Collaborative Construction of Structured KnowledgeW7workshopam1am2pm1pm2champlaintueworkshophttp://www2007.org/workshop-W8.php(Full-day workshop)0Sponsored Search AuctionsW9workshopam1am2pm1pm2colemantueworkshophttp://www2007.org/workshop-W9.php(Full-day workshop)0Tagging and Metadata for Social Information OrganizationW8workshopam1am2pm1pm2theatretuetutorialhttp://www2007.org/tutorial-T1.php(Half-day tutorial)0Foundations and Challenges of Web AdvertisingT1tutorialam1am2theatretuetutorialhttp://www2007.org/tutorial-T5.php(Half-day tutorial)0Learning to Rank in Vector Spaces and Social NetworksT5tutorialpm1pm2oaktuetutorialhttp://www2007.org/tutorial-T2.php(Half-day tutorial)0User-Centric Identity for Web ApplicationsT2tutorialam1am2oaktuetutorialhttp://www2007.org/tutorial-T6.php(Half-day tutorial)0An Integrated Approach to Evaluating Web Accessibility: Automated, Manual and User-based TestingT6tutorialpm1pm2lacombetuetutorialhttp://www2007.org/tutorial-T3.php(Half-day tutorial)0Cost-Effective Engineering of Web Application Product Lines (Reuse Beyond Components: Exploiting Similarity Patterns)T3tutorialam1am2norquaytuetutorialhttp://www2007.org/tutorial-T7.php(Half-day tutorial)0Deploying Web-scale Mash-ups by Linking Microformats and the Semantic WebT7tutorialpm1pm2norquaytuetutorialhttp://www2007.org/tutorial-T4.php(Half-day tutorial)0Next Generation Web Services in PracticeT4tutorialam1am2lacombetuetutorialhttp://www2007.org/tutorial-T8.php(Half-day tutorial)0Web Workloads: Characterization, Modeling and ApplicationT8tutorialpm1pm2albertatuehistoryhttp://www2007.org/webhistory.php(5:00pm to 8:00pm, starting in Riverview Lounge)1Web History Receptioneveningvanhornewedplenaryhttp://www2007.org/berners-lee.phpThe Two Magics of Web Science (Van Horne Ballroom)1WWW2007 Opening Ceremonies and Plenary Speaker: Tim Berners-Lee (MIT/W3C)am1vanhornewedexhibition(Van Horne C)0Sponsor Exhibition Hallam2pm1pm2vanhornethuexhibition(Van Horne C)0Sponsor Exhibition Hallam2pm1pm2vanhornefriexhibition(Van Horne C)0Sponsor Exhibition Hallam2pm1pm2petrakwedmuseumExhibit0Web History Displayam2pm1pm2petrakthumuseumExhibit0Web History Displayam2pm1pm2petrakfrimuseumExhibit0Web History Displayam2pm1pm2petraksatmuseumExhibit0Web History Displayam2pm1pm2shaughnwedhistoryhttp://www2007.org/webhistory.phpPioneers of the Web and E-Commerce0Web History Trackam2pm1pm2vanhornewedmisc(Van Horne Ballroom and Foyer, 6:00pm to 8:00pm)1WWW2007 Welcome Receptioneveningbeattywedpaper1 of 2 (Communication in Developing Regions)0Technology for Developing Regionspapersam2beattywedpaper2 of 2 (Networking Issues in the Web)0Technology for Developing Regionspaperspm2colemanwedpanelhttp://www2007.org/panel1.phpPhillip Hallam-Baker (Verisign)0Web Sciencepanelam2beattywedpanelhttp://www2007.org/panel2.phpAmit Nanavati (IBM India)0Web Delivery Models for Developing Regionspanelpm1colemanwedtutorialhttp://www2007.org/tutorial-T9.php(Half-day tutorial)0Semantic Digital LibrariesT9tutorialpm1pm2theatrewedsponsoredhttp://www2007.org/industrytopic1.phpSearch and Data0Industry Talkspm1newbrunswickwedpaper1 of 2 (Querying and Transforming XML)0XML and Web Datapapersam2newbrunswickthupaper2 of 2 (Parsing, Normalizing, and Storing XML)0XML and Web Datapapersam2newbrunswickwedpaper1 of 2 (Personalization)0Browsers and User Interfacespaperspm1newbrunswickwedpaper2 of 2 (Smarter Browsing)0Browsers and User Interfacespaperspm2albertawedpaper1 of 7 (Search Potpourri)0Searchpapersam2albertawedpaper2 of 7 (Crawlers)0Searchpaperspm1albertawedpaper3 of 7 (Web Graphs)0Searchpaperspm2cascadewedW3Chttp://www2007.org/prog-W3CTrack.php#wednesdayMaking Mobile Web Browsing Better0W3C Trackam2cascadewedW3Chttp://www2007.org/prog-W3CTrack.php#wednesdayRich Web Applications0W3C Trackpm1cascadewedW3Chttp://www2007.org/prog-W3CTrack.php#wednesdayThe Future of the Web Page0W3C Trackpm2vanhornethuplenaryhttp://www2007.org/raghavan.phpWeb N.0: What sciences will it take? (Van Horne Ballroom)1WWW2007 Announcements and Plenary Speaker: Prabhakar Raghavan (Yahoo! Research)am1vanhornethumisc(offsite at Brewster's MountView Barbecue; bus transportation provided)1WWW2007 Banquet (6:00pm to 9:00pm)eveningshaughnthupaper1 of 2 (Scalable Systems for Dynamic Content)0Performance and Scalabilitypapersam2beattythupaper1 of 1 (Pervasive Web and Mobility)0Pervasive Web and Mobilitypapersam2newbrunswickthupaper1 of 1 (IPE)0Industrial Practice and Experiencepaperspm1colemanthudevelhttp://www2007.org/panel7.phpPaul Miller (Talis)0Semantic Web with Datapanelam2shaughnthupanelhttp://www2007.org/panel3.phpArun Iyengar (IBM Research)0Performance and Scalabilitypanelpm1shaughnthupaper2 of 2 (Performance Engineering of Web Applications)0Performance and Scalabilitypaperspm2beattythututorialhttp://www2007.org/tutorial-T10.php(Half-day tutorial)0Model Driven Semantic Web EngineeringT10tutorialpm1pm2colemanthudevelhttp://www2007.org/prog-Developers.php#thursdayProgramming the Web0Developers Trackpm1colemanthudevelhttp://www2007.org/prog-Developers.php#thursdayWeb Tools0Developers Trackpm2theatrethusponsoredhttp://www2007.org/industrytopic7.phpWeb Search0Industry Talksam2theatrethusponsoredhttp://www2007.org/industrytopic2.phpMobile Web and Ajax0Industry Panelpm1albertathupaper1 of 5 (Identifying Structure in Web Pages)0Data Miningpapersam2albertathupaper2 of 5 (Mining Textual Data)0Data Miningpaperspm1cascadethuW3Chttp://www2007.org/prog-W3CTrack.php#thursdayAdvances in Semantic Web0W3C Trackam2cascadethuW3Chttp://www2007.org/prog-W3CTrack.php#thursdayWeb of Services for Enterprise Computing0W3C Trackpm2cascadethuW3Chttp://www2007.org/prog-W3CTrack.php#thursdaySecurity and Usability on the Web0W3C Trackpm1vanhornefriplenaryhttp://www2007.org/buxton.phpDesign for the World Narrow Web (Van Horne Ballroom)1WWW2007 Announcements and Plenary Speaker: Bill Buxton (Microsoft Research/University of Toronto)am1shaughnfripaper1 of 2 (Web Modeling)0Web Engineeringpapersam2shaughnfripaper2 of 2 (End-User Perspective and Measurement in Web Engineering)0Web Engineeringpaperspm1beattyfripaper1 of 2 (Orchestration and Choreography)0Web Servicespaperspm1shaughnfripaper1 of 3 (Defending Against Emerging Threats)0Security, Privacy, Reliability, and Ethicspaperspm2shaughnfripaper(Defending Against Emerging Threats)(cont'd)0Security, Privacy, Reliability, and Ethicspaperspm3beattyfripaper2 of 2 (SLAs and QoS)0Web Servicespaperspm2beattyfripaper(SLAs and QoS) (cont'd)0Web Servicespaperspm3colemanfridevelhttp://www2007.org/prog-Developers.php#fridayLinked Data0Developers Trackam2colemanfritutorialhttp://www2007.org/tutorial-T11.php(Half-day tutorial)0Semantic Web: Technologies and Applications for the Real-WorldT11tutorialpm1pm2theatrefrisponsoredhttp://www2007.org/industrytopic3.phpWeb and Patents0Industry Talksam2theatrefridevelhttp://www2007.org/prog-Developers.php#fridayEmerging Web Platforms0Developers Trackpm1theatrefridevelhttp://www2007.org/prog-Developers.php#fridayNext Generation Web Servers0Developers Trackpm2newbrunswickfripaper1 of 5 (Applications)0Semantic Webpapersam2newbrunswickfripaper2 of 5 (Similarity and Extraction)0Semantic Webpaperspm1newbrunswickfripaper3 of 5 (Query Languages and DBs)0Semantic Webpaperspm2newbrunswickfripaper(Query Languages and DBs) (cont'd)0Semantic Webpaperspm3albertathupaper4 of 7 (Search Quality and Precision)0Searchpaperspm2albertafripaper5 of 7 (Advertisements and Click Estimates)0Searchpaperspm1albertafripaper6 of 7 (Knowledge Discovery)0Searchpaperspm2albertasatpaper7 of 7 (Personalization)0Searchpapersam2albertafripaper3 of 5 (Similarity Search)0Data Miningpapersam2cascadefriW3Chttp://www2007.org/prog-W3CTrack.php#fridayA Multimodal Web to Expand Universal Access0W3C Trackam2cascadefriW3Chttp://www2007.org/prog-W3CTrack.php#fridayArchitectural Integration0W3C Trackpm1cascadefriW3Chttp://www2007.org/prog-W3CTrack.php#fridayQuery, Interchange, and Access with XML!0W3C Trackpm2vanhornesatplenaryhttp://www2007.org/hardt.phpAn Identity Story (Van Horne Ballroom)1WWW2007 Announcements and Plenary Speaker: Dick Hardt (SXIP Identity)am1vanhornesatmisc5:00pm to 5:30pm1WWW2007 Closing Ceremonyeveningalbertasatpaper4 of 5 (Predictive Modeling of Web Users)0Data Miningpaperspm1albertasatpaper5 of 5 (Mining in Social Networks)0Data Miningpaperspm2colemansatdevelhttp://www2007.org/prog-Developers.php#saturdayWeb Data 10Developers Trackam2colemansatdevelhttp://www2007.org/prog-Developers.php#saturdayWeb Data 20Developers Trackpm1colemansatdevel0Cancelledpm2theatresatsponsoredhttp://www2007.org/industrytopic4.phpWeb Enterprises0Industry Talksam2theatresatsponsoredhttp://www2007.org/industrytopic5.phpSocial Computing0Industry Panelpm1theatresatsponsoredhttp://www2007.org/industrytopic6.phpNew Web-based Business Models: Money or Meaning?0Industry Panelpm2beattysatpaper1 of 2 (E-Communities)0E* Applicationspapersam2beattysatpaper2 of 2 (E-Commerce and E-Content)0E* Applicationspaperspm1theatrethupanelhttp://www2007.org/panel5.phpGreg Conti (USMA)0Web Search Privacy Issuespanelpm2newbrunswickthupanelhttp://www2007.org/panel4.phpSusan Boll (U. Oldenburg) and Raphael Troncy (CWI)0Multimedia Metadata Standards in Semantic Webpanelpm2beattyfripanelhttp://www2007.org/panel6.phpYoelle Marek (Google, Israel)0Searching Personal Contentpanelam2shaughnsatpaper4 of 5 (Ontologies)0Semantic Webpapersam2shaughnsatpaper5 of 5 (Semantic Web and Web 2.0)0Semantic Webpaperspm1newbrunswicksatpaper2 of 3 (Passwords and Phishing)0Security, Privacy, Reliability, and Ethicspapersam2shaughnsatpaper3 of 3 (Access Control and Trust on the Web)0Security, Privacy, Reliability, and Ethicspaperspm2newbrunswicksatbofhttp://www2007.org/bof1.phpThe WWW and China0Birds of a Feather (BOF) Session 1 of 2pm1newbrunswicksatbofhttp://www2007.org/bof2.phpTopic TBD0Birds of a Feather (BOF) Session 2 of 2pm2beattysatmisc0Cancelledpm2 15The World Wide Web (WWW) is rapidly becoming important for society as a medium for sharing data, information and services, and there is a growing interest in tools for understanding collective behaviors and emerging phenomena in the WWW. In this paper we focus on the problem of searching and classifying {\em communities} in the web. Loosely speaking a community is a group of pages related to a common interest. More formally communities have been associated in the computer science literature with the existence of a locally dense sub-graph of the web-graph (where web pages are nodes and hyper-links are arcs of the web-graph). The core of our contribution is a new scalable algorithm for finding relatively dense subgraphs in massive graphs. We apply our algorithm on web-graphs built on three publicly available large crawls of the web (with raw sizes up to 120M nodes and 1G arcs). The effectiveness of our algorithm in finding dense subgraphs is demonstrated experimentally by embedding artificial communities in the web-graph and counting how many of these are blindly found. Effectiveness increases with the size and density of the communities: it is close to 100\% for communities of a thirty nodes or more (even at low density). It is still about 80\% even for communities of twenty nodes with density over $50\%$ of the arcs present. At the lower extremes the algorithm catches 35\% of dense communities made of ten nodes. We complete our Community Watch system by clustering the communities found in the web-graph into homogeneous groups by topic and labelling each group by representative keywords.Yon DourisboureInstitute for Informatics and Telematics of C.N.R.Filippo GeraciInstitute for Informatics and Telematics of C.N.R.Marco PellegriniInstitute for Informatics and Telematics of C.N.R.56Metrics such as click counts are vital to online businesses but their measurement has been problematic due to inclusion of high variance robot traffic. We posit that by applying statistical methods more rigorous than have been employed to date that we can build a robust model of the distribution of clicks following which we can set probabilistically sound thresholds to address outliers and robots. Prior research in this domain has used inappropriate statistical methodology to model distributions and current industrial practice eschews this research for conservative ad-hoc click-level thresholds. Prevailing belief is that such distributions are scale-free power law distributions but using more rigorous statistical methods we find the best description of the data is instead provided by a scale-sensitive Zipf-Mandelbrot mixture distribution. Our results are based on ten datasets from various verticals in the Yahoo domain. Since mixture models can overfit the data we take care to use the BIC log-likelihood method which penalizes overly complex models. Using a mixture model in the web activity domain makes sense because there are likely multiple classes of users. In particular, we have noticed that there is a significantly large set of ``users'' that visit the Yahoo portal exactly once a day. We surmise these may be robots testing internet connectivity by pinging the Yahoo main website.<br /><br /> Backing up our quantitative analysis is graphical analysis in which empirical distributions are plotted against theoretical distributions in log-log space using robust cumulative distribution plots. This methodology has two advantages: plotting in log-log space allows one to visually differentiate the various exponential distributions and secondly, cumulative plots are much more robust to outliers. We plan to use the results of this work for applications for robot removal from web metrics business intelligence systems.Kamal AliYahooMark ScarrYahoo57Automated matching of semantic service descriptions is the key to automatic service discovery and binding. But when trying to find a match for a certain request it may often happen, that the request cannot be serviced by a single offer but could be handled by combining existing offers. In this case automatic service composition is needed. Although automatic composition is an active field of research it is mainly viewed as a planning problem and treated separatedly from service discovery. In this paper we argue that an integrated approach to the problem is better than seperating these issues as is usually done. We propose an approach that integrates service composition into service discovery and matchmaking to match service requests that ask for multiple connected effects, discuss general issues involved in describing and matching such services and present an efficient algorithm implementing our ideas.Ulrich KuesterFriedrich Schiller University JenaBirgitta Koenig-RiesFriedrich-Schillder-University JenaMirco SternUniversitaet KarlsruheMichael KleinUniversitaet Karlsruhe58Finding relationships between entities on the Web, e.g., the connections between different places or the commonalities of people, is a novel and challenging problem. Existing Web search engines excel in keyword matching and document ranking, but they cannot well handle many relationship queries. This paper proposes a new method for answering relationship queries on two entities. Our method first respectively retrieves the top Web pages for either entity from a Web search engine. It then matches these Web pages and generates an ordered list of Web page pairs. Each Web page pair consists of one Web page for either entity. The top ranked Web page pairs are likely to contain the relationships between the two entities. One main challenge in the ranking process is to effectively filter out the large amount of noise in the Web pages without losing much useful information. To achieve this, our method assigns appropriate weights to terms in Web pages and intelligently identifies the potential connecting terms that capture the relationships between the two entities. Only those top potential connecting terms with large weights are used to rank Web page pairs. Finally, the top ranked Web page pairs are presented to the searcher. For each such pair, the query terms and the top potential connecting terms are properly highlighted so that the relationships between the two entities can be easily identified. We implemented a prototype on top of the Google search engine and evaluated it under a wide variety of query scenarios. The experimental results show that our method is effective at finding important relationships with low overhead.Gang LuoIBM T.J. Watson Research CenterChunqiang TangIBM T.J. Watson Research CenterYing-li TianIBM T.J. Watson Research Center67Schema statements in OWL are interpreted in a different way from similar statements in a relational database setting. This can lead to problems in data-centric applications, where OWL's interpretation of the statements intended as constraints may be confusing and/or inappropriate. We propose an extension of OWL that attempts to mimic the intuition behind integrity constraints in relational databases. We discuss the algorithms for checking constraint satisfaction for different types of knowledge bases, and show that, provided the constraints are satisfied, we can disregard them while answering a broad range of positive queries.Boris MotikUniversity of ManchesterIan HorrocksUniversity of ManchesterUlrike SattlerUniversity of Manchester70Click fraud is jeopardizing the industry of Internet advertising. Internet advertising is crucial for the thriving of the entire Internet, since it allows producers to advertise their products, and hence contributes to the well being of e-commerce. Moreover, advertising supports the intellectual value of the Internet by covering the running expenses of the content publishers' sites. Some publishers are dishonest, and use automation to generate traffic to defraud the advertisers. Similarly, some advertisers automate clicks on the advertisements of their competitors to deplete their competitors' advertising budgets. This paper describes the advertising network model, and focuses on the most sophisticated type of fraud, which involves coalitions among fraudsters. We build on several published theoretical results to devise the Similarity-Seeker algorithm that discovers coalitions made by pairs of fraudsters. We then generalize the solution to coalitions of arbitrary sizes. Before deploying our system on a real network, we conducted comprehensive experiments on data samples for proof of concept. We detected numerous coalitions that span numerous sites. Interestingly, 93% of the discovered sites were real fraudsters.Ahmed MetwallyUniversity of California, Santa BarbaraDivyakant AgrawalUniversity of California, Santa BarbaraAmr El AbbadiUniversity of California, Santa Barbara89We consider the problem of online keyword advertising auctions among multiple bidders with limited budgets, and study a natural bidding heuristic in which advertisers attempt to optimize their utility by equalizing their return-on-investment across all keywords. We show that existing auction mechanisms combined with this heuristic can experience cycling (as has been observed in many current systems), and therefore propose a modified class of mechanisms with small random perturbations. This perturbation is reminiscent of the small time-dependent perturbations employed in the dynamical systems literature to convert many types of chaos into attracting motions. We show that the perturbed mechanism provably converges in the case of first-price auctions and experimentally converges in the case of second-price auctions. Moreover, the point of convergence has a natural economic interpretation as the unique market equilibrium in the case of first-price mechanisms. In the case of second-price auctions, we conjecture that it converges to the ``supply-aware'' market equilibrium. Thus, our results can be alternatively described as a tatonnement process for convergence to market equilibrium in which prices are adjusted on the side of the buyers rather than the sellers. We also observe that perturbation in mechanism design is useful in a broader context: In general, it can allow bidders to ``share'' a particular item, leading to stable allocations and pricing for the bidders, and improved revenue for the auctioneer.Christian BorgsMicrosoft ResearchJennifer ChayesMicrosoft ResearchOmid EtesamiU.C. BerkeleyNicole ImmorlicaMicrosoft ResearchKamal JainMicrosoft ResearchMohammad MahdianYahoo! Research91In this paper, we propose a new similarity measure to compute the pairwise similarity of text-based documents based on suffix tree document model. By applying the new suffix tree similarity measure in Group-average Agglomerative Hierarchical Clustering (GAHC) algorithm, we developed a new suffix tree document clustering algorithm (NSTC). Our experimental results on two standard document clustering benchmark corpus OHSUMED and RCV1 indicate that the new clustering algorithm is a very effective document clustering algorithm. Comparing with the results of traditional keyword tfidf similarity measure in the same GHAC algorithm, NSTC achieved an improvement of 51% on the average of F-measure score. Furthermore, we apply the new clustering algorithm in analyzing the Web documents in online forum communities. A topic oriented clustering algorithm is developed to help people in assessing, classifying and searching the the Web documents in a large forum community.Hung ChimCity University of Hong KongXiaotie DengCity University of Hong Kong100Often scientists seek to search for articles on the Web related to a particular chemical. When a scientist searches for a chemical formula using a search engine today, she gets back articles where the exact keyword string expressing the chemical formula is found. Searching for the exact occurrence of keywords while searching results in two problems for this domain: a) if the author searches for CH4 and the article has H4C, the article is not returned, and b) ambiguous searches like "He" return all documents where Helium is mentioned as well as documents where the pronoun "he" occurs. To remedy these deficiencies, we propose a chemical formula search engine. To build a chemical formula search engine, we must solve the following problems: (1) extract chemical formulae from text documents, (2) index chemical formulae, and (3) design a ranking function for articles where the chemical formulae occur. Furthermore, query models are introduced for formula search, and for each a scoring scheme based on features of partial formulae is proposed to measure the relevance of chemical formulae and queries. We evaluate algorithms for identifying chemical formulae in documents using a classification method based on Support Vector Machines (SVM), and a probabilistic model based on conditional random fields (CRF). Different methods for SVM and CRF to tune the trade-off between recall and precision for imbalanced data are proposed to improve the over-all performance. A feature selection method based on frequency and discrimination is used to remove uninformative and redundant features. Experiments show that our approaches of chemical formula extraction work well, especially after trade-off tuning. The results also demonstrate that feature selection can reduce the index size without changing the ranked query results much.Bingjun SunPennsylvania State UniversityQingzhao TanPennsylvania State UniversityPrasenjit MitraPennsylvania State UniversityC. Lee GilesPennsylvania State University111Spammers use questionable search engine optimization (SEO) techniques to promote their spam links into top search results. In this paper, we focus on one prevalent type of spam - redirection spam - where one can identify spam pages by the third-party domains that these pages redirect traffic to. We propose a five-layer, double-funnel model for describing end-to-end redirection spam, present a methodology for analyzing the layers, and identify prominent domains on each layer using two sets of commercial keywords - one targeting spammers and the other targeting advertisers. The methodology and findings are useful for search engines to strengthen their ranking algorithms against spam, for legitimate website owners to locate and remove spam doorway pages, and for legitimate advertisers to identify unscrupulous syndicators who serve ads on spam pages.Yi-Min WangMicrosoft ResearchMing MaMicrosoft ResearchYuan NiuUC DavisHao ChenUC Davis120With the growing use of dynamic web content generated from relational databases, traditional caching solutions for throughput and latency improvements are ineffective. We describe a middleware layer called Ganesh that reduces the volume of data transmitted without semantic interpretation of queries or results. It achieves this reduction through the use of cryptographic hashing to detect similarities with previous results. These benefits do not require any compromise of the strict consistency semantics provided by the back-end database. Further, Ganesh does not require modifications to applications, web servers, or database servers, and works with closed-source applications and databases. Using two benchmarks representative of dynamic web sites, measurements of our prototype show that it can increase end-to-end throughput by as much as twofold for non-data intensive applications and by as much as tenfold for data intensive ones.Niraj ToliaCarnegie Mellon UniversityM. SatyanarayananCarnegie Mellon University127This paper is based on our exploratory study of a South Indian village in Chamrajanagar district of Karnataka. The study was to understand the rural communication environment and villagers' communication preferences. We examined people's lifestyle, working conditions and their communication eco-system. Our study revealed that villagers, unlike urban inhabitants, interacted with people outside the village only for specific, rather than casual purposes. Another interesting aspect of rural communication was the marginal use of the postal system and the ubiquitous use of pay phone, apart from word of mouth and face-to-face interactions. In fact, personal (face-to-face) interaction was usually preferred among villages in this region, over other kinds of communication, despite infrastructural constraints like poor transport services.<br /><br /> We also observed that communication frequency increased when status quo changed to one that required immediate attention. During the analysis we identified certain social, economic and cultural communication gaps (or problems). However, these problems were clear opportunities to connect the unconnected rural users, by deploying new communication systems and features. Here, we have highlighted some of our findings and possible design avenues based on these findings.Sarita SeshagiriMotorola India Research LabsAman SagarMotorola India Research LabsDhaval JoshiMotorola India Research Labs140Cryptographic protocols are useful for trust engineering in Web transactions. The Cryptographic Protocol Programming Language (CPPL) provides a model wherein trust management annotations are attached to protocol actions, and are used to constrain the behavior of a protocol participant to be compatible with its own trust policy.<br /><br /> The first implementation of CPPL generated stand-alone, single-session servers, making it unsuitable for deploying protocols on the Web. We describe a new compiler that uses a constraint-based analysis to produce multi-session server programs. The resulting programs run without persistent TCP connections for deployment on traditional Web servers. Most importantly, the compiler preserves existing proofs about the protocols. We present an enhanced version of the CPPL language, discuss the generation and use of constraints, show their use in the compiler, formalize the preservation of properties, present subtleties, and outline implementation details.Jay McCarthyBrown UniversityJoshua D. GuttmanMITRE CorporationJohn D. RamsdellMITRE CorporationShriram KrishnamurthiBrown University145Given a set of machines and a set ofWeb applications with dynamically changing demands, an application placement controller decides how many instances to run for each application and where to put them, while observing all kinds of resource constraints. This problem is NP hard. In this paper, we propose an online algorithm that uses heuristics to efficiently solve this problem. It allows multiple applications to share a single machine, and strives to maximize the total satisfied application demand, to minimize the number of application starts and stops, and to balance the load across machines. It can produce within 30 seconds high-quality solutions for hard placement problems with thousands of machines and thousands of applications. This scalability is crucial for dynamic resource provisioning in large-scale enterprise data centers. Our algorithm significantly and consistently outperforms the existing state-of-the-art algorithm under a wide variety of workloads.Chunqiang TangIBM T.J. Watson Research CenterMalgorzata SteinderIBM ResearchMichael SpreitzerIBM ResearchGiovanni PacificiIBM Research158Digital media companies have recently started embracing P2P networks as an alternative content distribution channel. However, the drawback of the current {\em P2P swarming} systems is that users need to download the full video and, hence, wait a long time before they can start watching it. While a lot of effort has gone into optimizing the distribution of large files, little research has been done on how to enable high-quality Video-on-Demand (VoD) functionality with P2P swarming systems. The main challenges reside in ensuring that users can start watching a movie at any point in time, while providing small start-up times, sustainable playback rates and high swarming efficiencies.<br /><br /> In this work, we explore the feasibility of providing high-quality VoD using P2P mesh-based networks. To this extent, we investigate scheduling and pre-fetching techniques, network coding, and mesh topology management. Using both simulations and results from a real implementation, we provide evidence that high-quality VoD is feasible, and give guidelines to enable play-as-you-download P2P swarming systems with high playback rates and minimum start-up delays.Siddhartha AnnapureddyNew York UniversitySaikat GuhaCornell UniversityDinan GunawardenaMicrosoft ResearchChristos GkantsidisMicrosoft ResearchPablo RodriguezTelefonica Research161It is no surprise that Semantic Web researchers and enthusiasts are excited to publish and accumulate semi-structured data on the Web. But looking beyond our community, we recognize that many, many other people also have structured data and want to publish it in rich browsing interfaces. These small-time authors fall into the same category as those early enthusiasts of the Web who were simply excited by the opportunity of using the new medium to share information that they cared about. With this insight, we create a lightweight structured data publishing framework called Exhibit that duplicates many factors we believe have contributed to the original growth of the Web. We argue that appealing to this segment of the Web population--addressing their publishing needs and desires at very low cost in many aspects--lets us leverage their labor to structure-ize existing content on the Web that has previously been authored in HTML by hand and is remaining hard to harvest automatically.David HuynhMIT CSAILDavid KargerMIT CSAILRob MillerMIT162Users searching for information in hypermedia environments often perform querying followed by manual navigation. Yet, the conventional text/hypertext retrieval paradigm does not explicity take post-query navigation into account. This paper proposes a new retrieval paradigm, called navigation-aided retrieval (NAR), which treats both querying and navigation as first-class activities. In the NAR paradigm, querying is seen as a means to identify starting points for navigation, and navigation is guided based on information supplied in the query. NAR is a generalization of the conventional probabilistic information retrieval paradigm, which implicitly assumes no navigation takes place.<br /><br /> This paper presents a formal model for navigation-aided retrieval, and reports empirical results that point to the real-world applicability of the model. The experiments were performed over a large Web corpus provided by TREC, using human judgments on a new rating scale developed for navigation-aided retrieval. In the case of ambiguous queries, the new retrieval model identifies good starting points for post-query navigation. For less ambiguous queries that need not be paired with navigation, the output closely matches that of a conventional retrieval system.Shashank PanditCarnegie Mellon UniversityChristopher OlstonYahoo! Research190Portlets strive to play at the front end the same role that Web services currently enjoy at the back end, namely, enablers of application assembly through reusable services. However, it is well-known in the component community that, the larger the component, the more reduced the reuse. Hence, the coarse-grained nature of portlets (they encapsulate also the presentation layer) can jeopardize this vision of portlets as reusable services. To avoid this situation, this work proposes a perspective shift in portlet development by introducing the notion of organization profile. While the user profile characterises the end user (e.g. age, name, etc), the organization profile captures the idiosyncrasies of the organization through which the portlet is being delivered (e.g. the portal owner) as far as the portlet functionality is concerned. The user profile is dynamic and hence, requires the portlet to be customised at run time. By contrast, the organization profile is known at registration time, and it is not always appropriate/possible to consider it at run time. Rather, it is better to customize the code at development time, and produce an organization-specific portlet which built-in, custom functionality. In this scenario, we no longer have a portlet but a family of portlets, and the portlet provider becomes the "assembly line" of this family. This work promotes this vision by introduces an organization-aware, WSRP-compliant architecture that let portlet consumers registry and handle "family portlets" in the same way that "traditional portlets". In so doing, portlets are nearer to become truly reusable services.Oscar DiazUniversity of the Basque CountrySalvador TrujilloUniversity of the Basque CountrySandy PerezUniversity of the Basque Country194We consider the problem of DUST: Different URLs with Similar Text. Such duplicate URLs are prevalent in web sites, as web server software often uses aliases and redirections, and dynamically generates the same page from various different URL requests. We present a novel algorithm, DustBuster, for uncovering DUST; that is, for discovering rules that transform a given URL to others that are likely to have similar content. DustBuster mines DUST effectively from previous crawl logs or web server logs, without examining page contents. Verifying these rules via sampling requires fetching few actual web pages. Search engines can benefit from information about DUST to increase the effectiveness of crawling, reduce indexing overhead, and improve the quality of popularity statistics such as PageRank.Ziv Bar-YossefTechnion - Israel Institute of Technology and Google HaifaIdit KeidarTechnion - Israel Institute of TechnologyUri SchonfeldUniversity of California Los Angeles200With the growth of interest on the web services, people pay more and more attention to choreography, that is, to describe collaborations of participants from a global viewpoint, in accomplishing a common business goal. In this paper, based on a simple choreography languages and a role-oriented process languages, we study some fundamental issues related to choreography, especially related to implementation, including semantics, projection and natural projection, dominant role in choices and iterations, etc. We develop the concept of \emph{dominant role} and propose some novel languages structures related to it. The study reveals some clues about the language, semantics, specification and implementation of choreography.Zongyan QiuPeking UniversityXiangpeng ZhaoPeking UniversityChao CaiPeking UniversityHongli YangPeking University207Given a large online network of online auction uesrs and their histories of transactions, how can we spot anomalies, or even auction fraud? We describe the algorithms and system design decisions behind our proposed NetProbe system for uncovering auction fraud. We show that it is possible to do fast and scalable fraud detection, in large auction networks. The main idea is to use the machinery of "Markov Random Fields" (MRF), and try to guess the hidden state (fraud/honest) of each participant. We describe the algorithms behind our system, that are based on "belief propagation"; we provide our own incremental but accurate approximations to it; and we list and justify our design decisions for efficient crawling of real auction networks. We report experiments on synthetic graphs containing as many as 7,000 nodes and 30,000 edges, where NetProbe was able to spot fraudulent nodes with over 90 % precision and recall, with execution times in the order of seconds. We also report experiments on a real graph consisting of about 700,000 transactions between more than 66,000 eBay users, where NetProbe was highly effective at unearthing hidden networks of fraudsters, within a realistic response time of about 6 minutes.Shashank PanditCarnegie Mellon UniversityDuen Horng ChauCarnegie Mellon UniversitySamuel WangCarnegie Mellon UniversityChristos FaloutsosCarnegie Mellon University215Near-duplicate documents are commonly found on the web. A pair of near-duplicate web pages differ from each other in a very small portion. The differences commonly consist of advertisements and timestamps. Such differences are irrelevant for web search. During web crawling, it is useful to quickly ascertain whether a newly crawled web page is a near-duplicate of a previously crawled web page or not.<br /><br /> In the course of developing a practical system for near-duplicate detection, we make two research contributions. First, we demonstrate the effectiveness of Charikar's fingerprinting technique for identifying near-duplicate web pages. We show that for 8 billion web-pages, a good choice of parameters is 64-bit fingerprints and 3-bit Hamming distances. Second, we present an algorithmic technique for identifying existing f-bit fingerprints that differ from a given fingerprint in at most k bit-positions, for small k. Our technique is useful for both online queries (single fingerprints) and batch queries (multiple fingerprints). Experimental evaluation over real data confirms the practicality of our design.Gurmeet MankuGoogle Inc.Arvind JainGoogle Inc.Anish Das SarmaStanford University216Continuous queries are used to monitor changes to time varying data and to provide results useful for online decision making. Typically a user desires to obtain the value of some aggregation function over distributed data items, for example, to know (a) the average of temperatures sensed by a set of sensors (b) the value of index of mid-cap stocks. In these queries a client specifies a coherency or accuracy requirement as part of the query. In this paper we present a low-cost, scalable technique to answer continuous aggregation queries using a content distribution network of dynamic data items. In such a network of data aggregators, each data aggregator serves a set of data items at specific coherencies. Just as various fragments of a dynamic web-page are served by one or more nodes of a CDN, our technique involves decomposing a client query into sub-queries and executing sub-queries on judiciously chosen data aggregators For executing an incoherency bounded continuous query, a query plan is required which includes the set of sub-queries, their individual incoherency bounds and data aggregators which can execute these sub-queries. An optimal query execution plan should satisfy client query's coherency requirement with least cost, measured in terms of the number of refresh messages sent from aggregators to the client. For estimating query execution cost, we build a continuous query cost model which can be used to estimate the number of messages required to satisfy the client specified incoherency bound. Performance results using real-world traces show that our cost based query planning leads to queries being executed using less than one third the number of messages required by existing schemes.Rajeev GuptaIBM India Research LabKrithi RamamrithamIIT Bombay223Nowadays, mobile users with positioning devices can access Location Based Services (LBS) and query about points of interest in their proximity. For such applications to succeed, privacy and confidentiality are essential. Encryption alone is not adequate; although it safeguards the system against eavesdroppers, the queries themselves may disclose the location and identity of the user. Recently, there have been proposed centralized architectures based on k-Anonymity, which utilize an intermediate anonymizer between the mobile users and the LBS. However, the anonymizer must be updated continuously with the current locations of all users. Moreover, the complete knowledge of the entire system poses a security threat, if the anonymizer is compromised.<br /><br /> In this paper we address two issues: (i) We show that existing approaches may fail to provide spatial anonymity for some distributions of user locations and describe a novel technique which solves this problem. (ii) We propose PRIVE, a decentralized architecture for preserving the anonymity of users issuing spatial queries to LBSs. Mobile users self-organize into an overlay network with good fault tolerance and load balancing properties. PRIVE avoids the bottleneck caused by centralized techniques both in terms of anonymization and location updates. Moreover, the status is distributed in numerous users, rendering the system resilient to attacks. Extensive experimental studies suggest that PRIVE is applicable to real-life scenarios with large populations of mobile users.Gabriel GhinitaNational University of SingaporePanos KalnisNational University of SingaporeSpiros SkiadopoulosUniversity of Peloponnese225Weblogs have become a prevalent source of information for people to express themselves. In general, there are two genres of contents in weblogs. The first kind is about the webloggers' personal feelings, thoughts or emotions. We call this kind of weblogs affective articles. A second kind of weblogs is about technologies and different kinds of informative news. In this paper, we present a machine learning method for classifying informative and affective articles among weblogs. We consider this problem as a binary classification problem. By using machine learning approaches, we achieve 92% on information retrieval performance measures including precision, recall and F1. We set up three studies on the applications of above classification approach in both research and industrial fields. We use the above classification approach to improve the performance of classification of emotions from weblog articles. We also develop an intent-driven weblog-search engine based on the classification techniques to improve the satisfaction of web users. Finally, we use above classification approach to search for weblogs with a great deal of informative articles.Xiaochuan NiDepartment of Computer Science and Engineering Shanghai Jiao-Tong UniversityGui-Rong XueShanghai Jiao-Tong UniversityXiao LingDepartment of Computer Science and Engineering Shanghai Jiao-Tong UniversityYong YuShanghai Jiao-Tong UniversityQiang YangHong Kong University of Science and Technology232In a social network, nodes correspond to people or other social entities, and edges correspond to social links between them. In an effort to preserve privacy, the practice of anonymization replaces names with meaningless unique identifiers. We describe a family of schemes such that even from a single anonymized copy of a social network, it is possible for an adversary to learn whether edges exist or not between specific targeted pairs of nodes.Lars BackstromCornell UniversityCynthia DworkMicrosoft ResearchJon KleinbergCornell University247Personalized web search is a promising way to improve search quality by customizing search results for people with individual information goals. However, users are uncomfortable with exposing private preference information to search engines. On the other hand, privacy is not absolute, and often can be compromised if there is a gain in service or profitability to the user. Thus, a balance must be struck between search quality and privacy protection. This paper presents a scalable way for users to automatically build rich user profiles. These profiles summarize a user's interests into a hierarchical organization according to specific interests. Two parameters for specifying privacy requirements are proposed to help the user to choose the content and degree of detail of the profile information that is exposed to the search engine. Experiments showed that the user profile improved search quality when compared to standard MSN rankings. More importantly, results verified our hypothesis that a significant improvement on search quality can be achieved by only sharing some higher-level user profile information, which is potentially less sensitive than detailed personal information.Yabo XuSimon Fraser UniversityBenyu ZhangMicrosoft Research AsiaZheng ChenMicrosoft Research AsiaKe WangSimon Fraser University272Object-oriented programming is the current mainstream programming paradigm but existing RDF APIs are mostly triple-oriented. Traditional techniques for bridging a similar gap between relational databases and object-oriented programs cannot be applied directly, given the different nature of Semantic Web data, as can for example be seen in the semantics of class membership, inheritance relations, and object conformance to schemas.<br /><br /> We present ActiveRDF, an object-oriented API for managing RDF data that offers full manipulation and querying of RDF data, does not rely on a schema and fully conforms to RDF(S) semantics. ActiveRDF can be used with different RDF data stores, adapters have been implemented to generic SPARQL endpoints, Sesame, Jena, Redland and YARS and new adapters can be added easily. In addition, integration with the popular Ruby on Rails framework enables fast development of Semantic Web applications.Eyal OrenDERI, National University of Ireland, GalwayRenaud DelbruDERI NUIGSebastian GerkeDERI NUIGArmin HallerDERI NUIGStefan DeckerDERI NUIG279Design principles for XML schemas that eliminate redundancies and avoid update anomalies have been studied recently. Several normal forms, generalizing those for relational databases, have been proposed. All of them, however, are based on the assumption of a native XML storage, while in practice most of XML data is stored in relational databases.<br /><br /> In this paper we study XML design and normalization for relational storage of XML documents. To be able to relate and compare XML and relational designs, we use an information-theoretic framework that measures information content in relations and documents, with higher values corresponding to lower levels of redundancy. We show that most common relational storage schemes preserve the notion of being well-designed (i.e., anomalies- and redundancy-free). Thus, existing XML normal forms guarantee well-designed relational storages as well. We further show that if this perfect option is not achievable, then a slight restriction on XML constraints guarantees a ``second-best'' relational design, according to possible values of the information-theoretic measure. We finally consider an edge-based relational representation of XML documents, and show that while it has similar information-theoretic properties with other relational representations, it can behave significantly worse in terms of enforcing integrity constraints.Solmaz KolahiUniversity of TorontoLeonid LibkinUniversity of Edinburgh286This paper is concerned with rank aggregation, the task of combining results of individual ranking functions in meta-search. Previously, rank aggregation was performed mainly by using unsupervised methods. It is hard for the unsupervised approach to improve ranking performances by leveraging the use of labeled data, when such data is available. We propose employing a supervised learning approach to perform the task, which we refer to as "Supervised Rank Aggregation". We set up a general framework for conducting rank aggregation with supervised learning, in which learning for rank aggregation is formalized as an optimization issue that minimizes disagreements with the labeled ground truth data. As case study, we focus on Markov Chain based rank aggregation in this paper. The optimization problem is not a convex optimization problem for Markov Chain based methods, however, and thus is hard to solve. We transform the optimization problem into semi-definite programming and give proofs on the correctness. Experimental results on meta-searches show that Supervised Rank Aggregation can significantly outperform existing unsupervised methods.Yu-Ting LiuMicrosoft Research Asia and Beijing Jiatong UniversityTie-Yan LiuMicrosoft Research AsiaTao QinTsinghua UniversityZhi-Ming MaChinese Academy of ScienceHang LiMicrosoft Research Asia287In this paper we present an application framework that leverages geospatial content on the World Wide Web by enabling innovative modes of interaction and novel types of user interfaces on advanced mobile phones and PDAs. We discuss the current development steps involved in building mobile geospatial Web applications and derive three technological pre-requisites for our framework: spatial query operations based on visibility and field of view, a 2.5D environment model, and a presentation-independent data exchange format for geospatial query results. We propose the Local Visibility Model as a suitable XML-based candidate and present a prototype implementation.Rainer SimonTelecommunications Research Center ViennaPeter FroehlichTelecommunications Research Center Vienna308Generic database replication algorithms do not scale linearly in throughput as they require to apply all update, deletion and insertion (UDI) queries to every database replica. The throughput is therefore limited to the point where the number of UDI queries alone is sufficient to overload one server. In such scenarios, partial replication of a database can help, as update queries are executed only by a subset of all servers. In this paper we propose GlobeTP, a system that employs partial replication to improve database throughput. GlobeTP exploits the fact that a Web application's query workload is composed of a small set of read and write templates. Using knowledge of these templates and their respective execution costs, GlobeTP provides database table placements that produce significant improvements in database throughput. We demonstrate the efficiency of this technique using two different industry standard benchmarks. In our experiments, GlobeTP increases the throughput by 57% to 150% compared to full replication, while using identical hardware configuration. Furthermore, adding a single query cache improves the throughput by another 30% to 60%.Tobias GroothuyseVrije Universiteit, AmsterdamSwaminathan SivasubramanianVrije Universiteit, AmsterdamGuillaume PierreVrije Universiteit, Amsterdam324Extractors and taggers turn unstructured text into entity-relation (ER) graphs where nodes are entities (email, paper, person, conference, company) and edges are relations (wrote, cited, works-for). Typed proximity search of the form type=person NEAR company~"IBM", paper~"XML" is an increasingly useful search paradigm in ER graphs. Proximity search implementations either perform a Pagerank-like computation at query time, which is slow, or precompute, store and combine per-word Pageranks, which can be very expensive in terms of preprocessing time and space. We present HubRank, a new system for fast, dynamic, space-efficient proximity searches in ER graphs. During preprocessing, HubRank computes and indexes certain "sketchy" random walk fingerprints for a small fraction of nodes, carefully chosen using query log statistics. At query time, a small "active" subgraph is identified, bordered by nodes with indexed fingerprints. These fingerprints are adaptively loaded to various resolutions to form approximate personalized Pagerank vectors (PPVs). PPVs at remaining active nodes are now computed iteratively. We report on experiments with CiteSeer's ER graph and millions of real CiteSeer queries. Some representative numbers follow. On our testbed, HubRank preprocesses and indexes 52 times faster than whole-vocabulary PPV computation. A text index is 56 MB. Whole-vocabulary PPVs would consume 102 GB. If PPVs are truncated to 56 MB, precision compared to true Pagerank drops to 0.55; in contrast, HubRank has precision 0.91 at 63 MB. HubRank's average query time is 328 milliseconds; query-time Pagerank computation takes 11 seconds on average.Soumen ChakrabartiIIT Bombay326Previous studies comparing the prediction accuracy of effort models built using Web cross- and single-company data sets have been inconclusive, and as such replicated studies are necessary to determine under what circumstances a company can place reliance on a cross-company effort model. This paper therefore replicates a previous study by investigating how successful a cross-company effort model is: i) to estimate effort for Web projects that belong to a single company and were not used to build the cross-company model; ii) compared to a single-company effort model. Our single-company data set had data on 15 Web projects from a single company and our cross-company data set had data on 68 Web projects from 25 different companies. The effort estimates used in our analysis were obtained by means of two effort estimation techniques, namely forward stepwise regression and case-based reasoning. Our results were similar to those from the replicated study, showing that predictions based on the single-company model were significantly more accurate than those based on the cross-company model.Emilia MendesThe University of AucklandSergio Di MartinoUniversity of SalernoFilomena FerrucciUniversity of SalernoCarmine GravinoUniversity of Salerno339This paper proposes a random Web crawl model. A Web crawl is a (biased and partial) image of the Web. This paper deals with the hyperlink structure, i.e. a Web crawl is a graph, whose vertices are the pages and whose edges are the hypertextual links. Of course a Web crawl has a very particular structure; we recall some known results about it. We then propose a model generating similar structures. Our model simply simulates a crawling, i.e. builds and crawls the graph at the same time. The graphs generated have lot of known properties of Web crawls. Our model is simpler than most random Web graph models, but captures the sames properties. Notice that it modelizes the crawling process instead of the page writting process of Web graph models.Toufik BennouasCriteo R&amp;DFabien de MontgolfierUniversite Paris 7342Given a large collection of sparse vector data in a high dimensional space, we investigate the problem of finding all pairs of vectors whose similarity score (as determined by a function such as cosine distance) is above a given threshold. We propose novel optimization and indexing techniques for this problem, resulting in an algorithm that is both faster and simpler than the previous state-of-the-art approaches. We demonstrate the effectiveness of our algorithm on the public DBLP dataset, and on two real-world web applications: generating recommendations for the Orkut social network, and computing pairs of similar queries from search snippet data among the 5 million most frequently issued Google queries. Our algorithm is between 5 times to 20 times faster than previous algorithms on these datasets.Roberto BayardoGoogleYiming MaU. California IrvineRamakrishnan SrikantGoogle366Several research efforts as well as deployments have chosen IEEE 802.11 as a low-cost, long-distance access technology to bridge the digital divide. In this paper, we consider the important issue of planning such networks to the minimize system cost. This is a non-trivial task since it involves several sets of variables: the network topology, tower heights, antenna types to be used and their orientations, and radio transmit powers. The task is further complicated due to the presence of network performance constraints, and the inter-dependence among the variables. Our first contribution in this paper is the formulation of this problem in terms of the variables, constraints and the optimization criterion. Our second contribution is in identifying the dependencies among the variables and breaking-down the problem into four tractable sub-parts. In this process, we extensively use domain knowledge to strike a balance between tractability and practicality.<br /><br /> We have evaluated the proposed algorithms using random input sets as well as real-life instances with success. We have been able to show detailed planning of network topology, required tower heights, antenna types, and transmit powers for the Ashwini project, a long distance WiFi network under deployment in Andhra Pradesh, India, In this case, we are able to achieve within 2\% additional cost of a lower bound estimate.Sayandeep SenIIT KanpurBhaskaran RamanIndian Institute of Technology, Kanpur391We present YAGO, a light-weight and extensible ontology with high coverage and quality. YAGO builds on entities and relations and currently contains roughly 900,000 entities and 5,000,000 facts. This includes the Is-A hierarchy as well as non-taxonomic relations between entities (such as hasWonPrize). The facts have been automatically extracted from the unification of Wikipedia and WordNet, using a carefully designed combination of rule-based and heuristic methods described in this paper. The resulting knowledge base is a major step beyond WordNet: in quality by adding knowledge about individuals like persons, organizations, products, etc. with their semantic relationships -- and in quantity by increasing the number of facts by more than an order of magnitude. Our empirical evaluation of fact correctness shows an accuracy of about 95%. YAGO is based on a logically clean model, which is decidable, extensible, and compatible with RDFS. Finally, we show how YAGO can be further extended by state-of-the-art information extraction techniques.Fabian M. SuchanekMax-Planck-Institute for Computer ScienceGjergji KasneciMax-Planck-Institute for Computer ScienceGerhard WeikumMax-Planck-Institute for Computer Science395Requirement engineering is emerging as an increasingly important discipline for supporting Web application development, as these are designed to satisfy diverse stakeholder needs, additional functional, information, multimedia and usability requirements as compared to traditional software applications. Moreover, when considering innovative e-commerce applications, value-based requirements engineering is an extremely relevant methodology which exploits the concept of economic value during the requirements engineering activity. In contrast, most of the methodologies proposed for the development of Web applications, primarily focus on the system design, and paying less attention to the requirements engineering, and specifically to value-based requirement engineering. Focusing this aspect, the paper presents integration of value-based requirement engineering models to WebML models using our recently proposed VIP Business Modeling Framework. The integration process is demonstrated using a well-known e-commerce application example by first presenting example VIP business models and then deriving WebML process, structural and other models from these business models.Farooque AzamBUAAZhang LiBUAARashid AhmadBUAA397This paper explores the use of social annotations to improve web search. Nowadays, many services e.g., del.icio.us have been developed for web users to organize and share their favorite web pages on line by using social annotations. We observed that the social annotations can benefit the web search in two aspects: 1) the annotations are usually good summaries of corresponding web pages; 2) the count of annotations indicates the popularity of web pages. Two novel algorithms are proposed to incorporate these information into page ranking: 1) SocialSimRank (SSR) calculates the similarity between social annotations and web queries; 2) SocialPageRank (SPR) captures the popularity of web pages. Preliminary experimental results show that SSR can find the latent semantic association between queries and annotations, while SPR successfully measures the quality (popularity) of a web page from the web users' perspective. We further empirically evaluate the proposed methods with 50 manually annotated queries and 3000 auto-generated queries, on a dataset consisting of 690,482 web pages with 2,879,614 different annotations [32]. Experiments show that both SSR and SPR benefit the web search significantly. By incorporating both the SPR and SSR features, the quality of search results can be improved by as much as 14.80% and 25.02% compared with the original performance in MAP on two query sets respectively.Shenghua BaoShanghai Jiao Tong UniversityXiaoyuan WuShanghai Jiao Tong UniversityBen FeiIBM China Research LabGui-Rong XueShanghai Jiao-Tong UniversityZhong SuIBM China Research LabYong YuShanghai Jiao-Tong University403Search queries applied to extract relevant information from the World Wide Web over a period of time may be denoted as continuous search queries. The improvement of continuous search queries may concern not only the quality of retrieved results but also the freshness of results, i.e. the time between the availability of a respective data object on the Web and the notification of a user by the search engine. In some cases a user should be notified immediately since the value of the respective information decreases quickly, as e.g. news about companies that affect the value of respective stocks or sales offers for products that may no longer be available after a short period of time. In the document filtering literature the optimization of such queries is usually based on threshold classification. Documents above a quality threshold are returned to a user. The threshold is tuned in order to optimize the quality of retrieved results. The disadvantage of such approaches is that the amount of information returned to a user may hardly be controlled without further user-interaction. In this paper we consider the optimization of bounded continuous search queries where only the estimated best k elements are returned to a user. We present a new optimization method for bounded continuous search queries based on the optimal stopping theory and compare the new method to methods currently applied by Web search systems. The new method provides results of significantly higher quality for the cases where very fresh results have to be delivered.Dirk KukulenzInstitute of Information SystemsAlexandros NtoulasMicrosoft Search Labs420Service-level agreements (SLAs) establish a contract between service providers and clients concerning Quality of Service (QoS) parameters. Without proper penalties, service providers have strong incentives to deviate from the advertised QoS, causing losses to the clients. Reliable QoS monitoring (and proper penalties computed on the basis of delivered QoS) are therefore essential for the trustworthiness of a service-oriented environment. In this paper, we present a novel QoS monitoring mechanism based on quality ratings from the clients. A reputation mechanism collects the ratings and computes the actual quality delivered to the clients. The mechanism provides incentives for the clients to report honestly, and pays special attention to minimizing cost and overhead.Radu JurcaEcole Polytechnique Federale de Lausanne EPFLWalter BinderUniversity of LuganoBoi FaltingsEcole Polytechnique Federale de Lausanne EPFL428Recent work on ontology-based Information Extraction (IE) has tried to make an increased use of the knowledge from the target ontology in order to improve the semantic annotation results. However, only very few approaches are able to benefit from the ontology structure and one of them is not a learning system, thus is not easy to adapt to new domains, whereas the other one does not perform semantic annotation of documents, but only ontology population.<br /><br /> This paper introduces a hierarchical learning approach for IE, which uses the target ontology as an essential part of the extraction process. Hierarchical classification takes into account the relations between concepts, thus benefiting directly from the ontology.<br /><br /> We also carry out evaluation experiments on the largest available semantically annotated corpus of 146 classes. The results demonstrate clearly the benefits of using knowledge from the ontology for ontology-based IE. We also demonstrate the advantages of our approach over other state-of-the-art learning systems on a commonly used benchmark dataset.Yaoyong LiUniversity of SheffieldKalina BontchevaUniversity of Sheffield429In this paper we describe new adaptive crawling strategies to efficiently locate the entry points to hidden-Web sources. The fact that hidden-Web sources are very sparsely distributed makes the problem of locating them especially challenging. We deal with this problem by using the contents of pages to focus the crawl on a topic; by prioritizing promising links within the topic; and by also following links that may not lead to immediate benefit. We propose a new framework whereby crawlers automatically learn patterns of promising links, and adapt their focus as the crawl progresses, thus greatly reducing the amount of required manual setup and tuning. Our experiments over real Web pages in a representative set of domains indicate that online learning leads to significant gains in harvest rates: the adaptive crawlers retrieve up to three times as many forms as crawlers that use a fixed focus strategy.Luciano BarbosaUniversity of UtahJuliana FreireUniversity of Utah433The ability to extract meaningful fragments from an ontology is key for ontology re-use. We propose a definition of a module that guarantees to completely capture the meaning of a given set of terms, i.e., to include all axioms relevant to the meaning of these terms, and study the problem of extracting minimally sized modules. We show that the problem of deciding if a module is minimal is undecidable even for rather restricted sub-languages of OWL DL. Hence we propose two ``approximations'', i.e., alternative definitions of modules for a vocabulary that still provide the above guarantee, but that are possibly too strict, and that may thus result in larger modules: the first approximation is semantic and can be checked using existing DL reasoners; the second is syntactic, and can be computed in polynomial time. Finally, we report on an empirical evaluation of our syntactic approximation that demonstrates that the modules we extract are surprisingly small.Bernardo Cuenca GrauUniversity of ManchesterIan HorrocksUniversity of ManchesterYevgeny KazakovUniversity of ManchesterUlrike SattlerUniversity of Manchester435As the data and ontology layers of the Semantic Web stack have achieved a certain level of maturity in standard recommendations such as RDF and OWL, the current focus lies on two related aspects. On the one hand, the definition of a suitable query language for RDF, SPARQL, seems to be close to candidate recommendation status within the W3C. The establishment of the Rules layer on top of the existing stack on the other hand marks the next step to be tackled, where especially languages with their roots in Logic Programming and Deductive Databases are receiving considerable attention. The purpose of this paper is threefold. First, we discuss the formal semantics of SPARQL extending recent results in several ways. Second, we provide translations from SPARQL to Datalog with stratified negation as failure. Third, we propose some useful and easy to implement extensions of SPARQL, based on this translation. As it turns out, the combination serves for direct implementations of SPARQL on top of existing rules engines as well as a basis for more general rules and query languages on top of RDF.Axel PolleresDERI, National University of Ireland447To increase confidence in the correctness of specified policies, policy developers can conduct policy testing by supplying typical test inputs (requests) and subsequently checking test outputs (responses) against expected ones. Unfortunately, manual testing is tedious and few tools exist for automated testing of XACML policies.<br /><br /> We present a fault model for access control policies and a framework to explore it. The framework includes mutation operators used to implement the fault model, mutant generation, equivalent-mutant detection, and mutant-killing determination. This framework allows us to investigate our fault model, evaluate coverage criteria for test generation and selection, and determine a relationship between structural coverage and fault-detection effectiveness. We have implemented the framework and applied it to various XACML policies. Our experimental results offer valuable insights into choosing mutation operators in mutation testing and choosing coverage criteria in test generation and selection.Evan MartinNorth Carolina State UniversityTao XieNorth Carolina State University461Enterprise data processing and content aggregation systems often require extensive use of human reviewed data (e.g. for training and monitoring machine learning-based applications). Today these needs are often met by in-house efforts or offshore contracting. Emerging applications attempt to provide automation for human reviewed data collection at Internet-scale. We conduct extensive experiments to study the effectiveness of one such application. We also study the feasibility of using Yahoo! Answers, a general question-answering forum, for human review data collection.Qi SuYahoo! IncDmitry PavlovYahoo! IncJyh-Herng ChowYahoo! IncWendell BakerYahoo! Inc464Discovering mappings between concept hierarchies is widely regarded as one of the hardest and most urgent problems facing the Semantic Web. The problem is even harder in domains where concepts are inherently vague and ill-defined, and cannot be given a crisp definition. A notion of approximate concept mapping is required in such domains, but until now, no such notion is available.<br /><br /> The first contribution of this paper is a definition for concepts is decomposed into a number of submappings, and a \emph{sloppiness value} determines the fraction of these submappings that can be ignored when establishing the mapping.<br /><br /> A potential problem of such a definition is that with an increasing sloppiness value, it will gradually allow mappings between any two arbitrary concepts. To improve on this trivial behaviour, we need to design a heuristic weighting which minimises the sloppiness required to conclude desirable matches, but at the same time maximises the sloppiness required to conclude undesirable matches. The second contribution of this paper is to show that a \emph{Google-based similarity measure} has exactly these desirable properties.<br /><br /> We establish these results by \emph{experimental validation in the domain of musical genres}. We show that this domain does suffer from ill-defined concepts. We take two real-life genre hierarchies from the Web, we compute approximate mappings between them at varying levels of sloppiness, and we validate our results against a hand-crafted Gold Standard.<br /><br /> Our method makes use of the huge amount of knowledge that is implicit in the current Web, and exploits this knowledge as a heuristic for establishing approximate mappings between ill-defined concepts.Risto Risto GligorovPhilips ResearchZharko AleksovskiPhilips ResearchWarner ten KatePhilips ResearchFrank van HarmelenVrije Universiteit Amsterdam468The development of user interfaces (UIs) is one of the most time-consuming aspects in software development. In this context, the lack of proper reuse mechanisms for UIs is increasingly becoming manifest, especially as software development is more and more moving toward composite applications. In this paper we propose a framework for the integration of stand-alone modules or applications, where integration occurs at the presentation layer. Hence, the final goal is to reduce the effort required for UI development by maximizing reuse.<br /><br /> The design of the framework is inspired by lessons learned from application integration, appropriately modified to account for the specificity of the UI integration problem. We provide an abstract component model to specify characteristics and behaviors of presentation components and propose an event-based composition model to specify the composition logic. Components and composition are described by means of a simple XML-based language, which is interpreted by a runtime middleware for the execution of the resulting composite application. A proof-of-concept prototype allows us to show that the proposed component model can also easily be applied to existing presentation components, built with different languages and/or component technologies.Jin YuUniversity of New South WalesBoualem BenatallahUniversity of New South WalesRegis Saint-PaulUniversity of New South WalesFabio CasatiUniversity of TrentoFlorian DanielPolitecnico di MilanoMaristella MateraPolitecnico di Milano469A key challenge for dynamic Web service selection is that Web services are typically highly configurable and service requesters often have dynamic preferences on service configurations. Current approaches, such as WS-Agreement, describe Web services by enumerating the various possible service configurations, an inefficient approach when dealing with numerous service attributes with large value spaces. We model Web service configurations and associated prices and preferences more compactly using utility function policies, which also allows us to draw from multi-attribute decision theory methods to develop an algorithm for optimal service selection. In this paper, we present an OWL ontology for the specification of configurable Web service offers and requests, and a flexible and extensible framework for optimal service selection that combines declarative logic-based matching rules with optimization methods, such as linear programming. Assuming additive price/preference functions, experimental results indicate that our algorithm introduces an overhead of only around 2 sec. compared to a random service selection, while giving optimal results. The overhead, as percentage of total time, decreases as the number of offers and configurations increase.Steffen LamparterInstitute AIFB, Universitaet Karlsruhe THAnupriya AnkolekarInstitute AIFB, Universitaet Karlsruhe THRudi StuderInstitute AIFB, Universitaet Karlsruhe THStephan GrimmFZI Karlsruhe479The workflow language Martlet described in this paper implements a new programming model that allows users to write parallel programs and analyse distributed data without having to be aware of the details of the parallelisation. Martlet abstracts the parallelisation of the computation and the splitting of the data through the inclusion of constructs inspired by functional programming. These allow programs to be written as an abstract description that can be adjusted automatically at runtime to match the data set and available resources. Using this model it is possible to write programs to perform complex calculations across a distributed data set such as Singular Value Decomposition or Least Squares problems, as well as creating an intuitive way of working with distributed systems<br /><br /> Having described and evaluated Martlet against other functional languages for parallel computation, this paper goes on to look at how Martlet might develop. In doing so it covers both possible additions to the language itself, and the use of JIT compilers to increase the range of platforms it is capable of running on.Daniel James GoodmanOxford University481The success of the Semantic Web depends on the availability of Web pages annotated with metadata. Free form metadata or tags, as used in social bookmarking and folksonomies based systems, have become more and more popular and successful. Such tags are relevant keywords associated with or assigned to a piece of information (e.g., a Web page), thus describing the item and enabling keyword-based classification. In this paper we propose P-TAG, a method which automatically generates personalized tags for Web pages. Keywords are generated based on the content of the Web page but also based on the content of the user's Desktop, thus expressing a personalized viewpoint very relevant for personal tags. We implemented and tested several algorithms for this approach and evaluated the relevance of the resulting keywords. These evaluations showed very promising results and we are therefore very confident that such a user oriented automatic tagging approach can provide large scale personalized metadata annotation as an important step towards realizing the Semantic Web.Paul - Alexandru ChiritaL3S / University of HannoverStefania CostacheL3S Research Center / University of HannoverSiegfried HandschuhNational University of IrelandWolfgang NejdlUniversity of Hannover485Data-driven web applications are structured into three tiers with different programming models at each tier. This division forces developers to manually partition application functionality across the tiers, resulting in complex logic, suboptimal partitioning, and expensive re-partitioning of applications.<br /><br /> In this paper, we introduce a unified platform for automatic partitioning of data-driven web applications. Our approach is based on Hilda, a high-level declarative programming language with a unified data and programming model for all the layers of the application. Based on run-time properties of the application, Hilda's run time system automatically partitions the application between the tiers to improve response time while adhering to memory or processing constraints at the clients. We evaluate our methodology with traces from a real application and with TPC-W, and our results show that automatic partitioning outperforms manual partitioning without the associated development overhead.Fan YangCornell UniversityNitin GuptaCornell UniversityNicholas GernerCornell UniversityXin QiCornell UniversityAlan DemersCornell UniversityJohannes GehrkeCornell UniversityJayavel ShanmugasundaramYahoo!495Although personalized search has been proposed for many years and many personalization strategies have been investigated, it is still unclear whether personalization is consistently effective on different queries for different users, and under different search contexts. In this paper, we study the problem and get some preliminary conclusions. We present a large-scale personalized search evaluation framework based on search logs and then evaluate five personalized search strategies (including two click-based and three profile-based ones) using 12-day MSN search logs. By analyzing the results, we reveal that personalized search has significant improvement over common web search on some queries but it also has little effect on other queries (e.g., queries with small click entropy) and even harms search accuracy under some situations. Furthermore, we show that click-based personalization strategies perform consistently and considerablely well while profile-based ones are unstable in our experiments. We also reveal that both long-term and short-term contexts are very important in improving search performance for profile-based personalized search strategies.Zhicheng DouNankai University, ChinaRuihua SongMicrosoft Research AsiaJi-Rong WenMicrosoft Research Asia504Clio is an existing schema-mapping tool that provides user-friendly means to manage and facilitate the complex task of transformation and integration of heterogeneous data such as XML over the Web or in XML databases. By means of mappings from source to target schemas, Clio can help users conveniently establish the precise semantics of data transformation and integration. In this paper we study the problem of how to efficiently implement such data transformation (i.e., generating target data from the source data based on schema mappings). We present a three-phase framework for high-performance XML-to-XML transformation based on schema mappings, and discuss methodologies and algorithms for implementing these phases. In particular, we elaborate on novel techniques such as streamed extraction of mapped source values and scalable disk-based merging of overlapping data (including duplicate elimination). We compare our transformation framework with alternative methods such as using XQuery or SQL/XML provided by current commercial databases. The results demonstrate that the three-phase framework (although as simple as it is) is highly scalable and outperforms the alternative methods by orders of magnitude.Haifeng JiangIBM Almaden Research CenterHoward HoIBM Almaden Research CenterLucian PopaIBM Almaden Research CenterWook-Shin HanComputer Enigeering Dept., Kyungpook National University, Korea507XML delivers key advantages in interoperability due to its flexibility, expressiveness, and platform-neutrality. As XML has become a performance-critical aspect of the next generation of business computing infrastructure, however, it has become increasingly clear that XML parsing often carries a heavy performance penalty, and that current, widely-used parsing technologies are unable to meet the performance demands of an XML-based computing infrastructure. Several efforts have been made to address this performance gap through the use of grammar-based parser generation. While the performance of generated parsers has been significantly improved, adoption of the technology has been hindered by the complexity of compiling and deploying the generated parsers. Through careful analysis of the operations required for parsing and validation, we have devised a set of specialized bytecodes, designed for the task of XML parsing and validation. These bytecodes are designed to engender the benefits of fine-grained composition of parsing and validation that make existing compiled parsers fast, while being coarse-grained enough to minimize interpreter overhead. This technique of using an interpretive, validating parser balances the need for performance against the requirements of simple tooling and robust scalable infrastructure. Our approach is demonstrated with a specialized schema compiler, used to generate bytecodes which in turn drive an interpretive parser. With almost as little tooling and deployment complexity as a traditional interpretive parser, the bytecode-driven parser usually demonstrates performance within 20% of the fastest fully compiled solutions.Morris MatsaIBMEric PerkinsIBMAbraham HeifetsIBMMargaret Gaitatzes KostoulasIBMDaniel SilvaIBMNoah MendelsohnIBMMichelle LegerIBM511Traffic classification is the ability to identify and categorize network traffic by application type. In this paper, we consider the problem of traffic classification in the network core. Classification at the core is challenging because only partial information of the flows and their contributors is available. We address this problem by developing and evaluating a classification framework that can classify a flow using only unidirectional flow information. We validated this approach using recent full-payload packet traces that we collected and pre-classified to establish a ``base truth''. From our evaluation, we find that flow statistics along the server-to-client path of a TCP connection provides higher classification accuracy than flow statistics along the client-to-server path. Because collection of the server-to-client flow statistics may not always be feasible, we developed and verified an algorithm that can estimate the missing statistics from a unidirectional packet trace.Jeffrey ErmanUniversity of CalgaryAnirban MahantiUniversity of CalgaryMartin ArlittHP Labs/University of CalgaryCarey WilliamsonUniversity of Calgary516Web-based communities have become an important place for people to seek and share expertise. We find that networks in these communities typically differ in their topology from other online networks such as the World Wide Web. Systems targeted to augment web-based communities by automatically identifying users with expertise, for example, need to adapt to the underlying interaction dynamics. In this study, we analyze the Java Forum, a large online help-seeking community, using social network analysis methods. We test a set of network-based ranking algorithms, including PageRank and HITS, on this large size social network in order to identify users with high expertise. We then use simulations to identify a small number of simple rules governing the question-answer dynamic in the network. These simple rules not only replicate the structural characteristics and algorithm performance on the empirically observed Java Forum, but also allow us to evaluate how other algorithms may perform in communities with different characteristics. We believe this approach will be fruitful for practical algorithm design and implementation for online expertise-sharing communities.Jun ZhangUniversity of MichiganMark AckermanUniversity of MichiganLada AdamicUniversity of Michigan520The aggregation and comparison of behavioral patterns on the WWW represent a tremendous opportunity for understanding past behaviors and predicting future behaviors. In this paper, we take a first step at achieving this goal. We present a large scale study correlating the behaviors of Internet users on multiple systems ranging in size from 27 m