Girdzijauskas, SarunasDatta, AnwitamanAberer, Karl2006-08-142006-08-142006-08-14200610.1007/978-3-540-71661-7_25https://infoscience.epfl.ch/handle/20.500.14299/232850WOS:000246228700025The research on P2P systems which support skewed key distributions has rapidly advanced in the recent years. Yet, the assumptions on the skews we are dealing with remained pretty simple: most of the existing literature assumes simple monotonous key distribution skews. However, this is not always the case. For example, Gnutella filename traces show that complex key-distributions rather than monotonous skews occur in practice. We show that one of the seminal P2P systems which support skewed keys - Mercury, performs poorly given such complex distributions generated from the trace of Gnutella filenames. We discuss the shortcomings of such state-of-the-art techniques. We present an overlay network Oscar, based on a novel overlay construction mechanism, which does not depend on the key-distribution complexity. We demonstrate through simulations that our technique performs well and significantly surpasses Mercury for such realistic workloads.text::conference output::conference proceedings::conference paper