The Resource Description Framework (RDF) is a family of specications developed and supported by the W3C consortium to represent information in the Web 1 . During the last years, RDF has gained popularity in many domains such as medicine and cultural heritage as a representation format for heterogeneous structured data on the Web [2]. RDF graphs can be interrogated by queries expressed with the SPARQL language. To write queries in this language can become very dicult. Users are required to know the language and the structure of the underlying dataset in order to write correct queries. Thus, the need for a system of keyword search for these graphs. Keyword search permits users to express their information need via a query in natural language, in a Google-like fashion. Keyword search over large knowledge bases can become dicult both in therms of memory and time required to answer to a single query. In this abstract, we discuss the experience of designing and implementing keyword search algorithms over big RDF databases.