Google has been told that it may be breaking European privacy laws by keeping people's search information on its servers for up to two years.
Google dominates the search engine world
A data protection group that advises the European Union has written to the search giant to express concerns.
The Article 29 group, made up of data protection commissioners around the EU, has asked Google to clarify its policy.
Peter Fleischer, Google's global privacy counsel, said the firm was committed to dialogue with the group.
"We believe it's an important part of our commitment to respect user privacy while balancing a number of important factors, such as maintaining security and preventing fraud and abuse," Mr Fleischer said.
"This group has addressed a letter to Google raising a number of questions," EU spokesman Pietro Petrucci said, adding that the Union's Justice Commissioner Franco Frattini was backing the investigation.
"He considers those questions raised by the letter to be appropriate and legitimate," Mr Petrucci said.
A spokeswoman for Google said the firm would answer the EU's privacy concerns before the panel's next meeting at the end of June.
"The concern is about keeping information about people's search for a definite period of time ranging from 18 to 24 months," she said.
"They (the working party) believe it is too long."
Earlier this year Google said it would anonymise personal data it receives from users' web search after 18 to 24 months.
At the time, the firm said it was taking the step partly to match data retention laws being rolled out across Europe.
European Internet Service Providers (ISPs) and phone companies are in the process of implementing an EU directive that forces them to retain a variety of communication data for up to two years.
Google collects and stores data from each query. It holds information such as the search term itself, the unique address of the PC being used, known as the IP address, and details of how a user makes searches, such as the browser used and previous queries to Google.
That information can contain private data about a user, and could be used to build a detailed picture of the user's habits or lifestyle.
Google has said it was using this information to help improve its different services and to monitor how its search engine was functioning.
Privacy groups are concerned about how the data collected by Google, and other web firms, could be used to monitor people's online habits.