Große Arrays of Double

Wenn ich das richtig verstanden habe, dann hast du eine 1000 x 1000 Matrix mit Werten, die du in der App verwalten(?) und durchsuchen möchtest?

Die Daten am Device aus einer csv zu lesen ist nicht so glücklich, wie du ja schon selber festgestellt hast; allgemein ist es immer besser, eine Aufgabe nur einmal zu erledigen, statt mehrfach, was in diesem Fall bedeuten würde, das du die Daten schon am PC in die Endform bringst, so das deine App sie "nur" noch benutzen muss.

Von welcher allgemeinen Form sind deine doubles?
Wenn irgend möglich würde ich die in ein Ganzzahl-Format überführen (um die numerischen Probleme zu vermeiden, deren Lösung oft aufwändig und immer nervtötend und lästig ist).

Wie sieht die Suchanforderung für die Matrix aus (Parameter, Ergebnis)?

Die allgemeine Antwort auf deine Frage wäre vermutlich die Überführung deiner Daten in eine Datenbank-Struktur, daher die Fragen; genauer wird das erst mit mehr Input

Das ist ein spannendes Problem.
Vermutlich wirst Du mit double[][] nicht weit kommen und, schlimmer noch, ewig brauchen.

Eine Alternative wäre das Programmieren einer eigenen Collection, einer erweiterten ArrayList beispielsweise.
In der könntest Du dann wahlweise Arrays oder Doubles packen und eigene Algorithmen zum Erstellen und Durchsuchen nutzen.
Könnte aber durch die starre Typenbindung Javas eher kompliziert umsetzbar werden.

Eine datenbankähnliche Struktur könnte sich je nach Anwendungsfall als wesentlich zu starr darstellen. Um dies zu beurteilen bedarf es fürwahr etwas mehr Informationen.

Das Hauptproblem ist meiner Meinung nach aber nicht die Art und Weise der Datenhaltung (also Array vs. Datenbank) sondern die Tatsache, dass Du das Ganze im Speicher vorhalten möchtest.

Ein bisschen Mathematik sagt uns Folgendes:
1 Double = 64 Bit = 8 Byte
1000 Double = 64.000 Bit = 8.000 Byte ~ 8 kB
1000 * 1000 Double = 64.000.000 Bit = 8.000.000 Byte = 7.812 kB ~ 7 MB

Eine CSV-Datei mit diesen 1000x1000 Daten dürfte ungleich größer sein.
Sagen wir, Dein Float wird mit 16 Nachkommastellen im Text dargestellt. (größte Genauigkeit)
Sagen wir weiter, dass Du lediglich positive Geokoordinaten hast (maximal 3 Vorkommastellen).
Das Ganze ist dann noch durch Semikolon und ohne sonstige Zeichen getrennt.
Also ungefähr 172.1098728302384376;103.9172073168452168;…

Da bist Du dann schlimmstenfalls bei 21.000.000 Byte = 20507 kB ~ 20MB
Insgesamt bist Du dann mit dem gelesenen CSV und Deine Datenarray bei fast 28 MB RAM.

Je öfter Du diese Datenmengen im RAM hin und her wuselst, desto länger dauert es.
Im Allgemeinen kein Problem, haben die meisten heutigen Endgeräte doch um und bei 1GB an RAM. Bei älteren Geräten mit ihren 256MB und einem Rohverbrauch von 150MB nur für Android sieht das hingegen schon gaaaaanz anders aus. Da kann Dir die Kombination OS + Hintergrundprozesse + Mailprogramm + Facebook + Deine App schon mal ein onMemoryLow() Event auslösen.

Und drittens: teste das Ganze nicht nur im Emulator. Der ist bei solchen Aktivitäten mindestens um den Faktor 5 langsamer als ein durchschnittlich ausgestattetes Endgerät.
So etwas musst Du immer auf dem langsamsten Endgerät testen, dass Du in die Finger bekommen kannst!