Contenuto
Ti trovi in: HOME »Programmi, progetti e risultati »I progetti »PRIN - Programmi di ricerca di Rilevante Interesse Nazionale»Programma di ricercaINIZIO_TESTO_DA_INDICIZZARE
PROGRAMMA DI RICERCA 2006
italiano - english
Unità di Ricerca
Programmi di ricerca simili:
- 1 - Sintesi automatica di modelli astratti a partire da dati temporali o spaziali
- 2 - Future applicazioni del paradigma peer-to-peer
- 3 - Metodi basati sulla similarita' per la visione artificiale e il riconoscimento delle forme: Teoria, algoritmi, applicazioni
- 4 - Nuove tecniche e strumenti per l'interrogazione di servizi di ricerca su Web
- 5 - Algoritmi per Internet e Web di prossima generazione: Metodologie, Progetto ed Esperimenti
- 6 - Basi di dati crittografate
- 7 - Comprensione ab-initio delle proprieta' strutturali, elettroniche, ottiche di sistemi di semiconduttori nanostrutturati e a bassa dimensionalita'
- 8 - Metodologie avanzate per il controllo di sistemi ibridi
- 9 - Elaborazione di segnali cifrati per la tutela della privacy nel trattamento di informazioni sensibili
- 10 - Progettazione, caratterizzazione ed applicazioni analitiche di sensori elettrochimici innovativi
Classificazione scientifico-disciplinare
- Area scientifico disciplinare: Scienze matematiche e informatiche
Classificazione brevettuale
- PHYSICS
- COMPUTING; CALCULATING; COUNTING (score computers for games A63; combinations of writing applicances with computing devices B43K29/08)
- ELECTRICAL DIGITAL DATA PROCESSING (computers in which a part of the computation is effected hydraulically or pneumatically G06D; optically G06E; self-contained input or output peripheral equipment G06K; impedance networks using digital techniques H03H) [C9603]
- COMPUTING; CALCULATING; COUNTING (score computers for games A63; combinations of writing applicances with computing devices B43K29/08)
Classificazione geografica
- Regione: Lazio
Bibliografia
[Ba96]Introduction to Discrete Event Simulation. In proceeding of the2th DYCOMANS workshop on " Management and Control : Tools in
Action", pp. 367-376 Algarve, Portugal.1996.
[BYSJ02] R. Baeza-Yates, F. Saint-Jean and C. Castillo. Web
structure, dynamics and page quality. In Proceedings of String
Processing and Information Retrieval (SPIRE), volume 2476 of Lecture
Notes in Computer Science, Lisbon, Portugal. Springer. 2002.
[CMRZ04] C. Castillo, M. Marin, A. Rodr?guez, and R. Baeza-Yates.
Scheduling algorithms for Web crawling. In Latin American Web
Conference (WebMedia/LA-WEB), pp 10–17, Riberao Preto, Brazil,
October 2004. IEEE CS Press.
[HH00] M. Henzinger, A. Heydon, M. Mitzenmacher and M. Najork. On
near–uniform url sampling. In Proceedings of the Ninth Conference on
World Wide Web, pages 295–308, Amsterdam, Netherlands. Elsevier
Science. 2000.
[BP98] L. Page,S. Brin Sergey, R. Motwani and T. Winograd. The PageRank citation ranking:
bringing order to the Web. Stanford Digital Library Technologies Project, 1998. http://citeseer.ist.psu.edu/page98pagerank.html
[GM05] Z. Gyongyi and H. Garcia-Molina. Web Spam Taxonomy. First International Workshop on Adversarial Information Retrieval on the Web, 2005. http://dbpubs.stanford.edu:8090/pub/2004-25
[FM04] D. Fetterly, M. Manasse and M. Najork. Statistical analysis of spam through detection of outliers in histograms. Proceedings of the seventh workshop on the Web and databases (WebDB), 2004. http://dx.doi.org/http://doi.acm.org/10.1145/1017074.1017077
[DS05] I. Drost and T. Scheffer. Thwarting the nigritude ultramarine: learning to identify link spam. Proceedings of the 16th European Conference on Machine Learning (ECML), 2005. http://www.informatik.hu-berlin.de/~scheffer/publications/ecml2005-nigritude.pdf
[AW03] K. Aberer and J. Wu. A framework for decentralized
ranking in web information retrieval. In APWeb,
pages 213–226, 2003.
[AW04] K. Aberer, J. Wu. Towards A Common Framework for Peer-to-Peer Web Retrieval. Book Chapter of From Integrated Publication and Informations Systems to Virtual Information and Knowledge Environments, EJN-Festschrift, Matthias Hemmje Ed., Springer LNCS, 2004.
[WA04] J. Wu and K. Aberer. Using SiteRank for P2P Web Retrieval. Tech Rep IC/2004/31, Swiss Federal Institute of Technology, Lausanne. 2004
[BP98] L. Page,S. Brin Sergey, R. Motwani and T. Winograd. The PageRank citation ranking:
bringing order to the Web. Stanford Digital Library Technologies Project, 1998. http://citeseer.ist.psu.edu/page98pagerank.html
[FM04] D. Fetterly, M. Manasse and M. Najork. Statistical analysis of spam through detection of outliers in histograms. Proceedings of the seventh workshop on the Web and databases (WebDB), 2004. http://dx.doi.org/http://doi.acm.org/10.1145/1017074.1017077
[DS05] I. Drost and T. Scheffer. Thwarting the nigritude ultramarine: learning to identify link spam. Proceedings of the 16th European Conference on Machine Learning (ECML), 2005. http://www.informatik.hu-berlin.de/~scheffer/publications/ecml2005-nigritude.pdf
[WA04b] J. Wu, K. Aberer. Using SiteRank for Decentralized Computation of Web Document Ranking. Proceedings of the Third International Conference on Adaptive Hypermedia and Adaptive Web-Based Systems, Eindhoven University of Technology, The Netherlands. 2004
[B05] R. A. Baeza-Yates. Applications of web query mining. In
Advances in Information Retrieval, 27th European Confer-
ence on IR Research, ECIR 2005, Santiago de Compostela,
Spain, March 21-23, 2005, Proceedings, volume 3408 of Lec-
ture Notes in Computer Science, pages 7-22. Springer, 2005.
[NCO04] A. Ntoulas, J. Cho, and C. Olston. What's new on the web?: the evolution of the web from a search engine perspective. In WWW '04:
Proceedings of the 13th international conference on World Wide Web , pages
1--12, New York, NY, USA, 2004. ACM Press.
[KHS03] R. Kraft, E. Hastor, and R. Stata. Timelinks: Exploring the
link structure of the evolving web. In Second Workshop on Algorithms
and Models for the Web-Graph (WAW2003) , 2003.
[KNRT03] Ravi Kumar, Jasmine Novak, Prabhakar Raghavan, and Andrew
Tomkins. On the bursty evolution of blogspace. In WWW '03: Proceedings
of the 12th international conference on World Wide Web, pages 568--576, New York, NY, USA, 2003. ACM Press.
[BKM00] A. Z. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan,
S.Stata, A. Tomkins, and J. Wiener. Graph structure in the web. Computer Networks, 33:309--320, June 2000.
[New05] M. E. J. Newman. Power laws, pareto distributions and zipf's law.
Contemporary Physics, 46:323--351, December 2005.
[PaRa02] G. Pandurangan, P. Raghavan, and E. Upfal. Using Pagerank to characterize Web structure.
In Proc. of COCOON, vol. 2387 of Lecture Notes in Computer Science}, pages 330--390, 2002.
[1] H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, New York, NY, 1987.
[6] D. Sivakumar R. Fagin, R. Kumar. Efficient similarity search and classification via rank aggregation. In SIGMOD ’03: Proceedings of the 2003 ACM SIGMOD international conference on Management of data, pages 301–312, New York, NY, USA, 2003. ACM Press.
[10] L. Ertz, M. Steinbach, and V. Kumar. Finding topics in collections of documents: A shared nearest neighbor approach. In Text Mine ’01, Workshop on Text Mining, First SIAM International Conference on Data Mining, Chicago, IL, (2001).
[14] Jon M. Kleinberg. Two Algorithms for Nearest-Neighbor Search in High Dimensions. In STOC, pages 599–608, 1997.
[18] A. Guttman. R-trees: A dynamic index structure for spatial searching. In SIGMOD Conference, pages 47–57, 1984.
[26] J. Goldstein and Raghu Ramakrishnan, Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbour Searches. Proceedings of the 26th International Conference on Very Large Data Bases (2000), 429 - 440
[101] Junghoo Cho and Hector Garcia-Molina. Parallel crawlers. In Proc. of the Eleventh International World-Wide Web conference (WWW 2002), pages 124-135, Honolulu, Hawaii, 2002. ACM Press.
[102] Allan Heydon and Marc Najork. Mercator: A scalable, extensible web crawler. World Wide Web, pages 219-229, December 1999.
[103] Paolo Boldi, Bruno Codenotti, Massimo Santini, and Sebastiano Vigna. Ubicrawler: A scalable fully distributed web crawler. Software: Practice & Experience, 34(8):711- 726, 2004.
[104] Keith Randall, Raymie Stata, Rajiv Wickremesinghe, and Janet L. Wiener. The LINK database: Fast access to graphs of the Web. Research Report 175, Compaq Systems Research Center, Palo Alto, CA, 2001.
[105] Krishna Bharat, Andrei Broder, Monika Henzinger, Puneet Kumar, and Suresh Venkatasubramanian. The Connectivity Server: Fast access to
linkage information on the web. In Proceedings of the Seventh International World–Wide Web Conference, pages 469–477, Brisbane, Australia, 1998.
[106] Paolo Boldi and Sebastiano Vigna. The WebGraph framework I: Compression techniques. In Proc. of the Thirteenth International World Wide Web Conference, pages 595- 601, Manhattan, USA, 2004. ACM Press.
[109] Jon M. Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM, 46(5):604-632, September 1999.
[110] Paolo Boldi, Massimo Santini, and Sebastiano Vigna. Do your worst to make the best: Paradoxical effects in PageRank incremental computations. Internet Math., 2(3):387- 404, 2005.
[111] Paolo Boldi, Massimo Santini, and Sebastiano Vigna. PageRank as a function of the damping factor. In Proc. of the Fourteenth International World Wide Web Conference, Chiba, Japan, 2005. ACM Press.
[112] Sebastiano Vigna. TruRank: Taking PageRank to the limit. In Poster Proc. of the Fourteenth International World Wide Web Conference, pages 557 566, Chiba, Japan, 2005. ACM Press.
Parole Chiave
ALGORITMI E STRUTTURE DATI PER IL WEB, ANALISI DEI COLLEGAMENTI, CRAWLING, SPAM DETECTION, NEAREST NEIGHBOURS, RANK AGGREGATION, WEB GRAPH, COMPRESSIONEWeb Ram: web retrieval and mining
Università degli Studi di Roma "La Sapienza"Abstract
Questo programma di ricerca è relativo ad un insieme di problemi aperti della ricerca contemporanea nel settore dell'information retrieval per il web (motori di ricerca). I problemi di cui ci vogliamo occupare sono sufficientemente importanti da meritare di essere studiati indipendentemente gli uni dagli altri ma, al contempo, essi presentano interazioni a vari livelli formando un tutto coerente:1. Crawling:
- uno degli obiettivi del progetto è collezionare una serie di snapshot di porzioni ragguardevoli del web (ad es. il dominio .it) allo scopo di (a) studiare l'evoluzione temporale del web e (b) sviluppare tecniche algoritmiche che siano in grado di restituire documenti che non solo siano rilevanti (rispetto ad una data query) ma anche aggiornati
- un altro obiettivo è quello di mettere a punto strategie di crawling in grado di unire i pregi di approcci esistenti. In particolare si vuole sviluppare strategie che siano molto efficienti in termini di utilizzo della memoria ma al contempo siano "cortesi" e in grado di raccogliere subito pagine di alta qualità
2. Spam: si vuole sviluppare nuovi algoritmi che siano in grado di individuare lo spam e calcolare di conseguenza il rank delle pagine
3. Aggregazione di segnali: i motori di ricerca allo stato dell'arte usano una varietà di segnali che vengono aggregati in modo opportuno in modo da assegnare alle >>>
Coordinatore Scientifico del Programma di Ricerca
Alessandro Panconesi Università degli Studi di ROMA "La Sapienza"Obiettivo del Programma di Ricerca
L'information retrieval per il web (Web IR) è un'area molto vitale della ricerca informatica contemporanea di indubbio rilievo economico-industriale. Il suo sviluppo mostra chiaramente come molte delle idee cruciali da un punto di vista economico e applicativo sono nate grazie a ricerche matematicamente sofisticate di natura fondamentale svoltesi nell'ambito degli algoritmi e delle strutture dati. Ad esempio, è noto che il motore di ricerca Google è basato sul cosidetto PageRank, un meccanismo che assegna un livello di "qualità" alle pagine che in ultima analisi si riduce al calcolo efficiente della distribuzione stazionaria di una opportuna catena di Markov. Similmente, il successo commerciale di Teoma, uno dei leder monidali nel settore dei motori di ricerca, è basato su una implementazione efficiente di un ingegnoso algoritmo di ranking dovuto a Jon Kleinberg e noto come Hits. Gli esempi abbondano.La ricerca in Web IR procede in modo naturale su quattro binari che, per essere maggiormente efficaci, è opportuno che interagiscano cointinuamente in un circolo virtuoso:
1. Raccolta dati: per raccogliere snapshot del web
2. Analisi dei dati: per eseguire analisi statistiche e data mining del web in modo da rilevare regolarità e peculiarità nella sua struttura
3. Algoritmi e strutture dati: per sviluppare nuove applicazioni allo stato dell'arte
4. Modelli matematici e loro validazione: per >>>
Durata
24 mesiBase di partenza scientifica nazionale o internazionale
In questo documento passiamo brevemente in rassegna alcuni aspetti dello stato dell'arte che sono rilevanti per le tematiche di ricerca che intendiamo sviluppare nell'ambito del progetto.NEAREST NEIGHBOURS:
Trovare l'insieme dei documenti più rilevanti rispetto ad una data interrogazione (query) si può ricondurre spesso e volentieri al seguente problema geometrico: dato un insieme S di punti in uno spazio a d dimensioni, e dato un punto Q, determinare i punti di S più vicni a Q. Questo problema è noto come Nearest Neighbour (NN). In applicazoni tipiche la dimensione dello spazio è molto grande o addirittura enorme. Questo fatto, noto come "la maledizione della dimensionalità" rende in pratica inutilizzabili le sofisticate soluzioni algoritmiche sviluppate nell'ambito della geometria computazionale in quanto il tempo di esecuzione di quegli algoritmi tipicamente dipende esponenzialmente dalla dimensione dello spazio (si veda, ad esempio [1]).
Per quanto riguarda le applicazioni di information retrieval (IR) tra le soluzioni interessanti che sono state proposte troviamo le p-sfere [26]. Questo metodo ha però bisogno di conoscere un campione della distribuzione delle query. A grandi linee, l'idea è di sfruttare questa conoscenza per organizzare lo spazio opportunamente, in modo che le query possano essere indirizzate rapidamente verso la porzione dello spazio più rilevante.
In [6 >>>



