Sql – Find n Nearest Neighbors for given Point using PostGIS

I am trying to solve the problem of finding the n nearest neighbors using PostGIS:

Starting Point:

• Table geoname with geonames (from
  geonames.org) containing
  latitude/longitude (WSG-84)
• Added a GeometryColumn geom with
  srid=4326 and datatype=POINT
• Filled geom with values: UPDATE geoname
  SET geom =
  ST_SetSRID(ST_Point(longitude,latitude),
  4326);
• Created GIST index for geom (CREATE
  INDEX geom_index ON geoname USING GIST (geom);) / Clustered geom_index: CLUSTER geom_index ON
  geoname;)
• Created PRIMARY KEY UNIQUE BTREE index for geonameid

Problem:
Find n (e.g. 5) nearest neighbors for a given Point in table geoname represented by id (geoname.geonameid.

Possible solution:

Inspired by http://www.bostongis.com/PrinterFriendly.aspx?content_name=postgis_nearest_neighbor, I tried the following query:

"SELECT start.asciiname, ende.asciiname, distance_sphere(start.geom, ende.geom) as distance " +
"FROM geoname As start, geoname As ende WHERE start.geonameid = 2950159 AND start.geonameid <> ende.geonameid " +
"AND ST_DWithin(start.geom, ende.geom, 300) order by distance limit 5"

Processing time: about 60s

Also tried an approach based on EXPAND:

"SELECT start.asciiname, ende.asciiname, distance_sphere(start.geom, ende.geom) as distance " +
"FROM geoname As start, geoname As ende WHERE start.geonameid = 2950159 AND start.geonameid <> ende.geonameid AND expand(start.geom, 300) && ende.geom " +
"order by distance limit 5"

Processing time: about 120s

The intended application is some kind of autocomplete. So, any approach taking longer than >1s is not applicable. Is it generally possible to achieve a response time of <1s with PostGIS?