Abstract:

Searching for information is one of the most common tasks that users of any computer system perform, ranging from searching on a local computer, to a shared database, and to the Internet. The growth of the Internet and the World Wide Web, the access to an immense amount of data, and the ability of millions of users to freely publish their own content has made the search problem more central than ever before. Compared to traditional information-retrieval systems, many of the emerging information systems of interest, including peer-to-peer networks, blogs, and social networks among others, exhibit a number of characteristics that make the search problem considerably more challenging.We survey algorithms for searching information in systems that are characterized by a number of such features: the data are linked in an underlying graph structure, they are distributed, highly dynamic, there is social information, tagging capabilities, and more. We call such algorithms, next-generation search algorithms.