I have this problem also. It started on May 17th, like yours did. There was a sequence of events that might be involved:
1) On May 16th, one of the kids downloaded a free game from the App Store called BasketballGeneralManager.app (he has an account on my iMac, with parental controls set).
2) The next time I woke the computer, there was a textbox on the login screen to the effect that “PublicAdviseSearch needs your AppleID password, or the app won’t work correctly”. I closed this window without entering the password and logged in.
3) Then I noticed a new icon in the Dock, labeled PathBrand.app. I looked in the Applications folder, and saw BasketballGeneralManager.app and PathBrand.app. I moved PathBrand.app into the Trash. At that time, I assumed the password request had to do with that app.
4) Then my Internet access stalled, and I looked into the Activity Manager and found root-owned PublicAdviseSearch sending and receiving packets. The list showed two processes labeled PublicAdviseSearch and one process labeled PublicAdviseSearchDaemon, owned by launchd(1). Any attempt to kill these processes results in them relaunching a second or two later.